春天来了！再次面试！程序员面试最重要的是展示什么？那时候是你渊博的计算机功底和聪明的小脑袋。如果你的知识很多，上层是深度学习，下层是财务会计，那几个小时永远不够你发挥。所以，一定要知道面试官的套路，随口抛出几句“冷知识”，借机逗一下。如果你基础不好，三天前才准备转码，那你就得准备几招，让你又胖又不肿脸。基于这两个需求，今天文摘菌就给大家介绍三种别出心裁的数据结构。在采访中提到的时候，那是相当的场面。这三个数据结构是。Dendenden等...1.布隆过滤器（bloomfilter）2.前缀特里树（prefixtrie）3.环形缓冲区（ringbuffer）先说说为什么选择这三种数据结构。首先，我觉得你提到的数据结构有点不太流行，以至于别人会认为你知道很多不同类型的数据结构。但是也不能太冷，免得面试官让你真的把实现细节或者原理说清楚，那你就完蛋了。***是你说的数据结构有点冷门，但是你的面试官听过，有印象。面试官希望他们什么都知道。他们听说过这种数据结构，但了解不多。当你介绍给他们时，他们会觉得你知道的很多。另外，这些数据结构还应该有实际的用例，这样在技术面试的时候才有机会介绍。虽然有点冷门，但也不能太low。如果你只知道一些菜鸟级别的数据结构（比如双向链表），你的面试估计会很冷。因此，这三种数据结构被***选中！布隆过滤器布隆过滤器是集成的概率版本。检查集合是否包含元素的时间复杂度为O(1)，空间复杂度为O(N)。布隆过滤器还可以检测集合是否可能包含元素，它的时间复杂度是O(1)，空间复杂度只需要O(1)！谁会真正使用布隆过滤器？Chrome需要在不牺牲速度或空间的情况下保护您免于访问垃圾网站。想象一下，如果每次您单击一个链接，Chrome都必须进行网络调用以检查其庞大的垃圾邮件URL数据库，然后才能允许您访问该页面，这会让您疯狂等待吗？另外，想象一下，如果Chrome改善延迟的解决方案是在本地存储整个垃圾URL列表，这根本不可行！因此，chrome在本地存储了一个潜在垃圾邮件URL的布隆过滤器，这样可以节省时间和空间，并允许快速检查给定的URL是否为垃圾邮件。对于普通URL，布隆过滤器响应“不是垃圾邮件”就足够了。如果一个URL被标记为“可能是垃圾邮件”，Google可以在跳转到它之前检查它的真实数据库。事实证明，当你愿意牺牲绝对时，你可以做伟大的事情！BloomFilter的工作原理Bloom过滤器的Wikipedia页面用很多术语描述了实现细节，所以我将在这里用简单的术语描述实现。如果你想要更精确的细节，你应该查看维基百科。我将跳过很多步骤，但我会给你一个概述。如果要在布隆过滤器中插入一个元素，首先假设有N个不同的确定性哈希函数。当同一个元素被输入到不同的哈希函数中时，会得到不同的值（有可能发生碰撞）。使用每个散列函数的输出作为数组[注1，注2]的索引，并将每个索引i的数组[i]设置为true。插入元素，你就完成了！插入元素的时间复杂度为O(1)，因为对每个插入元素所做的唯一工作是运行恒定数量的哈希函数，并设置恒定数量的数组索引。那么如何检查布隆过滤器是否包含该元素呢？再次运行所有相同的哈希函数！哈希函数是确定性的，所以相同的输入应该返回相同的输出。所以对应每一个索引，检查布隆过滤器数组是否在索引处设置为true。如果哈希函数输出的数组的每个元素都为真，那么可以说这个元素很有可能已经被插入到布隆过滤器中。这种方法总是存在误报的可能性。然而，布隆过滤器的一大特点是永远不会出现漏报。那么，您需要多少个散列函数，需要多大的数组？您必须对此进行数学计算。维基百科对它们进行了更详细的解释，值得一读。注1：哈希函数的输出如何作为索引：让哈希函数输出一个整数值M，取长度N。N%M(NmodM)得到一个值Q，即0≤Q注2：实际上，您应该使用位数组而不是普通数组。数组的每个元素至少需要1个字节，你只需要为“数组”的每个元素存储true/false。因此，您可以通过将其存储为位数组来节省空间，这是该数据结构的全部要点。如果你想让自己听起来很聪明，位数组（又名位向量）也值得在面试中提及。好吧，真正的专家面试建议总是在脚注中。注3：严格来说，如果您的所有哈希函数都在O(1)时间内运行，则插入复杂度仅为O(1)。前缀树（prefixtrie）前缀树是一种数据结构，可以让你通过前缀快速查找字符串，也可以找到具有共同前缀的字符串。我对引入这种数据结构的第一个建议是称它为“前缀树”，而不仅仅是“树”。这样，您就可以让面试官知道您是那种了解与前缀和后缀相关的算法的人，并且您还希望准确描述您喜欢的数据结构。后缀树也是一个很有趣的话题，但是实现细节很残酷。这就是为什么我只谈论前缀树并假装知道后缀树。谁真正使用前缀树？基因组学研究人员！事实证明，当您试图解开构成基因组序列的数百万个核苷酸的奥秘时，现代基因组研究在很大程度上依赖于字符串算法和数据结构。对于基因组数据，您通常需要比对序列、发现差异或发现重复模式。如果你想深入了解它，你可以从生物信息学阅读开始，然后学习“DNA测序算法”或“生物信息学算法”之类的课程。如果你想做一些真正有趣的阅读，我强烈推荐阅读药物基因组学。随着基因组测序和字符串算法的进步，我们实际上可以使用个体的基因组进行预测，以确定他们是否拥有正确的基因来对药物做出正确的反应。例如，如果他们的基因组缺少处理某种药物的酶的基因，则该药物可能会对他们产生副作用。如果我们知道哪些基因很重要，我们就可以给它们一种不同的药物！我承认，前缀树和基因组学之间的联系不是很强。其实前缀树最直接的用法就是查字典！但这不会很无聊吗？前缀树的原理想象一下，你有一棵树，每个节点都有一个包含26个子节点的数组，每个子节点对应一个英文字母。（如果您想包括其他字符，您可以将26更改为不同的值。）要在树中表示单词，您将从根节点开始，沿着路径前进，并在每个节点处添加一个字母。例如（图片来源维基百科），对于“tea”这个词，你从根开始，被引导到t节点，然后是e，最后是a。因此，搜索一个词需要O(N)的时间（其中N是词的长度），并且如果词的前缀不存在可以提前结束。如果我查询“zzzzzzzzz”，树可以在“zz”之后结束查询。环形缓冲区（ringbuffer）环形缓冲区是一种非常好的使用普通数组的方法，它主要用于处理数据流。谁真正使用环形缓冲区？也许Netflix会使用它？我用谷歌搜索“netflix环形缓冲区”，发现他们发布了一些开源环形缓冲区代码。但问题是，企业真的会使用他们开源的代码吗？环形缓冲区的原理很好。真的有其他人在读这篇文章吗？如果你能读到这里，说明你的基础一定不错，那就去维基百科看看这个数据结构吧，比前两个简单多了！综上所述，Digest今天介绍了三种重要的数据结构：Bloomfilter、prefixtrie、ringbuffer。如果你想成为一个聪明的程序员，你值得拥有这些结构！【本文为栏目组织大数据文摘原创翻译，微信公众号“大数据文摘（id：BigDataDigest）”】点此查看作者更多好文
