超大規模數據場景(思路)——面試高頻算法題目

用4KB內存尋找重復元素

從40個億中產生不存在的整數【位】

如果只讓用10MB空間存儲？

初次遍歷

二次遍歷

用2GB內存在20億個整數中查找出現次數最多的數【分塊】

從億萬個URL中查找問題【分塊堆】

40億個非負整數中找出現兩次的數【位不過多個位哈】

對20GB的文件進行排序【分塊+堆】

超大文本中搜索兩個單詞的最短距離

從10億數字中尋找最小的100萬個數字【堆】

在海量數據中，此時普通的數組、鏈表、Hash、樹等等結構有無效了，因為內存空間放不下了。

而常規的遞歸、排序，回溯、貪心和動態規劃等思想也無效了，因為執行都會超時，必須另外想辦法。

這類問題該如何下手呢？這里介紹三種非常典型的思路：

位存儲：使用位存儲最大的好處是占用的空間是簡單存整數的1/8。例如一個40億的整數數組，如果用整數存儲需要16GB左右的空間，而如果使用位存儲，就可以用0.5GB的空間，這樣很多問題就能夠解決了。
分塊：如果文件實在太大，無法在內存中放下，則需要考慮將大文件分成若干小塊，先處理每個塊，最后再逐步得到想要的結果，這種方式也叫做外部排序。這樣需要遍歷全部序列至少兩次，是典型的用時間換空間的方法。
堆：如果在超大數據中找第K大、第K小，K個最大、K個最小，則特別適合使用堆來做。而且將超大數據換成流數據也可以，而且幾乎是唯一的方式。

用4KB內存尋找重復元素

給定一個數組，包含從1到N的整數，N最大為32000，數組可能還有重復值，且N的取值不定，若只有4KB的內存可用，該如何打印數組中所有重復元素。

本身是一道海量數據問題，如果去掉“只有4KB”的要求，我們可以先創建一個大小為N的數組，然后將這些數據放進來，但是整數最大為32000。如果直接采用數組存，則應該需要32000*4B=128KB的空間，而題目有4KB的內存限制，我們就必須先解決該如何存放的問題。

如果只有4KB的空間，那么只能尋址8*4*2^10個比特，這個值比32000要大的，因此我們可以創建32000比特的位向量(比特數組)，其中一個比特位置就代表一個整數。利用這個位向量，就可以遍歷訪問整個數組。如果發現數組元素是v，那么就將位置為v的設置為1，碰到重復元素，就輸出一下。

public class FindDuplicatesIn32000 {public void checkDuplicates(int[] array) {BitSet bs = new BitSet(32000);for (int i = 0; i < array.length; i++) {int num = array[i];int num0 = num - 1;if (bs.get(num0)) {System.out.println(num);} else {bs.set(num0);}}}class BitSet {int[] bitset;public BitSet(int size) {this.bitset = new int[size >> 5];}boolean get(int pos) {int wordNumber = (pos >> 5);//除以32int bitNumber = (pos & 0x1F);//除以32return (bitset[wordNumber] & (1 << bitNumber)) != 0;}void set(int pos) {int wordNumber = (pos >> 5);//除以32int bitNumber = (pos & 0x1F);//除以32bitset[wordNumber] |= 1 << bitNumber;}}
}

從40個億中產生不存在的整數【位】

給定一個輸入文件，包含40億個非負整數，請設計一個算法，產生一個不存在該文件中的整數，假設你有1GB的內存來完成這項任務。

核心點：我們存儲的并不是這40億個數據本身，而是其對應的位置。

如果數據量很大，采用位方式（俗稱位圖）存儲數據是常用的思路，我們可以使用 bit map 的方式來表示數出現的情況。

申請一個長度為 4 294 967 295(500MB*8) 的 bit 類型的數組 bitArr（就是boolean類型），bitArr 上的每個位置只可以表示 0 或1 狀態。8 個bit 為 1B，所以長度為 4 294 967 295 的 bit 類型的數組占用 500MB 空間，這就滿足題目給定的要求了。

遍歷這 40 億個無符號數，遇到所有的數時，就把 bitArr 相應位置的值設置為 1。

遍歷完成后，再依次遍歷 bitArr，看看哪個位置上的值沒被設置為 1，這個數就不在 40 億個數中。

如果只讓用10MB空間存儲？

分塊

初次遍歷

40億個數需要500MB的空間，那如果只有10MB的空間，至少需要50個塊才可以。

一般來說，我們劃分都是使用2的整數倍，因此劃分成64個塊是合理的。

因為一共只有 40 億個數，所以，如果統計落在每一個區間上的數有多少，肯定有至少一個區間上的計數少于67 108 864。利用這一點可以找出其中一個沒出現過的數。

第一次遍歷，先申請長度為 64 的整型數組 countArr[0..63]，countArr[i]用來統計區間 i 上的數有多少。遍歷 40 億個數，根據當前數是多少來決定哪一個區間上的計數增加。

遍歷完 40 億個數之后，遍歷 countArr，必然會有某一個位置上的值（countArr[i]）小于 67 108 864，表示第 i 區間上至少有一個數沒出現過。

二次遍歷

假設找到第 37 區間上的計數小于 67 108 864，那么我們對這40億個數據進行第二次遍歷：

申請長度為 67 108 864 的 bit map，這占用大約 8MB 的空間，記為 bitArr{0..67108863}。
遍歷這 40 億個數，此時的遍歷只關注落在第 37 區間上的數，記為 num（num滿足num/67 108 864==37），其他區間的數全部忽略。
如果步驟 2 的 num 在第 37 區間上，將 bitArr{num - 67108864*37}的值設置為 1，也就是只做第 37 區間上的數的 bitArr 映射。
遍歷完 40 億個數之后，在 bitArr 上必然存在沒被設置成 1 的位置，假設第 i 個位置上的值沒設置成 1，那么 {67 108 864*37+i} 這個數就是一個沒出現過的數。

用2GB內存在20億個整數中查找出現次數最多的數【分塊】

有一個包含 20 億個全是 32 位整數的大文件，在其中找到出現次數最多的數。

分塊

通常的做法是使用哈希表對出現的每一個數做詞頻統計，哈希表的 key 是某一個整數，value 是這個數出現的次數。就本題來說，一共有 20 億個數，哪怕只是一個數出現了 20 億次，用 32 位的整數也可以表示其出現的次數而不會產生溢出，所以哈希表的 key 需要占用 4B，value 也是 4B。那么哈希表的一條記錄（key,value）需要占用 8B，當哈希表記錄數為 2 億個時，需要至少 1.6GB 的內存。

如果 20 億個數中不同的數超過 2 億種，最極端的情況是 20 億個數都不同，那么在哈希表中可能需要產生 20 億條記錄，這樣內存會不夠用，所以一次性用哈希表統計 20 億個數的辦法是有很大風險的。

解決辦法是把包含 20 億個數的大文件用哈希函數分成 16 個小文件，根據哈希函數的性質，同一種數不可能被散列到不同的小文件上，同時每個小文件中不同的數一定不會大于 2 億種，假設哈希函數足夠優秀。然后對每一個小文件用哈希表來統計其中每種數出現的次數，這樣我們就得到了 16 個小文件中各自出現次數最多的數，還有各自的次數統計。接下來只要選出這16 個小文件各自的第一名中誰出現的次數最多即可。

把一個大的集合通過哈希函數分配到多臺機器中，或者分配到多個文件里，這種技巧是處理大數據面試題時最常用的技巧之一。但是到底分配到多少臺機器、分配到多少個文件，在解題時一定要確定下來。可能是在與面試官溝通的過程中由面試官指定，也可能是根據具體的限制來確定，比如本題確定分成 16 個文件，就是根據內存限制 2GB 的條件來確定的。

從億萬個URL中查找問題【分塊堆】

有一個包含 100 億個 URL 的大文件，假設每個 URL 占用 64B，請找出其中所有重復的 URL。

補充問題：某搜索公司一天的用戶搜索詞匯是海量的（百億數據量），請設計一種求出每天熱門 Top 100 詞匯的可行辦法。

解答：原問題的解法使用解決大數據問題的一種常規方法：把大文件通過哈希函數分配到機器，或者通過哈希函數把大文件拆成小文件，一直進行這種劃分，直到劃分的結果滿足資源限制的要求。首先，你要向面試官詢問在資源上的限制有哪些，包括內存、計算時間等要求。在明確了限制要求之后，可以將每條 URL 通過哈希函數分配到若干臺機器或者拆分成若干個小文件，這里的“若干”由具體的資源限制來計算出精確的數量。

例如，將 100 億字節的大文件通過哈希函數分配到 100 臺機器上，然后每一臺機器分別統計分給自己的 URL 中是否有重復的 URL，同時哈希函數的性質決定了同一條 URL 不可能分給不同的機器；或者在單機上將大文件通過哈希函數拆成 1000 個小文件，對每一個小文件再利用哈希表遍歷，找出重復的 URL；還可以在分給機器或拆完文件之后進行排序，排序過后再看是否有重復的 URL 出現。總之，牢記一點，很多大數據問題都離不開分流，要么是用哈希函數把大文件的內容分配給不同的機器，要么是用哈希函數把大文件拆成小文件，然后處理每一個小數量的集合。

補充問題最開始還是用哈希分流的思路來處理，把包含百億數據量的詞匯文件分流到不同的機器上，具體多少臺機器由面試官規定或者由更多的限制來決定。對每一臺機器來說，如果分到的數據量依然很大，比如，內存不夠或存在其他問題，可以再用哈希函數把每臺機器的分流文件拆成更小的文件處理。處理每一個小文件的時候，通過哈希表統計每種詞及其詞頻，哈希表記錄建立完成后，再遍歷哈希表，遍歷哈希表的過程中使用大小為 100 的小根堆來選出每一個小文件的 Top 100（整體未排序的 Top 100）。每一個小文件都有自己詞頻的小根堆（整體未排序的 Top 100），將小根堆里的詞按照詞頻排序，就得到了每個小文件的排序后 Top 100。然后把各個小文件排序后的 Top 100 進行外排序或者繼續利用小根堆，就可以選出每臺機器上的 Top100。不同機器之間的 Top 100 再進行外排序或者繼續利用小根堆，最終求出整個百億數據量中的 Top 100。對于 Top K 的問題，除用哈希函數分流和用哈希表做詞頻統計之外，還經常用堆結構和外排序的手段進行處理。

40億個非負整數中找出現兩次的數【位不過多個位哈】

32 位無符號整數的范圍是 0～4 294 967 295，現在有 40 億個無符號整數，可以使用最多 1GB的內存，找出所有出現了兩次的數。

首先，可以用 bit map 的方式來表示數出現的情況。具體地說，是申請一個長度為4 294 967 295x2 的bit 類型的數組bitArr，用 2 個位置表示一個數出現的詞頻，1B 占用 8 個bit，所以長度為 4 294 967 295x2 的 bit 類型的數組占用 1GB 空間。

遍歷這 40 億個無符號數，如果初次遇到 num，就把bitArr[num*2 + 1]和 bitArr[num*2]設置為 01，如果第二次遇到 num，就把bitArr[num*2+1]和bitArr[num*2]設置為 10，如果第三次遇到 num，就把bitArr[num*2+1]和bitArr[num*2]設置為 11。以后再遇到 num，發現此時 bitArr[num*2+1]和 bitArr[num*2]已經被設置為 11，就不再做任何設置。遍歷完成后，再依次遍歷 bitArr，如果發現bitArr[i*2+1]和bitArr[i*2]設置為 10，那么 i 就是出現了兩次的數。

對20GB的文件進行排序【分塊+堆】

假設你有一個20GB的文件，每行一個字符串，請說明如何對這個文件進行排序？

這里給出大小是20GB，我們只能將文件劃分成一些塊，每塊大小是xMB，x就是可用內存的大小，例如1GB一塊，那我們就可以將文件分為20塊。我們先對每塊進行排序，然后再逐步合并。這時候我們可以使用兩兩歸并，也可以使用堆排序策略將其逐步合并成一個。

超大文本中搜索兩個單詞的最短距離

有個超大文本文件，內部是很多單詞組成的，現在給定兩個單詞，請你找出這兩個單詞在這個文件中的最小距離，也就是像個幾個單詞。有辦法在O(n)時間里完成搜索操作嗎？方法的空間復雜度如何？

最直觀的做法是遍歷數組 words，對于數組中的每個word1，遍歷數組words 找到每個word2并計算距離。該做法在最壞情況下的時間復雜度是 O(n^2)，需要優化。本題我們少不了遍歷一次數組，找到所有word1 和word2出現的位置，但是為了方便比較，我們可以將其放到一個數組里，例如：

listA:{1,2,9,15,25}
listB:{4,10,19}
合并成
list:{1a,2a,4b,9a,10b,15a,19b,25a}

合并成一個之后更方便查找，數字表示出現的位置，后面一個元素表示元素是什么。然后一邊遍歷一邊比較就可以了。

但是對于超大文本，如果文本太大那這個list可能溢出。如果繼續觀察，我們會發現其實不用單獨構造list，從左到右遍歷數組words，當遍歷到 word1時，如果已經遍歷的單詞中存在word2 ，為了計算最短距離，應該取最后一個已經遍歷到的 word2所在的下標，計算和當前下標的距離。同理，當遍歷到word2時，應該取最后一個已經遍歷到的word1所在的下標，計算和當前下標的距離。

基于上述分析，可以遍歷數組一次得到最短距離，將時間復雜度降低到O(n)。用index1和index2分別表示數組words 已經遍歷的單詞中的最后一個word1的下標和最后一個word2的下標，初始時index1 =index2=?1。遍歷數組words，當遇到word2時，執行如下操作：