1. 現有海量日志數據保存在一個超級大的文件中，該文件無法直接讀入內存，要求從中提取某天出訪問百度次數最多的那個IP。

• 從這一天的日志數據中把訪問百度的IP取出來，逐個寫入到一個大文件中;
• 注意到IP是32位的，最多有2^32個IP。同樣可以采用映射的方法，比如模1000，把整個大文件映射為1000個小文件;
• 找出每個小文中出現頻率最大的IP(可以采用hash_map進行頻率統計，然后再找出頻率最大的幾個)及相應的頻率;
• 在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。

2. 給定a、b兩個文件，各存放50億個url，每個url各占用64字節，內存限制是4G，如何找出a、b文件共同的url？

假如每個url大小為10bytes，那么可以估計每個文件的大小為50G×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即可。
• 求每對小文件ai和bi中相同的url時，可以把ai的url存儲到hash_set/hash_map中。然后遍歷bi的每個url，看其是否在剛才構建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

3、有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。

• 算法思想： 分而治之 + hash統計 + 堆/快速排序

• 分而治之/hash映射：順序讀文件中，對于每個詞x，取hash(x)%5000，然后按照該值存到5000個小文件（記為x0,x1,…x4999）中。這樣每個文件大概是200k左右。如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續往下分，直到分解得到的小文件的大小都不超過1M。
• hash_map統計：對每個小文件，采用trie樹/hash_map等統計每個文件中出現的詞以及相應的頻率。
• 堆/歸并排序：取出出現頻率最大的100個詞（可以用含100個結點的最小堆）后，再把100個詞及相應的頻率存入文件，這樣又得到了5000個文件。最后就是把這5000個文件進行歸并（類似于歸并排序）的過程了。

參考資料