原⽂链接：
更多精彩内容(BAT招聘、笔试、⾯试、技术)，请访问
题⽬
问题⼀：现有海量⽇志数据，要提取出某⽇访问百度次数最多的那个IP(可以将题⼲简化，假设⽇志中仅包含IP数据，也就是说待处理的⽂件中包含且仅包含全部的访问IP，但空间有限，不能全部加载，假设只有512MB)
解决⽅案：
这是⼀道典型的思想的题⽬，这种问题处理起来套路⽐较固定，对于⼤部分的数据量⽐较⼤的前提的问题⽽⾔，分治都是⼀个可选的解决⽅ 案，但不⼀定是最优的，解决⽅法基本划分为三步⾛：无机粘结剂
那么对于本问题就显得⽐较明显了：
⾸先解决如何划分，由于IP地地址范围从000.000.000.000~255.255.255.255共有2^32个⼤约4GB，那么我们可以通过取模的⽅式进⾏划分，直接将四段数据相连就得到⼀个IP对应的数字A，再对A模1024(模数取多少可以⾃⼰指定，保证每个⼩⽂件能被放到内存就好)，这样⼤⽂件被划分成⼩⽂件了，并且相同的IP⼀定被划分到相同的⽂件中。 其次解决每个⼩⽂件中TOP1的问题：
这⾥可以⽤很多⽅式进⾏处理，⽐如你可以构造⾃⼰的HashMap,key为IP，value为当前出现次数，最后到value最⼤的Key即为当前⽂件中出现次数最多的IP。
最后要解决结果合并问题：
这⾥直接将1024个⼦⽂件的统计结果进⾏⽐较就好，不⽤排序，直接选择最⼤的⼀个就好。
注意：这⾥第⼆步是影响效率的地⽅，读者可以想想如何优化这⾥的Wordcount，可以⽤trie树等
问题⼆：有⼀个1G⼤⼩的⼀个⽂件，⾥⾯每⼀⾏是⼀个词，词的⼤⼩不超过16字节，内存限制⼤⼩是1M。返回频数最⾼的100个词。解决⽅案：细⼼的读者可以发现这个和第⼀个问题应该没有太⼤别，区别就在于第⼀个问题是Top1，这个问题是TOP100。
那么对于这个问题，主要考虑的是如何划分(每个⽂件要⼩于1M)，这⾥可以考虑划分为2028份。
对于第⼆步可以考虑⽤
即常⽤的TopN⼿段。第⼀：如何有效的划分数据第⼆：如何在⼦集上解决问题第三：如何合并结果
1
2
3
4
5
第三部就是更为常见的
问题三：给定a、b两个⽂件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你出a、b⽂件共同的url？
解决⽅案：这种题⽬，我⾸先想到的就是
当然使⽤布隆过滤器存在⼀定的错误率，所以⾯试者可以和⾯试官进⾏进⼀步的沟通，看是否允许有⼀定的错误率。
如果使⽤布隆过滤器，那么问题就很好办了，4G的内存⾜以容纳300多亿的bit，所以⾜够处理了，先将a⽂件中的url都放⼊布隆过滤器，之后遍历b⽂件，对每个url都询问布隆过滤器看其是否已经存在，如果存在，则此条URL输⼊结果⽂件。
关于布隆过滤器使⽤空间和错误率的关系可以看
第⼆种⽅案就是采⽤更为通⽤的但对于这个问题效率较低的分治思想，对a,b进⾏分⽚，a,b⽂件⼤⼩都⼤约320G，那么每个⽂件都切分成1G的320个⼩⽂件。
伪代码如下：
当然这个在实现的时候可以进⼀步优化，⾸先可以并⾏处理(这⾥只⽤了2G内存，所以⾄少可以2个线程并⾏)
其次，可以对a中URL进⾏⼩部分判重处理，如果之前已经有了，
就不必处理。
问题四：有10个⽂件，每个⽂件1G，每个⽂件的每⼀⾏存放的都是⽤户的query，每个⽂件的query都可能重复。要求你按照query的频度排序。
解决⽅案：这种题⼜是典型的wordcount问题，⾸先这种题不⽤说都是内存有限制(最好问问⾯试官，内存限制是多少)。如果没内存限制直接⼀个trie树就搞定了(因为⼀般来说query的重复都⽐较多)。
如果内存限制⽐较⼤，那么可以尝试屡试不爽的分治⽅法。但在使⽤之前需要先对原来的⽂件进⾏⼀下处理通过hash(url)%A，这⾥A只分成多少分，这⾥可以也取10，就是将原来的10个⽂件转为新的10个⽂件，如果内存限制⽐较⼤，那么这个A可以根据内存⼤⼩调整，要让1G/A <= 内存⼤⼩。
接下来就是要对每个⼩⽂件进⾏统计，可以⽤hashmap(url,count)，也可以⽤trie树。
之后采⽤的⽅法得到最终结果。
问题五：怎么在海量数据中出重复次数最多的⼀个？
解决⽅案：如果看了前⾯四个题⽬，这⾥相信读者应该已经会⾃⼰解决了。
使⽤屡试不爽的分治思路，先划分成⼩⽂件，之后分别统计，之后再选取max，读者可以思考如何优化⼩⽂件内的处理⽅法。
问题六：在2.5亿个整数中出不重复的整数，注，内存不⾜以容纳这2.5亿个整数。
解决⽅案：⾸先对于这种问题基本上都可以采⽤分治的思想，先进⾏划分后进⾏单独处理，最后进⾏结果合并。但对于这道题⽬显然分治思想⽐较牵强，效率不⾼。lista->{a1,a320}listb->{b1,b2,b3 (320)
1
2
固液分离装置
3resultlist = []for tmpfile in lista: for infile in listb: for url in tmpfile: if url in infile: resultlist.add(url)
1
2
3
4
5
6
那么再审视⼀下这个题⽬，其只需要到不重复的整数，⽆需什么排序，⽽且⼜限定在整数，那么显然可以考虑位集的思想。
2.5亿个整数，显然可以⽤⼀个250M的位集表⽰。
⼀个位集可以表⽰如下：
但简单的位集只能表⽰存在与否，因为每个bit表⽰⼀个整数，1个bit只能表⽰两种情况，但在本题⽬中不但需要表⽰存在性，还需要表⽰是否多次出现，即需要寻出现次数>=2，那么⾄少需要两个bit才能表⽰这种情况，00->不出现，01->出现⼀次，10->出现⾄少2次，这样就能统计出那些数据出现重复。
总结⼀下就是本题⽬可以⽤位集的变形，每个数⽤2个bit表⽰，那么总共需要250M*2b = 500Mb的内存，完全满⾜题⽬，⽽且效率还是o(n)。
荸荠削皮机问题七:⼀个⽂本⽂件，⼤约有⼀万⾏，每⾏⼀个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。解决⽅案：分治思想这⾥就简要阐述⼀下，可以利⽤trie树进⾏词频统计，之后采⽤TopN的解决⽅法，关于排序的问题可以看
369ii
折叠桶堆排序的时间复杂度是n(longk),n是数据集合⼤⼩，k是topK中的k，那么复杂度是max(n*len(e),nlogk)，其中len(e)表⽰字符串平均⼤⼩。这⾥想讲⼀下另⼀种稍显技巧的⽅法，即⽤变形的位集表⽰，由于题⽬中只有1w的数据，那么⼀个词最多出现1w词，那么⽤18个bit就可以表⽰最多出现的次数，说道这⾥读者可以回顾⼀下第六个题⽬了，其实和题⽬六很相似的，这⾥每个数字⽤18个bit表⽰，那么剩下的问题就是解决如何将每个词转化为1~10000的数字，这⾥读者可以⾃⾏YY或者⾃⾏搜索，⽅法有很多。关键的问题是要想到可以⽤这种⽅式来解决，那么复杂度显然就是o(n)
问题⼋：给40亿个不重复的unsigned int的整数，没排过序的，然后再给⼀个数，如何快速判断这个数是否在那40亿个数当中？ （PS：腾讯⾯试题）
解决⽅案：这个题⽬限定的⽐较明确了，整数、不重复，那么理所当然可以⽤bitMap的思想去解决了。
申请⼀个40亿的bit数组，初始化为0，遍历数据集合，有的占位1，给定待验证的数据，直接看相应位置的是1还是0即可。
当然有⼈可能觉得40亿的bit内存装不下啊，那怎么办，当然可以分治了，写到N个⽂件中总可以了吧，根据待验证的数，直接查相应的⽂件，在相应的⽂件中查看是1还是0。
⽐如分成1W份，被分割的⽂件按下标存储：
那么相当于每个⽂件存储4Mb的位，待验证的数据为a，那么⽬标⽂件的index为
求出index，再在file(index)中查。
问题九：上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。
解决⽅案：典型的TopN问题，请参考前⾯的问答题。
问题⼗: 搜索引擎会通过⽇志⽂件把⽤户每次检索使⽤的所有检索串都记录下来，每个查询串的长度为1-255字节。假设⽬前有⼀千万个记录（这些查询串的重复度⽐较⾼，虽然总数是1千万，但如果除去重复后，不超过3百万个。⼀个查询串的重复度越⾼，说明查询它的⽤户越多，也就是越热门），请统计出最热门的10个查询串，要求使⽤的内存不能超过1G。
解决⽅案：典型的TopN问题，请参考前⾯的问题的答案，可以考虑使⽤分治的思想。file1,file2,file3 ... file10000
1index*400000<=a<=(index+1)*400000
1
总结：处理海量数据问题的四板斧
1.分治
基本上处理海量数据的问题，分治思想都是能够解决的，只不过⼀般情况下不会是最优⽅案，但可以作为⼀个baseline，可以逐渐优化⼦问题来达到⼀个较优解。传统的就是分治思想，涉及到⼤量⽆法加载到内存的⽂件、排序等问题都可以⽤这个⽅法解决。
适⽤场景：数据量⼤⽆法加载到内存
技能链接:
2.哈希(Hash)
个⼈感觉Hash是最为粗暴的⼀种⽅式，但粗暴却⾼效，唯⼀的缺点是耗内存，需要将数据全部载⼊内存。
适⽤场景：快速查，需要总数据量可以放⼊内存
3.bit(位集或BitMap)
位集这种思想其实简约⽽不简单，有很多扩展和技巧。⽐如多位表⽰⼀个数据(能够表⽰存在和数量问题)，BloomFilter(布隆过滤器就是⼀个典型的扩展)，在实际⼯作中应⽤场景很多，⽐如消息过滤等，读者需要掌握，但对于布隆过滤器使⽤有⼀些误区和不清楚的地⽅，读者可以看下⾯这篇博客避免这些性能上的误区。
适⽤场景：可进⾏数据的快速查，判重
技能链接:
4.堆(Heap)
堆排序是⼀种⽐较通⽤的TopN问题解决⽅案，能够满⾜绝⼤部分的求最值的问题，读者需要掌握堆的基本操作和思想。
适⽤场景：处理海量数据中TopN的问题(最⼤或最⼩)，要求N不⼤，使得堆可以放⼊内存
技能链接:
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议