挺有意思的題目。
1. 給你A,B兩個文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4G，讓你找出:A,B文件共同的URL。 解法一：Hash成內(nèi)存大小的小塊文件，然后分塊內(nèi)存內(nèi)查交集。
解法二：Bloom Filter（廣泛應(yīng)用于URL過濾、查重。參考http://en.wikipedia.org/wiki/Bloom_filter、http://blog.csdn.net/jiaomeng/archive/2007/01/28/1496329.aspx）
2. 有10個文件，每個文件1G， 每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復(fù)。要你按照query的頻度排序。解法一：根據(jù)數(shù)據(jù)稀疏程度算法會有不同，通用方法是用Hash把文件重排，讓相同query一定會在同一個文件，同時進行計數(shù)，然后歸并，用最小堆來統(tǒng)計頻度最大的。
解法二：類似1，但是用的是與簡單Bloom Filter稍有不同的CBF（Counting Bloom Filter）或者更進一步的SBF（Spectral Bloom Filter，參考http://blog.csdn.net/jiaomeng/archive/2007/03/19/1534238.aspx）
解法三：MapReduce，幾分鐘可以在hadoop集群上搞定。參考http://en.wikipedia.org/wiki/MapReduce
3. 有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16個字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。解法一：跟2類似，只是不需要排序，各個文件分別統(tǒng)計前100，然后一起找前100。