中國IDC圈6月3日報道，1. 給定a、b兩個文件，各存放50億個url，每個url各占64字節，內存限制是4G，讓你找出a、b文件配合的url？

方案1：將大文件分成可以或許被內存加載的小文件。

可以預計每個文件安的巨細為50G×64=320G，遠遠大于內存限制的4G。所以不行能將其完全加載到內存中處理懲罰。思量采納分而治之的要領。

s 遍歷文件a，對每個url求取 ，然后按照所取得的值將url別離存儲到1000個小文件（記為 ）中。這樣每個小文件的約莫為300M。

s 遍歷文件b，采納和a溝通的方法將url別離存儲到1000各小文件（記為 ）。這樣處理懲罰后，所有大概溝通的url都在對應的小文件（ ）中，差池應的小文件不行能有溝通的url。然后我們只要求出1000對小文件中溝通的url即可。

s 求每對小文件中溝通的url時，可以把個中一個小文件的url存儲到hash_set中。然后遍歷另一個小文件的每個url，看其是否在適才構建的hash_set中，假如是，那么就是配合的url，存到文件內里就可以了。

方案2：內存映射成BIT最小存儲單位。

假如答允有必然的錯誤率，可以利用Bloom filter，4G內存或許可以暗示340億bit。將個中一個文件中的url利用Bloom filter映射為這340億bit，然后挨個讀取別的一個文件的url，查抄是否與Bloom filter，假如是，那么該url應該是配合的url（注領悟有必然的錯誤率）。

2. 有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都大概反復。要求你憑據query的頻度排序。

方案1：

s 順序讀取10個文件，憑據hash(query)%10的功效將query寫入到別的10個文件（記為 ）中。這樣新生成的文件每個的巨細約莫也1G（假設hash函數是隨機的）。

s 找一臺內存在2G閣下的呆板，依次對 用hash_map(query, query_count)來統計每個query呈現的次數。操作快速/堆/合并排序憑據呈現次數舉辦排序。將排序好的query和對應的query_cout輸出到文件中。這樣獲得了10個排好序的文件（記為 ）。

s 對 這10個文件舉辦合并排序（內排序與外排序相團結）。

方案2：

一般query的總量是有限的，只是反復的次數較量多罷了，大概對付所有的query，一次性就可以插手到內存了。這樣，我們就可以回收trie樹/hash_map等直接來統計每個query呈現的次數，然后按呈現次數做快速/堆/合并排序就可以了。

方案3：

與方案1雷同，但在做完hash，分成多個文件后，可以交給多個文件來處理懲罰，回收漫衍式的架構來處理懲罰（好比MapReduce），最后再舉辦歸并。

//一般在大文件中找出呈現頻率高的，先把大文件映射成小文件，模1000，在小文件中找到高頻的。

3. 有一個1G巨細的一個文件，內里每一行是一個詞，詞的巨細不高出16字節，內存限制巨細是1M。返回頻數最高的100個詞。

方案1：順序讀文件中，對付每個詞x，取 ，然后憑據該值存到5000個小文件（記為 ）中。這樣每個文件或許是200k閣下。假如個中的有的文件高出了1M巨細，還可以憑據雷同的要領繼承往下分，知道解析獲得的小文件的巨細都不高出1M。對每個小文件，統計每個文件中呈現的詞以及相應的頻率（可以回收trie樹/hash_map等），并取出呈現頻率最大的100個詞（可以用含100個結點的最小堆），并把100詞及相應的頻率存入文件，這樣又獲得了5000個文件。下一步就是把這5000個文件舉辦合并（雷同與合并排序）的進程了。

4. 海量日志數據，提取出某日會見百度次數最多的誰人IP。

方案1：首先是這一天，而且是會見百度的日志中的IP取出來，逐個寫入到一個大文件中。留意到IP是32位的，最多有 個IP。同樣可以回收映射的要領，好比模1000，把整個大文件映射為1000個小文件，再找出每個小文中呈現頻率最大的IP（可以回收hash_map舉辦頻率統計，然后再找出頻率最大的幾個）及相應的頻率。然后再在這1000個最大的IP中，找出誰人頻率最大的IP，即為所求。

5. 在2.5億個整數中找出不反復的整數，內存不敷以容納這2.5億個整數。

方案1：回收2-Bitmap（每個數分派2bit，00暗示不存在，01暗示呈現一次，10暗示多次，11無意義）舉辦，共需內存 內存，還可以接管。然后掃描這2.5億個整數，查察Bitmap中相對應位，假如是00變01，01變10，10保持穩定。所描完過后，查察bitmap，把對應位是01的整數輸出即可。

方案2：也可回收上題雷同的要領，舉辦分別小文件的要領。然后在小文件中找出不反復的整數，并排序。然后再舉辦合并，留意去除反復的元素。

6. 海量數據漫衍在100臺電腦中，想個步伐高校統計出這批數據的TOP10。

方案1：