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

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

可以預(yù)計每個文件安的巨細(xì)為50G×64=320G，遠(yuǎn)遠(yuǎn)大于內(nèi)存限制的4G。所以不行能將其完全加載到內(nèi)存中處理懲罰。思量采納分而治之的要領(lǐng)。

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

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

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

方案2：內(nèi)存映射成BIT最小存儲單位。

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

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

方案1：

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

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

s 對 這10個文件舉辦合并排序（內(nèi)排序與外排序相團(tuán)結(jié)）。

方案2：

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

方案3：

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

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

3. 有一個1G巨細(xì)的一個文件，內(nèi)里每一行是一個詞，詞的巨細(xì)不高出16字節(jié)，內(nèi)存限制巨細(xì)是1M。返回頻數(shù)最高的100個詞。

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

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

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

5. 在2.5億個整數(shù)中找出不反復(fù)的整數(shù)，內(nèi)存不敷以容納這2.5億個整數(shù)。

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

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

6. 海量數(shù)據(jù)漫衍在100臺電腦中，想個步伐高校統(tǒng)計出這批數(shù)據(jù)的TOP10。

方案1：