常見大數(shù)據(jù)和空間面試題

Hydrogen 發(fā)布于2019-08-15 18:04 / 2449人閱讀

摘要：答案使用，申請一個長度為類型的，每個位置只表示或，該數(shù)組占用空間約。遍歷億個數(shù)，當(dāng)前數(shù)為，落在區(qū)間，對應(yīng)。

過濾100億黑名單 題目

假設(shè)有100億個URL的黑名單，每個URL最多占用64B，設(shè)計一個過濾系統(tǒng)，判斷某條URL是否在黑名單里。

要求

不高于萬分之一的判斷失誤率；額外內(nèi)存不超過30GB

答案

100億個64B的URL需要640GB的內(nèi)存，顯然直接存哈希表不合理。考慮布隆過濾器，假設(shè)有一個長度為m的bit類型數(shù)組，如圖所示：

輸入階段：

有k個哈希函數(shù)，函數(shù)的輸出域S大于或等于m，假設(shè)哈希函數(shù)彼此獨(dú)立，對于同一個輸入(以字符串表示的URL)，經(jīng)過k個哈希函數(shù)的計算結(jié)果也是相互獨(dú)立。對計算的每一個結(jié)果Mod m，將bit array上對應(yīng)的位置置1，如下：

一個輸入對象會將bitmap某些位置涂黑，處理完所有輸入對象，會將bitmap相當(dāng)多位置涂黑，至此，布隆過濾器生成完畢，代表之前所有輸入對象的集合。

20億個數(shù)中出現(xiàn)最多的數(shù) 問題

包含20億個全是32位整數(shù)的大文件，在其中找出出現(xiàn)次數(shù)最多的數(shù)。

要求

內(nèi)存限制：2GB

答案

將20億個數(shù)用hash函數(shù)分成16個文件。然后統(tǒng)計每個小文件中，哪個數(shù)字出現(xiàn)次數(shù)最多。最后再比較每個小文件的次數(shù)最多的數(shù)。（本題分成16個也是根據(jù)題目來的。考慮最極端情況。20億個數(shù)都不同）32位的整數(shù)要占4b,key占4b，value占4b。共8b。內(nèi)存只有2G。所以大概每個小文件存2億條。就需要10個小文件。但是hash函數(shù)必須2的n次方。所以2的4次方。16個

40億個數(shù)找沒出現(xiàn)的數(shù) 問題

有一個包含40億個無符號整數(shù)的文件，最多使用1GB內(nèi)存，找到所有沒出現(xiàn)的數(shù)

分析

最差情況，40億個數(shù)都不同，哈希表保存出現(xiàn)過的數(shù)，需要內(nèi)存4B*40億，大約16GB內(nèi)存。

答案

使用bitmap，申請一個長度為4294967295bit類型的bitArray，每個位置只表示0或1，該數(shù)組占用空間約500MB。遍歷這20億個數(shù)，例如遇到7000，就將bitArray[7000]置1。遍歷完成后，再依次遍歷bitArray，哪個位置沒有置1，哪個數(shù)就不在40億個數(shù)中。

40億個數(shù)找第一個沒出現(xiàn)的數(shù) 。內(nèi)存只有10M 答案

具體的，第一次遍歷，申請長度64的整形數(shù)組countArr[0...63]，統(tǒng)計每個區(qū)間計數(shù)增加。例如，當(dāng)前數(shù)是34225522090，34225522090/67108864=51，countArr[51]++。遍歷完之后，必定有一個countArr[i]小于67108864，表示i區(qū)間內(nèi)至少有一個數(shù)沒出現(xiàn)過。此時countArr[]使用的內(nèi)存是64*4B。

假設(shè)在37區(qū)間有一個數(shù)沒出現(xiàn)，申請一個長度為67108864的bitmap，內(nèi)存大約8MB，記為bitArr[0~67108863]。再一次遍歷40億個數(shù)，只關(guān)心37區(qū)間的數(shù)，記為num。將bitAry[num-6710886437]的值置位1。遍歷完之后，bitArr必然有沒有置1的位置，記為i，則6710886437+i就是沒出現(xiàn)過的數(shù)。

找出100億個重復(fù)URL以及搜索詞匯topK問題 問題

有一個包含100億URL的大文件，每個URL占64B，找出重復(fù)URL；補(bǔ)充，找出top100搜索詞匯

常規(guī)答案

大文件通過哈希函數(shù)分配到不同機(jī)器

哈希函數(shù)將大文件拆分成小文件。

對于每一個小文件，利用哈希表遍歷，找出重復(fù)的URL，或者分給機(jī)器或拆分文件完之后，進(jìn)行排序，看是否有重復(fù)的URL。

補(bǔ)充問題的思路也是通過哈希函數(shù)分流，對于每個小文件，簡歷詞頻哈希表，建一個大小為100的小根堆，選出每個小文件的top100.每個小文件的top100進(jìn)行外排序或者接著使用小根堆，就能得到100億數(shù)據(jù)的top100.

出現(xiàn)兩次的數(shù)以及中位數(shù)問題 問題

有40億個無符號32位整數(shù)，最多可以使用1GB內(nèi)存，找出所有出現(xiàn)了兩次的數(shù)；補(bǔ)充問題，最多使用10MB內(nèi)存，找到40億個數(shù)的中位數(shù)

答案

第一個問題可以用bitmap做，申請長度為2?232bit的bitArr，2個bit表示一個數(shù)出現(xiàn)的詞頻。遍歷40億個數(shù)，假設(shè)出現(xiàn)num，將bitArr[2num]和bitArr[2num+1]設(shè)置為01，第二次出現(xiàn)，設(shè)置為10，第三次，設(shè)置為11。以后再遇到11的，就不做處理。遍歷完成后，再遍歷一次，若發(fā)現(xiàn)bitArr[2num]和bitArr[2num+1]是10，則num是出現(xiàn)了兩次的數(shù)。

第二個問題，分區(qū)間討論。長度為2MB的unsigned int數(shù)組占用8MB，將區(qū)間數(shù)目定位232/2M，取整為2148個區(qū)間，第0區(qū)間0~2M-1，第i區(qū)間2Mi~2M（i+1）-1

申請一個長度為2148的unsigned int整數(shù)數(shù)組arr[0..2147],arr[i]表示i區(qū)間有多少個數(shù)，arr占用內(nèi)存小于10MB。遍歷40億個數(shù)，當(dāng)前數(shù)num為num，落在區(qū)間(num/2M)，對應(yīng)arr[num/2M]++。累加統(tǒng)計每個區(qū)間的累計數(shù)目，就能找到40億個數(shù)的中位數(shù)。例如0~K-1區(qū)間數(shù)目個數(shù)為19.998億，加上第K個區(qū)間就超過了20億，說要中位數(shù)一定在K區(qū)間中，并且一定是第K區(qū)間的第0.002億個數(shù)。

接著申請長度2M的unsigned int數(shù)組countArr[0..2M-1]，占用8MB。遍歷40億個數(shù)，只關(guān)心第K區(qū)間的數(shù)numi，countArr[numi-K*2M]++。統(tǒng)計完之后在第K區(qū)間找地0.002億個數(shù)字即可。

一致性哈希

分布式數(shù)據(jù)庫集群緩存，例如memcached，將數(shù)據(jù)的id通過哈希函數(shù)轉(zhuǎn)換為key，假設(shè)有N個機(jī)器，計算key%N，得到及其所屬編號，增刪改查都在這臺機(jī)器上。一致性哈希能在機(jī)器擴(kuò)容（N發(fā)生變化），使得不用重新計算一遍key%N

三臺機(jī)器處于哈希環(huán)，id通過哈希映射為key，在哈希環(huán)中順時針找距離最近的機(jī)器。

機(jī)器較少的時候可能會出現(xiàn)負(fù)載不均衡，如圖所示：

答案

引入虛擬節(jié)點(diǎn)，增加結(jié)點(diǎn)數(shù)