關(guān)于海量數(shù)據(jù)的面試題

1、首先處理大數(shù)據(jù)的面試題，有些基本概念要清楚：（1）1Gb = 109bytes（1Gb = 10 億字節(jié)）：1Gb = 1024Mb，1Mb = 1024Kb， 1Kb = 1024bytes；基本流程是，分解大問題，解決小問題，從局部最優(yōu)中選擇全局最優(yōu)；（當(dāng)然，如果直接放內(nèi)存里就能解決的話，那就直接想辦法求解，不需要分解了。）分解過程常用方法：hash(x)%m。其中 x 為字符串/url/ip，m 為小問題的數(shù)目，比如把一個(gè)大文件分解為 1000 份，m=1000；解決問題輔助數(shù)據(jù)結(jié)構(gòu)：hash_map，Trie 樹，bit map，二叉排序樹（AVL，SBT，樹）；top K 問題：最大

2、 K 個(gè)用最小堆，最小K 個(gè)用最大堆。（至于為什么？自己在紙上寫個(gè)小栗子，試一下就知道了。）處理大數(shù)據(jù)常用排序：快速排序/堆排序/歸并排序/桶排序下面是幾個(gè)例題（每個(gè)題的解法都不唯一，下面只列出了眾多解法中的一種）：1. 給定 a、b 兩個(gè)文件，各存放 50 億個(gè) url，每個(gè)url 各占 64 字節(jié)，內(nèi)存限制是 4G，讓你找出 a、b 文件共同的url？假如每個(gè) url 大小為 10bytes，那么可以估計(jì)每個(gè)文件的大小為 50G64=320G，遠(yuǎn)遠(yuǎn)大于內(nèi)存限制的 4G，所以不可能將其完全加載到內(nèi)存中處理，可以采用分治的決。來(lái)解Step1：遍歷文件 a，對(duì)每個(gè) url 求取hash(url)

3、%1000，然后根據(jù)所取得的值將url 分到 1000 個(gè)小文件（記為 a0,a1,.,a999 ，每個(gè)小文件約 300M）；別Step2: 遍歷文件 b，采取和 a 相同的方式將url 分別b0,b1,.,b999）；到 1000 個(gè)小文件（記為巧妙之處：這樣處理后，所有可能相同的 url 都被保存在對(duì)應(yīng)的小文件（a0 vs b0, a1 vs b1 ,.,a999 vs b999）中，不對(duì)應(yīng)的小文件不可能有相同的 url。然后只要求出這個(gè)1000 對(duì)小文件中相同的 url 即可。Step3：求每對(duì)小文件 ai 和 bi 中相同的 url 時(shí)，可以把 ai 的 url到hash_sesh_m

4、ap 中。然后遍歷 bi 的每個(gè)url，看其是否在剛才構(gòu)建的 hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。草圖如下（左邊分解 A，右邊分解 B，中間求解相同url）：2. 有一個(gè) 1G 大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過 16 字節(jié)，內(nèi)存限制大小是 1M，要求返回頻數(shù)最高的 100 個(gè)詞。Step1：順序讀文件中，對(duì)于每個(gè)詞 x，取 hash(x)%5000，然后按照該值存到 5000個(gè)小文件（記為 f0 ,f1 ,. ,f4999）中，這樣每個(gè)文件大概是 200k 左右，如果其中的有的文件超過了 1M 大小，還可以按照類似的方法繼續(xù)往下分，直到分解

5、得到的小文件的大小都不超過 1M；Step2：對(duì)每個(gè)小文件，統(tǒng)計(jì)每個(gè)文件中出現(xiàn)的詞以及相應(yīng)的頻率（可以采用 trie 樹/hash_map 等），并取出出現(xiàn)頻率最大的 100 個(gè)詞（可以用含 100 個(gè)結(jié)點(diǎn)的最小堆），并把 100 詞及相應(yīng)的頻率存入文件，這樣又得到了 5000 個(gè)文件；Step3：把這 5000 個(gè)文件進(jìn)行歸并（類似與歸并排序）；草圖如下（分割大問題，求解小問題，歸并）：3. 現(xiàn)有海量日志數(shù)據(jù)保存在一個(gè)超級(jí)大的文件中，該文件無(wú)法直接讀入內(nèi)存，要求從中提次數(shù)最多的那個(gè)IP。取某天出Step1：從這一天的日志數(shù)據(jù)中把的IP 取出來(lái)，逐個(gè)寫入到一個(gè)大文件中；Step2：注意到 IP 是 32 位的，最多有 232 個(gè) IP。同樣可以采用的方法，比如模1000，把整個(gè)大文件為 1000 個(gè)小文件；Step3：找出每個(gè)小文中出現(xiàn)頻率最大的 IP（可以采用