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

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

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

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

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

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

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

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

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

方案1：

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

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

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

方案2：

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

方案3：

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

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

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

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

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

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

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

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

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

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

方案1：