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