2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设目前有1000万条记录（这些查询字符串的重复度比较高，虽然总数是1000万条，但是如果去掉重复的话，不会超过300万条。重复度越高查询字符串的数量，这意味着查询它的用户越多，它就越受欢迎。）请统计10 个最流行的查询字符串。所需内存不能超过1G。
本文对典型的Top K算法进行了解释。文中最终给出的算法是：第一步对这批海量数据进行预处理，利用Hash表在O(N)时间内完成排序；然后，第二步使用数据结构堆查找Top K，时间复杂度为N"logK。也就是说，借助堆结构，我们可以在log时间内找到并调整/移动。因此，维护一个大小为K（本题为10）的小根堆，然后遍历300万个Query，分别与根元素进行比较。因此，我们最终的时间复杂度为：O(N) + N"*O(logK)，（N为1000万，N"为300万）。好吧，更详细的内容请参考原文。
或者：使用trie树，关键字字段存储查询字符串出现的次数。如果没有出现则为0。最后用最小推10个元素来对出现频率进行排序。
3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
解决方案：按顺序读取文件。对于每个单词x，取hash(x)%5000，然后将值存储到5000个小文件中（记为x0,x1,x4999）。每个文件大约200k。
如果部分文件大小超过1M，可以继续以类似的方式进行分割，直到分解后的小文件大小不超过1M。对于每个小文件，统计每个文件中出现的单词及其对应的频率（可以使用trie树/hash_map等），取出出现频率最高的100个单词（可以使用100个节点的最小堆） ），并将100个单词和对应的频率保存到文件中，从而获得另外5000个文件。接下来就是对这5000个文件执行归并（类似于归并排序）过程。
4、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
仍然是典型的TOP K算法。解决方案如下： 方案一：顺序读取10个文件，根据hash(query)%10的结果将查询写入另外10个文件（记为）。这样，每个新生成的文件大小约为1G左右（假设哈希函数是随机的）。找一台内存2G左右的机器，使用hash_map(query, query_count)统计每个query出现的次数。使用快速/堆/合并排序按出现次数排序。将排序后的查询和对应的query_cout输出到文件中。这样就得到了10个排序后的文件（标记为）。
对这10个文件进行合并排序（内部排序和外部排序相结合）。
方案二：一般查询总量有限，但重复次数比较多。可能所有查询都可以一次添加到内存中。这样我们就可以利用trie树/hash_map等直接统计每个查询出现的次数，然后根据出现的次数进行快速/堆/归并排序。
方案3：与方案1类似，但是散列后分成多个文件，可以交给多个文件处理，采用分布式架构（如MapReduce），最后合并。
5、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
方案一：可以估算每个文件的大小为5G64=320G，远大于4G的内存限制。所以不可能完全加载到内存中进行处理。考虑分而治之的方法。
遍历文件a，获取每个URL的hash(url)%1000，然后根据获取的值将URL存储到1000个小文件（记为a0、a1、a999）中。每个小文件大约300M。
遍历文件b，将url存入1000个小文件中（记为b0,b1,b999），方法与a相同。经过这样处理后，所有可能相同的url都在对应的小文件（a0 vs b0,a1 vs b1,...,a999 vs b999）中，不对应的小文件不可能有相同的url。那么我们只需要在1000对小文件中找到相同的URL即可。
当在每对小文件中找到相同的URL时，可以将其中一个小文件的URL存储在hash_set中。然后遍历另一个小文件的每个URL，看是否在刚刚构造的hash_set中。如果是，则它是一个通用URL，可以保存在文件中。
方案2：如果允许一定的错误率，可以使用布隆过滤器。 4G内存可以代表大约340亿位。使用布隆过滤器将其中一个文件中的URL映射到这340亿位，然后一一读取另一个文件的URL，检查是否与布隆过滤器匹配。如果是这样，那么该URL应该是一个普通的URL（注意会有一定的错误率）。
布隆过滤器以后会在这个BLOG里详细讲解。
6、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
方案一：使用2-Bitmap（每个数字分配2位，00表示不存在，01表示出现一次，10表示多次，11无意义）。它需要总内存并且是可以接受的。然后扫描这2.5亿个整数，检查Bitmap中对应的位。如果00变为01，01变为10，10保持不变。绘制完成后，检查位图，输出对应位为01的整数。
方案2：也可以使用类似于问题1的方法来分割小文件。然后在小文件中找到唯一的整数并对其进行排序。然后合并，注意去除重复元素。
7、腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
和上面的问题6类似，我的第一反应是快速排序+二分查找。下面是其他更好的方法：方案1：oo，申请512M内存，一位代表一个unsigned int值。读入40亿个数字，设置对应的位，读入要查询的数字，检查对应的位是否为1，如果为1则表示存在，如果为0则表示不存在。
dizengrong:方案2：这个问题在《编程珠玑》中有很好的描述。大家可以参考下面的思路来讨论：而因为2^32超过了40亿，所以给定的数字可能在也可能不在其中。这里我们将40 亿个数字中的每一个都表示为32 位二进制。假设这40 亿个数字最初放置在一个文件中。
然后将这40亿个数字分成两类： 1.最高位为0 2.最高位为1并将这两类分别写入两个文件。一个文件中的数字数量=20 亿，另一个文件=20 亿（这相当于减半）；与要查找的数字的最高位进行比较，然后进入相应的文件中重新查找
然后把这个文件分成两类： 1.第二高位为0 2.第二高位为1
并将这两个类别分别写入两个文件，一个文件的数字数量=10亿，另一个=10亿（这相当于减半）；与要查找的数字的第二高位进行比较，然后进入相应的文件再次查找。 以此类推，即可求出，时间复杂度为O(logn)。解决方案2已完成。
附：这里简单介绍一下位图方法： 使用位图方法判断整数数组中是否存在重复项是常见的编程任务之一。当集合中的数据量比较大时，我们通常希望减少步骤数。此时不宜采用双循环方法。
位图方法更适合这种情况。它的方法是根据集合中的最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到任意就给新数组的位置赋值1。如果遇到5，就将新数组的第六个元素设置为1，这样下次遇到5想要设置的时候，就会发现新数组的第六个元素已经是1了，也就是说这次的数据一定和之前的一样。数据中有重复。这种通过将新数组设置为零然后将其设置为一来初始化新数组的方法类似于位图处理方法，因此称为位图方法。最坏情况下的操作次数为2N。如果已知数组的最大值，并且可以预先固定新数组的长度，那么效率可以提高一倍。
8、怎么在海量数据中找出重复次数最多的一个？
方案一：先做散列，然后找到模块映射成小文件，在每个小文件中找到重复次数最多的，记录重复次数。然后在上一步得到的数据中找出重复次数最多的就是你想要的（具体参考上一题）。
9、上千万或上亿数据（有重复），统计其中出现次数最多的钱N个数据。
选项1：当前机器的内存应该能够存储数千万或数亿的数据。因此，可以考虑使用hash_map/搜索二叉树/红黑树等来统计次数。接下来就是取出出现次数最多的前N个数据。这可以使用问题2 中提到的堆机制来完成。
10、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
选项1：本题考虑时间效率。使用trie树统计每个单词出现的次数，时间复杂度为O(nle)（le代表单词的平均长度）。然后找到出现频率最高的前10个单词，可以使用堆来实现。正如上一个问题提到的，时间复杂度是O(nlg10)。因此总时间复杂度取O(nle) 和O(nlg10) 之间较大的一个。
附、100w个数中找出最大的100个数。选项1：在上一个问题中，我们已经提到它是用包含100个元素的最小堆来完成的。复杂度为O(100wlg100)。
方案二：使用快速排序的思想。每次划分后，仅考虑大于轴的部分。当大于轴的部分超过100个时，使用传统排序算法排序，取前100个，复杂度为O(100w100)。
选项3：使用部分消除法。选择前100个元素进行排序，记为序列L。然后每次扫描剩余的元素x，与这100个已排序元素中最小的元素进行比较。如果大于最小元素，则删除最小元素，插入L进去。依次循环，直到扫描完所有元素。复杂度为O(100w*100)。
好了，关于深度解析：海量数据处理面试难题解析及十项高效策略汇总和的问题到这里结束啦，希望可以解决您的问题哈！
【深度解析：海量数据处理面试难题解析及十项高效策略汇总】相关文章：
2.米颠拜石
3.王羲之临池学书
8.郑板桥轶事十则
用户评论
这篇文章讲了什么呀？好想学一下海量数据的处理技巧。
有15位网友表示赞同！
面试准备材料啊！收藏了，希望能真有机会用得上这些知识。
有20位网友表示赞同！
我可有点担心自己对海量数据处理了解的还不够深入哎。
有7位网友表示赞同！
十道题确实不少，需要好好练习一下才能应对面试吧。
有10位网友表示赞同！
数据分析这行貌似越来越热门了，学习这些处理方法很关键的样子。
有18位网友表示赞同！
希望能详细讲解一下那些方法，方便理解运用。
有20位网友表示赞同！
海量数据处理感觉非常抽象，希望文章能用一些例子来解释。
有16位网友表示赞同！
面试官喜欢问什么类型的问题呢？ 提前了解下比较好应对啊。
有17位网友表示赞同！
最近在学习编程，学习这方面知识也对未来发展很有帮助。
有16位网友表示赞同！
大数据处理这块我需要多加练习才行，希望能通过文章来提升水平
有5位网友表示赞同！
原来海量数据处理方法这么多种多样啊！感觉自己还有很多地方需要加强。
有20位网友表示赞同！
学习新的技能总是很让人兴奋的。期待能从这篇文章中学到不少东西！
有15位网友表示赞同！
面试题和方法总结一起看，学习起来也更系统一些。
有17位网友表示赞同！
这种类型的文章很有用，可以帮我了解这个领域的知识点。
有9位网友表示赞同！
看来海量数据处理真的是一个重要且复杂的领域。
有8位网友表示赞同！
希望这篇文章能给我提供一些实用的技巧和方法。
有18位网友表示赞同！
学习起来的时候注意要把文章的内容好好消化理解才比较好运用到实际工作中。
有12位网友表示赞同！
期待接下来能持续学习更多关于大数据处理的知识！
有14位网友表示赞同！