神彩争霸88计划官方想伪装成资深程序员?知道这三个数据结构就够了

  • 时间:
  • 浏览:20

春招来袭啦!又要面试啦!

程序员面试展示哪2个最重要?当时是你渊博的计算机学识,以及聪明的小脑瓜。

本来 你学富五车,上知淬硬层 学习, 下知财务会计,那短短数小时也绝欠缺你表演。很多,你一定得知晓面试官的套路,随口丢出2个应景的“冷知识”卖个乖巧。

本来 你基础神彩争霸88计划官方不行,4天 前刚准备转码,那就更得准备2个的小把戏,不需要打肿脸不能充一回胖神彩争霸88计划官方人。

基于这有4个 需求,今天文摘菌就来给村里人 介绍有4个 讨巧的数据特征。面试当中一提,那从前相当撑场面。

这有4个 数据特征本来 。神彩争霸88计划官方登登登等…

1. 布隆过滤器(bloom filter)

2. 前缀树(prefix trie)

3. 环形缓冲(ring buffer)

先来说一下,为哪2个挑了这有4个 数据特征。

首先我随便说说,你提到的数据特征要稍微冷门或多或少,从前别人就会认为你了解很多不类似型的数据特征。但它不可不需要能太冷门,以免你的面试官要求你真正解释实现细节或原理,那时你就game over了。***是你提到的数据特征有点儿冷门,但你的面试官听说过,对它有印象。

面试官都希望被委托人哪2个都知道,村里人 听说过你这个数据特征但又不太了解,当你向村里人 介绍时,村里人 就会随便说说你懂得有点儿多。

除此之外,哪2个数据特征还应该具有实际用例,以便在技术面试的后后,你能有本来 展开介绍。它随便说说稍微有点儿冷门但本来 能太low,你本来 只知道或多或少菜鸡水平的数据特征(比如双向链表),你的面试八成就凉了。

很多,这有4个 数据特征就被***选中啦!

布隆过滤器

布隆过滤器是集合的概率版本。检测集合与非 暗含某元素的时神彩争霸88计划官方间简化度为O(1)、空间简化度为O(N)。Bloom过滤器也可不需要能检测出集合与非 本来 暗含该元素,它的时间简化度为O(1),而空间简化度只前要O(1)!

谁会真正使用布隆过滤器?

Chrome前要在不牺牲传输速度或空间的情況下保护你免受访问垃圾邮件网站。

想象一下,本来 每次你点击有4个 链接,Chrome都前要进行网络通话来检查它庞大的垃圾邮件URL数据库,本来 才允许你访问你这个页面,这会不需要要我等疯掉。此外,设想一下,本来 Chrome改善延迟的处置方案是在本地存储整个垃圾邮件URL列表,这根本本来 不可行的!

很多,chrome在本地存储了有4个 潜在垃圾邮件URL的布隆过滤器,这既节省时间又节省空间,可不需要能快速检查给定的URL与非 为垃圾邮件。对于普通的URL,布隆过滤器对“非垃圾邮件”的响应就足够判定了。本来 有4个 URL被标记为“本来 是垃圾邮件”,这麼Google可不需要能在跳转后后检查它真实数据库。事实证明,当要我我牺牲绝对时,要我做出伟大的事情!

布隆过滤器的原理

布隆过滤器的维基百科页用血块的术语描述了实现细节,很多在这里我会用简单的描述一下实现过程。本来 要我我更精确的细节,你应该去看看维基百科。我会略过很多步骤,但我会要我有有4个 大致了解。

本来 你想在Bloom过滤器中插入有4个 元素,首先假设有N个不同的挑选性哈希函数。当同有4个 元素输入不同哈希函数时,会得到不同的值(冲突是可不需要能有的)。

使用每个哈希函数的输出作为数组的索引[注释1,注释2],并对应每个索引i将数组[i]设置为true。插入元素就完成了!插入元素的时间简化度是O(1),本来 对每个插入元素所做的唯一工作是运行恒定数量的哈希函数,并设置恒定数量的数组索引。

那该怎么检查布隆过滤器与非 暗含该元素? 再次运行所有相同的哈希函数!

哈希函数是挑选性的,本来 相同的输入应返回相同的输出。很多相对应每个索引,检查布隆过滤器的数组与非 在该索引处设置为true即可。本来 哈希函数输出的数组的每个单元都为真,这麼可不需要能很高的概率说你这个元素本来 插入到了布隆过滤器中。你这个土土办法老要指在误报的本来 性。不过,布隆过滤器的一大特色是永远不需要冒出漏报。

这麼,你前要2个个哈希函数,又前要多大的数组呢?这你就得好好算一番了。维基百科对它们的解释更完整篇 ,你值得一读。

注释1:怎么使用哈希函数的输出作为索引:设哈希函数输出整数值M,取长度N。N%M(N mod M)得到有4个 值Q,即0≤Q

注释2:实际上,你应该使用位数组而全是普通数组。数组的每个元素大概 前要有4个 神彩争霸88计划官方字节,而你只前要为“数组”的每个元素存储true / false。本来 ,要我通过将其存储为位数组来节省空间,这是你这个数据特征的重点。本来 要我我听起来很聪明,这麼位数组(也本来 位向量)也值得你在面试时提出。嗯,真正的面试专家建议老要在脚注中。

注释3:严格来说,本来 你的所有哈希函数全是O(1)时间内运行,这麼插入的简化度才是O(1)。

前缀树(prefix trie)

前缀树是并与非 数据特征,允许你通过其前缀快速查找字符串,还可不需要能查找有公共前缀的字符串。

我对介绍你这个数据特征的***条建议是,将它称为“前缀树”,而不仅仅是“树”。从前,你后后面试官知道你是那种了解与前缀和后缀相关算法的人,本来 你也希望对你的fancy数据特征进行准确描述。后缀树也是有4个 非常有趣一句话题,但实现细节十分残暴。这本来 为哪2个要我是谈论前缀树,本来 假装了解后缀树。

谁会真的用前缀树?

基因组学研究人员!

事实证明,现代基因组研究在很大程度上依赖于字符串算法和数据特征,本来 你试图从组成基因组序列的数百万个核苷酸中探索奥秘。对于基因组数据,你老要前要对齐序列,找到差异或找到重复的模式。本来 你想了解更多相关信息,可不需要能先阅读生物信息学读物,本来 参与“DNA测序算法”或“生物信息学算法”等课程。

本来 要我我阅读或多或少真正有意思的读物,我强烈建议你读一读药物基因组学。随着基因组测序和字符串算法的进步,村里人 实际上可不需要能预测使用个体的基因组,来挑选它们与非 具有对药物正确反应的正确基因。类似,本来 村里人 的基因组缺少用于产生处置并与非 药物的酶的基因,这麼药物本来 会对村里人 产生副作用。本来 村里人 知道哪2个基因是重要的,村里人 可不需要能给村里人 并与非 不同的药物!

我承认,前缀树和基因组学之间的联系不太紧密。随便说说前缀树的最直接用法本来 用来查字典啦!但光这麼讲全是忒无聊了点么。

前缀树的原理

想象一下,你有一棵树,每个节点全是有4个 暗含26个子节点的数组,每个子节点对应有4个 英文字母。(本来 要暗含或多或少字符,可不需要能将26更改为不同的值。)要在你的树中表示单词,你将从根节点现在现在开始 ,沿着路径向下走,并在每个节点加暗含4个 字母。

类似(图片来源维基百科),对于“tea”你这个词,你从根现在现在开始 ,被引导到t节点,本来 是e,***是a。本来 ,搜索单词前要O(N)的时间(其中N是单词的长度),本来 单词的前缀不指在,则可不需要能提前现在现在开始 。本来 我查询“zzzzzzzz”,树可不需要能在“zz”后后现在现在开始 查询。

环形缓冲区(ring buffer)

环形缓冲区是使用普通数组的并与非 非常好的土土办法,它主要被用于处置数据流。

谁会真的使用环形缓冲区?

说不定Netflix会用?

我用google搜索“netflix ring buffer”,发现了村里人 发布了或多或少开源环缓冲区代码。但难题报告 是,公司真的会用村里人 本来 开源的代码嘛?

环形缓冲区的原理

好啦好啦。真的还村里人 在读这篇文章嘛。

本来 你读到了这儿,说明你基础一定还不错,那就直接去维基百科瞅一眼你这个数据特征吧,比前有4个 简单多了!

总结一下,今天文摘菌介绍了有4个 重要的数据特征:布隆过滤器(bloom filter),前缀树(prefix trie),环形缓冲(ring buffer)。

想当有4个 聪明程序员,哪2个特征你值得拥有!

【本文是51CTO专栏机构大数据文摘的原创译文,微信公众号“大数据文摘( id: BigDataDigest)”】

     

戳这里,看该作者更多好文

【编辑推荐】

【责任编辑:

张燕妮

TEL:(010)684763006】



点赞 0