第一部分：海量数据处理
1.寻找热门查询：
解：
step1 建立hash table：
首先对含有一千万个query的日志文件进行遍历，建立hash
table，key是查询串，H(key)是它被查询的次数，遍历时，如果key在hash
table中已存在，则令H(key)++;若不存在，则将key加入hash table，并令H(key)=1。这样建立的hash
table不超过三百万个记录，1G的内存是足够了的。时间复杂度是O（N1），其中N1为一千万。
Step2 对建好的hash table排序（部分排序）：
方法一：初始化一个可以存放K=10个记录的数组，将hash
table的前K个记录赋给数组，并从大到小进行排序，时间复杂度是O(KlogK)，再读取hash
table剩下的N-K个记录的第一个，与数组的最后一个值进行比较，如果比它小，则继续读取hash
table的下一个记录，如果比数组的最后一个值大，则将数组的最后一个记录删除，将它插入使插入后的数组依然从大到小有序，时间复杂度是O(k)，然后继续读取hash
table的下一个记录，重复上面的步骤直到hash
table剩下的N-K个记录读完。因此step2的时间复杂度是O(N2*K),其中N2为三百万。
方法二：读取hash table的前K个记录建最小堆，时间复杂度是O(K），再依次读取hash
table剩下的N-K条记录，每读取一条，将它与堆顶元素（即当前最小值）进行比较，若比它小，则继续读取hash
table的下一条记录，否则对堆进行一次维护，将这条记录替代掉原先的堆顶元素，然后调整使之重新形成一个堆，其时间复杂度为O(logK)，因此，直到hash
table读完，总时间复杂度为O(N2*logK)。
显然方法二优于方法一。
方法三：当K比较小的时候，直接对整个hash
table建立最大堆，O(N2),堆顶元素即为最热门查询串，再以堆中最后一个元素替代之，再调整使之形成新的堆，O(logN2)，如此可以获得排行第二热门的查询串，重复上述步骤，直到获得最热门的十个查询串。时间复杂度是O(N2)+O(K*logN2)。
因此，整个程序的时间复杂度为O(N1)+O(N2*logK)。
或O(N1)+O(N2)+O(K*logN2)。
2.海量日志数据，提取出某日访问百度次数最多的那个IP。
解：注意到IP是32位的，因此至多有2^32个IP，海量日志数据至多为2^32*4B，首先利用映射,H(key)=keyP00,如此将海量日志数据分配到5000个小文件中，然后对每个小文件进行统计，找寻次数最多的IP，和它的频度,再找这5000个IP中频度最大的IP即为所求。
3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
解：step1:分而治之/hash映射：首先用Hash(key) 00将这个文件中的词分配到2000个小文件中.
Step2:hash统计：统计每个小文件中的出现的词和它出现的频率。
Step3：堆/归并排序：再找寻每个小文件中频度最高的100个词，（可以建立大小为100最小堆，将之后的元素与堆顶元素比较，若比它小，则继续下一个与堆顶元素比较，否则，替代堆顶元素，更新堆），再对这2000个小文件的频度最高100词进行归并。
4.海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
解： 此题与上面第3题类似
若不同电脑中的数据没有重复：
堆排序：在每台电脑上求出TOP10，可以采用包含10个元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆）。比如求TOP10大，我们首先取前10个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP10大。
求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。
若不同电脑中的数据有重复：
对每个电脑中的数据做hash映射，hash(key)=key0,利用hash（key)的值将数据重新分配到100台电脑中，如此保证相同的数据必定位于同一台电脑中。
5、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
解：step1.对每个文件中的query 取hash(query
)0,将这10个文件中的数据重新分配到100个小文件中.
Ste2.hash统计，统计每个出现的用户query和它的频度。
Step3.对这100个文件每个文件对频度次数进行堆排序.
Step4.将排好序的100个文件进行归并排序。
6、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
7、怎么在海量数据中找出重复次数最多的一个？
8、上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。
9、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
解：step1.hash统计，统计每个出现的词及它的频度，O(N),N=10000.
Step2.对这个文本文件的前10个H（key)建立大小为10的最小堆...与问题1类似。O(N*log10).
10、腾讯笔试题：在一个文件中有
10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。
解：不妨设这10G个整数都是64位的，即每个整数占8字节。2G=2*2^10*2^10*2^10字节，因此2G内存可以存放256M个整数。
首先建立hash
table。将这个文件分割成m个大小小于2G的文件。当key属于区间Ki时，hash(key)=i；i=0...m-1；然后在遍历每个文件做统计，得到m个key
的范围和这个范围内key的个数。如此便可锁定中位数所在的区间并由此锁定它所在的文件。例如有500个key位于[0,300],800个key位于[300,700],400个key位于[700,1000]，则中位数是所有数排好序后的第850个数和第851个数之和除以2，显然第850大数和第851大数位于[300,700]，由于[0,300]有500个数，因此中位数是第二个文件中也就是[300,700]中第350大数和第351大数，于是对这个文件中的数进行堆排序，可建立大小为351的最小堆，然后将元素与堆顶比较，若比堆顶小，则到下一个否则替代，更新堆。如此得到前351大的数，其中第350和351的数即为所求。也可以类似的，可以继续对第二个文件做分割，然后锁定中位数的范围，直到这个范围缩小到足够小，然后再对这个范围内的数进行排序，如此便可减少内部排序的规模。