海量日志数据，提取出某日访问百度次数最多的那个IP。
IP地址是32位的二进制数,所以共有N=2^32=4G个不同的IP地址, 创建一个unsigned count[N]的数组,
即可统计出每个IP的访问次数,而sizeof(count) == 4G*4byte=16G, 远远超过了32位计算机所支持的内存大小,
因此不能直接创建这个数组.
下面采用划分法解决这个问题.
假设允许使用的内存是512M,512M/4byte=128M,子问题大小为128M，即512M内存可以统计128M个不同的IP地址的访问次数.
而N/128M = 4G/128M = 32 ,所以只要把IP地址划分成32个不同的区间,分别统计出每个区间中访问次数最大的IP,
然后就可以计算出所有IP地址中访问次数最大的IP了.
因为2^5=32, 所以可以把IP地址的最高5位作为区间编号, 剩下的27为作为区间内的值,
建立32个临时文件,代表32个区间,把相同区间的IP地址保存到同一的临时文件中.
如果某个区间大于内存，就继续分割。
Top K. 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
依然是先将大文件散列成小文件(小文件大于内存就继续分割)，每个小文件用hash统计词频。
然后每个小文件可以用各种方法求TopK词频的记录。
如果用最小堆，可以先假设小文件的记录中的前K个记录为TopK，将这K个记录建立最小堆，堆顶就是目前第K多的记录；
然后每次来一个新的记录，和堆顶比较，如果大于堆顶，则替换堆顶，并维护最小堆。
然后在对所有小文件的TopK记录归并。
下面是大堆的代码，小堆类似
# 大堆：A[parent(i)]>=A[i]，小堆相反，堆排序中使用大堆
# 维护一个大堆。假设A[i]的两个子树都已经是大堆，但A[i]可能较小。
# 此方法让A[i]在堆中逐层下降。A[i]下降后，以其为根的堆可能不是大堆，需递归调用此方法，复杂度lgn.
# assume that 2 subtrees of A[i] are already maxheap
def max_heapify(A, i, size):
l = left(i)
r = right(i)
largest = i
if l < size and A[l] > A[largest]:
largest = l
if r < size and A[r] > A[largest]:
largest = r
if largest != i:
tmp = A[largest]
A[largest] = A[i]
A[i] = tmp
max_heapify(A, largest, size)
# 把任意数组变成一个大堆。
# 数组A的n/2+1到n为树的叶子节点，可以看成大堆，对非叶子节点自底向上的调用max_heapify()。线性时间
def build_max_heap(A):
# from bottom to top
for i in range(0, len(A) / 2 + 1)[::-1]:
max_heapify(A, i, len(A))
给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M。
遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行， 共需内存2^32 * 2 bit=1 GB内存，还可以接受。
可以用一个long数组，一个long64位，可以表示32个数，数组的长度为2^32/32=2^27。比如，0占据数组第一个元素的前两位，1占据数组第一个元素的3、4位….
然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。 所描完事后，查看bitmap，把对应位是01的整数输出即可。
