這些海量數(shù)據(jù)類題,面試出現(xiàn)率極高,請收藏!
近期看到群里有小伙伴面試遇到了大數(shù)據(jù)類的題目，這類題目也是面試中比較高頻的，今天給大家整理了一些海量數(shù)據(jù)類的超高頻面試題目。
由于篇幅有限，這里選取6個為例，給大家分享一下。
更全面的海量數(shù)據(jù)類超高頻面試問題和答案
在下方【代碼界的小白】公眾號卡片回復(fù)：海量數(shù)據(jù)，即可獲取10+頁的PDF。
什么是海量數(shù)據(jù)?
所謂海量數(shù)據(jù)處理，就是指數(shù)據(jù)量太大，無法在較短時間內(nèi)迅速解決，或者無法一次性裝入內(nèi)存。
而解決方案就是：
- 針對時間，可以采用巧妙的算法搭配合適的數(shù)據(jù)結(jié)構(gòu)，如 Bloom filter/Hashmap/bit-map/堆/數(shù)據(jù)庫/倒排索引/Trie樹；
- 針對空間，大而化小，分而治之（hash映射），把規(guī)模大化為規(guī)模小的，各個擊破。
[海量數(shù)據(jù)]處理的基本方法總結(jié)起來分為以下幾種：
- 分而治之/hash映射 + hash統(tǒng)計 + 堆/快速/歸并排序；
- Trie樹/Bloom filter/Bitmap
- 數(shù)據(jù)庫/倒排索引；
- 雙層桶劃分；
- 外排序；
- 分布式處理之Hadoop/Mapreduce
1、海量日志數(shù)據(jù)，統(tǒng)計出某日訪問[百度]次數(shù)最多的那個IP
解決方式：IP地址最多有 2^32 = 4G 種取值情況，所以不能完全加載到內(nèi)存中進(jìn)行處理，采用 hash分解+ 分而治之 + 歸并的方式：
（1）按照 IP 地址的 Hash(IP)%1024 值，把海量IP日志分別存儲到1024個小文件中。這樣，每個小文件最多包含4MB個IP地址；
（2）對于每一個小文件，構(gòu)建一個IP為key，出現(xiàn)次數(shù)為value的Hash map，同時記錄當(dāng)前出現(xiàn)次數(shù)最多的那個IP地址
（3）然后再在這1024組最大的IP中，找出那個頻率最大的IP
2、有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。
解決思想：hash分解+ 分而治之 + 歸并
（1）順序讀文件中，對于每個詞x，按照 hash(x)/(1024*4) 存到4096個小文件中。這樣每個文件大概是250k左右。如果其中有的文件超過了1M大小，還可以按照hash繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M。
（2）對每個小文件，可以采用 trie樹/hashmap 統(tǒng)計每個文件中出現(xiàn)的詞以及相應(yīng)的頻率，并使用 100個節(jié)點(diǎn)的小頂堆取出出現(xiàn)頻率最大的100個詞，并把100個詞及相應(yīng)的頻率存入文件。這樣又得到了4096個文件。
（3）下一步就是把這4096個文件進(jìn)行歸并的過程了
3、有a、b兩個文件，各存放50億個url，每個url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？
解決方案1：hash 分解+ 分而治之 + 歸并 的方式：
如果內(nèi)存中想要存入所有的 url，共需要 50億 * 64= 320G大小空間，所以采用 hash 分解+ 分而治之 + 歸并 的方式：
（1）遍歷文件a，對每個 url 根據(jù)某種hash規(guī)則，求取hash(url)/1024，然后根據(jù)所取得的值將 url 分別存儲到1024個小文件（a0~a1023）中。這樣每個小文件的大約為300M。如果hash結(jié)果很集中使得某個文件ai過大，可以再對ai進(jìn)行二級hash(ai0~ai1024)，這樣 url 就被hash到 1024 個不同級別的文件中。
（2）分別比較文件，a0 VS b0，…… ，a1023 VS b1023，求每對小文件中相同的url時：把其中一個小文件的 url 存儲到 hashmap 中，然后遍歷另一個小文件的每個url，看其是否在剛才構(gòu)建的 hashmap 中，如果是，那么就是共同的url，存到文件中。
（3）把1024個文件中的相同 url 合并起來
解決方案2：Bloom filter
如果允許有一定的錯誤率，可以使用 Bloom filter。
4G內(nèi)存大概可以表示 340 億bit，n = 50億。
如果按照出錯率0.01算需要的大概是650億個bit，現(xiàn)在可用的是340億，相差并不多，這樣可能會使出錯率上升些。
將其中一個文件中的 url 使用 Bloom filter 映射為這340億bit
然后挨個讀取另外一個文件的url，檢查是否與Bloom filter，如果是，那么該url應(yīng)該是共同的url（注意會有一定的錯誤率）
4、有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的 query，每個文件的query都可能重復(fù)。要求你按照query的頻度[排序]
解決方案1：hash分解+ 分而治之 +歸并
（1）順序讀取10個文件 a0~a9，按照 hash(query)%10 的結(jié)果將 query 寫入到另外10個文件（記為 b0~b9）中，這樣新生成的文件每個的大小大約也1G
（2）找一臺內(nèi)存2G左右的機(jī)器，依次使用 hashmap(query, query_count) 來統(tǒng)計每個 query 出現(xiàn)的次數(shù)。利用 快速/堆/歸并排序 按照出現(xiàn)次數(shù)進(jìn)行排序。將排序好的query和對應(yīng)的query_cout輸出到文件中。這樣得到了10個排好序的文件c0~c9。
（3）對這10個文件 c0~c9 進(jìn)行歸并排序（內(nèi)排序與外排序相結(jié)合）。每次取 c0~c9 文件的 m 個數(shù)據(jù)放到內(nèi)存中，進(jìn)行 10m 個數(shù)據(jù)的歸并，即使把歸并好的數(shù)據(jù)存到 d結(jié)果文件中。如果 ci 對應(yīng)的m個數(shù)據(jù)全歸并完了，再從 ci 余下的數(shù)據(jù)中取m個數(shù)據(jù)重新加載到內(nèi)存中。直到所有ci文件的所有數(shù)據(jù)全部歸并完成。
解決方案2：Trie樹
如果query的總量是有限的，只是重復(fù)的次數(shù)比較多而已。
可能對于所有的query，一次性就可以加入到內(nèi)存了。
在這種情況下，可以采用 trie樹/hashmap 等直接來統(tǒng)計每個query出現(xiàn)的次數(shù)，
然后按出現(xiàn)次數(shù)做快速/堆/歸并排序就可以了。
5、在 2.5 億個整數(shù)中找出不重復(fù)的整數(shù)，內(nèi)存不足以容納這2.5億個整數(shù)。
解決方案1：hash 分解+ 分而治之 + 歸并
（1）2.5億個 int 類型 hash 到1024個小文件中 a0~a1023，如果某個小文件大小還大于內(nèi)存，進(jìn)行多級hash
（2）將每個小文件讀進(jìn)內(nèi)存，找出只出現(xiàn)一次的數(shù)據(jù)，輸出到b0~b1023
（3）最后數(shù)據(jù)合并即可
解決方案2 ：2-Bitmap
如果內(nèi)存夠1GB的話，采用 2-Bitmap 進(jìn)行統(tǒng)計，共需內(nèi)存 2^32 * 2bit = 1GB內(nèi)存。
2-bitmap 中，每個數(shù)分配 2bit（00表示不存在，01表示出現(xiàn)一次，10表示多次，11無意義）
然后掃描這 2.5 億個整數(shù)，查看Bitmap中相對應(yīng)位，如果是00，則將其置為01；如果是01，將其置為10；如果是10，則保持不變。
掃描完成后，查看Bitmap，把對應(yīng)位是01的整數(shù)輸出即可。（如果是找出重復(fù)的數(shù)據(jù)，可以用1-bitmap。第一次bit位由0變1，第二次查詢到相應(yīng)bit位為1說明是重復(fù)數(shù)據(jù)，輸出即可）
6、現(xiàn)有兩個各有20億行的文件，每一行都只有一個數(shù)字，求這兩個文件的交集。
解決方案：采用 bitmap 進(jìn)行問題解決，int 的[最大數(shù)]是 2^32 = 4G。
用一個二進(jìn)制的下標(biāo)來表示一個 int 值，大概需要4G個bit位，即約4G/8 = 512M的內(nèi)存，就可以解決問題了。
① 首先遍歷文件，將每個文件按照數(shù)字的正數(shù)，負(fù)數(shù)標(biāo)記到2個 bitmap 上，為：正數(shù) bitmapA_positive，負(fù)數(shù) bitmapA_negative
② 遍歷另為一個文件，生成正數(shù)：bitmapB_positive，bitmapB_negative
③ 取 bitmapA_positive and bitmapB_positive 得到2個文件的正數(shù)的交集，同理得到負(fù)數(shù)的交集。
④ 合并，問題解決
這里一次只能解決全正數(shù)，或全負(fù)數(shù)，所以要分兩次
其他
另外還沒有下載Java面試超高頻問題和答案的朋友，可以通過以下兩個途徑領(lǐng)取了！
獲取《Java面試必知必會》方法
- 1、點(diǎn)擊閱讀原文可以進(jìn)入到gitee下載《Java面試必知必會》1.0版本
- 2、點(diǎn)擊下方卡片回復(fù)：Java面試必知必會