腾讯海量数据面试题
1 在一个文件中有10G 个整数，乱序排列，要求找出中位数。内存限制为2G。
10G个数，中位数就是第5G、第5G+1个数。
回想一下，一般情况下求中位数的做法：类似于快排的partition，找到一个数，使比它小的数的个数占到总数的一半就行。
可以把数值空间分段，然后统计每一段中数据的个数，这样就可以很容易的确定中位数在那一段。找个该段后，数据量已经急剧减小了，剩下的问题就好处理了。
这种方法可以说是桶排序的思想，也可以说是hash的思想。
下面具体分析一下：
因为要统计每一段中数据的个数，所以可以用一个unsigned int型。unsigned int一般占4个字节，可以计数到2^32-1，大约是4G。题目中有10G个数，如果有很多数落在同一个段中，unsigned int肯定不够用。所以，这里的计数用要8字节的long long。即，相当于有一个数组，数组是long long性，数组的每一个元素，代表了一个数据段内的数据个数。这个数组有多大？为了充分利用2G内存，数组大小2G/8 = 256M。即，有数组long long cnt[256M].
假设题目中的10G个数都是4字节的int。如何把这10G个整数，映射到cnt[256M]的数组中。可以使用计算机中的虚拟地址到物理地址的转换。取int的高28位作为数组下标的索引值，这样就可以完成映射。
整个算法的流程：
a扫描10G个整数，对每个整数，取高28位，映射到数组的某个元素上
b给数组的这个元素加1，表示找到一个属于该数据段的元素
c扫描完10G个整数后，数组cnt中就记录了每段中元素的个数
d从第一段开始，将元素个数累计，直到值刚好小于5G，则中位数就在该段
e这时对10G个整数再扫描一遍，记录该段中每个元素的个数。直至累计到5G即可。
2 一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数。
方法一：
使用位图。4字节的int，有4G个不同的值。每个值，对应1bit，则共需 4G/8 = 512M 内存。初始状态，对512M的位图清零。然后，对这40亿个整数进行统计。如果某个值出现了，那么就把这个值对应的bit置位。最后，扫描位图，找到一个没有被置位的bit即可。
方法二：
分段统计。Long long cnt[512M/8=64M]对应数值空间的64M个数据段。每个数据段包含64个不同值，用一个long long作为这个数据段内的位图，位图占64M*8=512M。
这样扫描一遍40亿个整数后，从数组中找到一个计数小于64的元素，然后查看它的位图，找出未出现的元素。
方法二平均性能应该比方法一快，但它占的内存很恐怖。其实，这两种方法都不是很实际，总共1G的内存，算法就消耗512M甚至1G，那剩下的系统程序怎么办？OS都跑不起来了吧。
3 腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。
最简单的想法：直接用STL的set。从某一时刻开始计时，每登陆一个QQ，把它放入set，如果已存则直接打印。直到5min后，就可以over了。下面来简单分析一下算法的复杂度：
空间复杂度：用str存储每个QQ号，假设QQ号有20位，理想情况下每个QQ占20Byte。则5min内的QQ：2w * 60 * 5 = 600w个，需要的存储空间600w * 20byte =12000w byte = 120M，这样的存储应该可以忍受吧。
时间复杂度：STL的set是用二叉树（更确切的说是：红黑树）实现的，查找效率是O( lgn )，应该还是挺快的吧。
呃，有人说不让用STL。那就自己设计一个数据结构呗。该用什么数据结构呢？想了想，还是继续用树，这里用一个trie tree吧。节点内容包括QQ号、指向子节点的指针（这里有10个，认为QQ由0---9的数字组成）。登陆时间要不要？考虑这样一个问题：是否需要把所有的QQ都保存在内存中？随着时间的增加，登陆的QQ会越来越多，比较好的方法是把长时间不登陆的QQ释放掉。所以需要记录登陆时间，以便于释放长期不登陆的QQ。
4 海量日志数据，提取出某日访问百度次数最多的那个IP
海量日志，文件太大，IP地址最多有2^32=4G，无法装入内存，，将这个大文件（hash映射：可以取模00）分成多个小文件（如1000）。
对每个小文件进行hash统计，hash_map(ip,value),得到每个文件出现频率最多的ip
将这些频率最高的ip进行统计，然后排序得出最大值，这里可以采用堆/快速/归并，但只取一个最大值的话可以采用堆排序。
5 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请统计最热门的10个查询串，要求使用的内存不能超过1G。
首先对这1千万个数据进行hash统计，映射成3百万个，每个对应一个频率, O(n)
使用top k算法，遍历这3百万数据，先取前10个数据构成一个小堆（将小的数据都删除掉），后面的元素依次与堆顶元素进行比较，如果大于堆顶元素，替换堆顶元素，重新调整堆，最多n-10次，时间复杂度建堆O（n）+O（nlogn） = O（nlogn）
最终时间复杂度O（nlogn）
6 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
思路：首先要求得每个词的频率，1G无法放入内存，需要分成多个小文件，对每个小文件的词进行统计
顺序读取文件，对每个词，可以hash(x)P00(只要不小于1024个文件，是为了保证每个小文件可以放入内存)， 这样被映射为5000个小文件，每个文件大概200K，每个文件最少1250个单词
对于每个小文件，利用hash_map记录每个单词出现的频率，选出频率最大的100个单词（可以用100个元素的最小堆），再生成对应的5000个文件分别包含这100个单词和频率，这分的文件太多了（关于分多少文件有什么准则吗？， 100*16*5000字节 > 1M, 无法放入内存），
对这5000个小文件进行归并排序，选出最大的100个。
以上也可以将从5000个文件得到的100个数，最后放入100个小文件吧，最后使用100路归并。
7 有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
hash映射这10个文件到另外的10个文件中（hash（query）），这是为了让相同的query放入一个文件中
对每个文件进行hash统计，统计出每个单词的频率，然后按照频率进行排序，使用快速/堆/归并都可以。将每个文件的结果，包含query和频率输出到10个文件中。
对这10个文件进行归并排序。
令因为重复查询比较多，对于所有的查询可以同时放入内存，这样可以将分成的10个文件一次装入内存，进行排序。
8 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
思路：每个文件的大小5G*64 = 32G，远远大于内存，需要对a，b分别分成小文件
利用一个hash(url)00，分别将a，b文件分别映射成1000个小文件，因为通过相同的映射函数，所以对于a，b，相同的url都在对应的文件中，（a0 vs b0, a1 vs b1等等）
分别比对这1000个对应的小文件，可以通过先将a映射到一个hash表中，然后依次遍历b，判断是否在a中出现，出现过则说明重复
9 在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
思路1：总共大小2.5*10^8*4字节=1G
将这么多整数先hash(val)00分成1000个小文件，相同的数就在相同的文件中
对每个小文件进行hash映射，统计出现次数，然后将对应次数为1的输出。
思路2：采用2-Bitmap(每个数分配2bit, 00表示不存在，01表示出现多次，11无意义)，所有的整数总共需内存2^32次方，2^32 * 2 bit = 1G内存，如果可以存入内存，首先全部置为0，依次遍历这2.5亿个整数，如果bitmap中是00则变01，01变10， 10保持不变，把01对应的数输出即可。
10 腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
思路1：同样采用位图，40亿个不重复的数，每个数用1bit表示，出现或不出现，40*10^8*1 = 0.5G大小。遍历这40亿个数，如果出现将对应位置为1，对于给定的数直接判断位图中对应的值。
思路2：编程珠玑上的一个思路。将每个整数都看成32位的二进制数，从最高位，依次按位来分，按最高位0，1分成两个文件，每个文件数字个数小于20亿，与所要判断的数的最高为进行比较，从而知道去哪个文件继续比较，然后对于选定的文件再按照次高位比较再分成2个文件，再比较判断数对应的位数，依次循环，直到最后一位，就可以找到或判断没有该数了。时间复杂度O（log2n）,因为每次都将数据减少一半，直到最后一个。
11 怎么在海量数据中找出重复次数最多的一个？
思路：hash分成小文件，分别统计每个小文件数据出现次数，找出出现次数最大的，然后在将每个小文件的最大值进行比较，找到最大值，与上面思路一样的。
12 100w个数中找出最大的100个数。
思路1：最小堆，找最大100个数
思路2：快速排序，每次分割之后只考虑比轴大的一部分（快速选择的思想），直到比轴大的一部分比100多时，采用传统排序，取前100个
思路3：选取前100个元素，排序，然后扫描剩余的元素，与排好序的元素中最小的相比，如果比它大，替换，重排前面，这跟堆排序思路一样。
13 5亿个整数找他们的中位数
思路：遍历这个文件，按照数的大小分别放入不同的文件，例如2^16个区域，每个区域大概9000个数的范围，然后统计每个区域的个数，然后就可以计算中位数落入哪个区域，并且可以计算出中位数是这个区域的第几大数，然后求出这个区域的第k个数就可以了。
分布式：
海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？
分析：思路其实是一样的，这只不过是分不到n台电脑上，首先你不能保证一个元素只出现在一台电脑上，所以需要先通过hash映射，遍历所有的数据，对于第一道题，将所有相同的数据映射到同一台机器上，对于第2个问题，每个电脑上存放不同范围的数据，然后再进行统计，第1道题就可以用前面题的思路，对于找出每台机子的前10个数，然后再统计这些数，找到top10, 第2道题，统计每台机子数的个数，找出中位数所在机子，并计算出中位数是这个机子的第几个就找到了。
总结：这些海量数据处理的题，思路基本差不多，首先是hash映射，成为不同类型的文件,然后hash统计，之后进行排序等等。以下是july总结的，以上也是参考其中博客整理一些思路的产物：
分而治之/hash映射 + hash统计 + 堆/快速/归并排序（频率最高，最大等）；
双层桶划分（中位数， 不重复数）：本质上还是分而治之的思想，重在“分”的技巧上！
适用范围：第k大，中位数，不重复或重复的数字
基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行
Bloom filter/Bitmap（可以用来实现数据字典，进行数据的判重，或者集合求交集，不重复数）；
Trie树（数据量大，重复多，但是数据种类小可以放入内存）/数据库（适用范围：大数据量的增删改查）/倒排索引（适用范围：搜索引擎，关键字查询）；
外排序：大数据排序，去重，外部排序的归并算法，置换选择败者树原理，最优归并数；
分布式处理之Hadoop/Mapreduce：数据量大，但数据种类小可以放入内存，将数据交给不同的机器去处理，数据划分，结果规约。
——END——
推荐阅读：