1、給定 a、b 兩個檔案，各存放 50 億個 url，每個 url 各佔 64 位元組，記憶體限制是 4G，讓你找出 a、b 檔案共同的 url？
1) 可以估計每個檔案安的大小為 50G×64=320G，遠遠大於記憶體限制的 4G。所以不可能將其完全載入到記憶體中處理。考慮採取 分而治之 的方法。
2) 遍歷檔案 a，對每個 url 求取 ，然後根據所取得的值將 url 分別儲存到 1000 個小檔案（記為 ）中。這樣每個小檔案的大約為 300M。
3) 遍歷檔案 b，採取和 a 相同的方式將 url 分別儲存到 1000 個小檔案（記為 ）。這樣處理後，所有可能相同的 url 都在對應的小檔案（ ）中，不對應的小檔案不可能有相同的 url。然後我們只要求出 1000 對小檔案中相同的 url 即可
4) 求每對小檔案中相同的 url 時，可以把其中一個小檔案的 url 儲存到 hash_set 中。然後遍歷另一個小檔案的每個 url，看其是否在剛才構建的 hash_set 中，如果是，那麼就是共同的 url，存到檔案裡面就可以了。
2、有 10 個檔案，每個檔案 1G，每個檔案的每一行存放的都是使用者的 query，每個檔案的 query 都可能重複。要求你按照 query 的頻度排序。方案 1：
1)順序讀取 10 個檔案，按照 hash(query) 的結果將 query 寫入到另外 10 個檔案（記為 ）中。這樣新生成的檔案每個的大小大約也 1G（假設 hash 函式是隨機的）。
2)找一臺記憶體在 2G 左右的機器，依次對 用 hash_map(query, query_count) 來統計每個 query 出現的次數。利用快速 / 堆 / 歸併排序按照出現次數進行排序。將排序好的 query 和對應的 query_cout 輸出到檔案中。這樣得到了 10 個排好序的檔案（記為 ）。
3) 對 這 10 個檔案進行歸併排序（內排序與外排序相結合）。
方案 2：
一般 query 的總量是有限的，只是重複的次數比較多而已，可能對於所有的 query，一次性就可以加入到記憶體了。這樣，我們就可以採用 trie 樹 /hash_map 等直接來統計每個 query 出現的次數，然後按出現次數做快速 / 堆 / 歸併排序就可以了。
方案 3：
與方案 1 類似，但在做完 hash，分成多個檔案後，可以交給多個檔案來處理，採用分散式的 架構 來處理（比如 MapReduce），最後再進行合併。
3、有一個 1G 大小的一個檔案，裡面每一行是一個詞，詞的大小不超過 16 位元組，記憶體限制大小是 1M。返回頻數最高的 100 個詞。順序讀檔案中，對於每個詞 x，取 ，然後按照該值存到 5000 個小檔案（記為 ）中。這樣每個檔案大概是 200k 左右。如果其中的有的檔案超過了 1M 大小，還可以按照類似的方法繼續往下分，知道分解得到的小檔案的大小都不超過 1M。對每個小檔案，統計每個檔案中出現的詞以及相應的頻率（可以採用 trie 樹 /hash_map 等），並取出出現頻率最大的 100 個詞（可以用含 100 個結點的最小堆），並把 100 詞及相應的頻率存入檔案，這樣又得到了 5000 個檔案。下一步就是把這 5000 個檔案進行歸併（類似與歸併排序）的過程了。
4、海量日誌資料，提取出某日訪問百度次數最多的那個 IP。首先是這一天，並且是訪問百度的日誌中的 IP 取出來，逐個寫入到一個大檔案中。注意到 IP 是 32 位的，最多有 個 IP。同樣可以採用對映的方法，比如模 1000，把整個大檔案對映為 1000 個小檔案，再找出每個小文中出現頻率最大的 IP（可以採用 hash_map 進行頻率統計，然後再找出頻率最大的幾個）及相應的頻率。然後再在這 1000 個最大的 IP 中，找出那個頻率最大的 IP，即為所求。
5、在 2.5 億個整數中找出不重複的整數，記憶體不足以容納這 2.5 億個整數。方案 1：
採用 2-Bitmap（每個數分配 2bit，00 表示不存在，01 表示出現一次，10 表示多次，11 無意義）進行，共需記憶體 記憶體，還可以接受。然後掃描這 2.5 億個整數，檢視 Bitmap 中相對應位，如果是 00 變 01，01 變 10，10 保持不變。所描完事後，檢視 bitmap，把對應位是 01 的整數輸出即可。
方案 2：
也可採用上題類似的方法，進行劃分小檔案的方法。然後在小檔案中找出不重複的整數，並排序。然後再進行歸併，注意去除重複的元素。
6、海量資料分佈在 100 臺電腦中，想個辦法高校統計出這批資料的 TOP10。1) 在每臺電腦上求出 TOP10，可以採用包含 10 個元素的堆完成（TOP10 小，用最大堆，TOP10 大，用最小堆）。比如求 TOP10 大，我們首先取前 10 個元素調整成最小堆，如果發現，然後掃描後面的資料，並與堆頂元素比較，如果比堆頂元素大，那麼用該元素替換堆頂，然後再調整為最小堆。最後堆中的元素就是 TOP10 大。
2) 求出每臺電腦上的 TOP10 後，然後把這 100 臺電腦上的 TOP10 組合起來，共 1000 個數據，再利用上面類似的方法求出 TOP10 就可以了。
7、怎麼在海量資料中找出重複次數最多的一個？先做 hash，然後求模對映為小檔案，求出每個小檔案中重複次數最多的一個，並記錄重複次數。然後找出上一步求出的資料中重複次數最多的一個就是所求（具體參考前面的題）。8、上千萬或上億資料（有重複），統計其中出現次數最多的錢 N 個數據。
上千萬或上億的資料，現在的機器的記憶體應該能存下。所以考慮採用 hash_map/ 搜尋二叉樹 / 紅黑樹等來進行統計次數。然後就是取出前 N 個出現次數最多的資料了，可以用第 6 題提到的堆機制完成。
8、1000 萬字符串，其中有些是重複的，需要把重複的全部去掉，保留沒有重複的字串。請怎麼設計和實現？這題用 trie 樹比較合適，hash_map 也應該能行。
9、一個文字檔案，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前 10 個詞，請給出思想，給出時間複雜度分析。這題是考慮時間效率。用 trie 樹統計每個詞出現的次數，時間複雜度是 O(nle)（le 表示單詞的平準長度）。然後是找出出現最頻繁的前 10 個詞，可以用堆來實現，前面的題中已經講到了，時間複雜度是 O(nlg10)。所以總的時間複雜度，是 O(nle) 與 O(nlg10) 中較大的哪一個。
10、一個文字檔案，找出前 10 個經常出現的詞，但這次檔案比較長，說是上億行或十億行，總之無法一次讀入記憶體，問最優解。首先根據用 hash 並求模，將檔案分解為多個小檔案，對於單個檔案利用上題的方法求出每個檔案件中 10 個最常出現的詞。然後再進行歸併處理，找出最終的 10 個最常出現的詞。
11、100w 個數中找出最大的 100 個數。方案 1： 在前面的題中，我們已經提到了，用一個含 100 個元素的最小堆完成。複雜度為 O(100wlg100)。
方案 2：採用快速排序的思想，每次分割之後只考慮比軸大的一部分，知道比軸大的一部分在比 100 多的時候，採用傳統排序演算法排序，取前 100 個。複雜度為 O(100w100)。
方案 3： 採用區域性淘汰法。選取前 100 個元素，並排序，記為序列 L。然後一次掃描剩餘的元素 x，與排好序的 100 個元素中最小的元素比，如果比這個最小的要大，那麼把這個最小的元素刪除，並把 x 利用插入排序的思想，插入到序列 L 中。依次迴圈，知道掃描了所有的元素。複雜度為 O(100w100)。
12、尋找熱門查詢：搜尋引擎 會透過日誌檔案把使用者每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為 1-255 位元組。假設目前有一千萬個記錄，這些查詢串的重複讀比較高，雖然總數是 1 千萬，但是如果去除重複和，不超過 3 百萬個。一個查詢串的重複度越高，說明查詢它的使用者越多，也就越熱門。請你統計最熱門的 10 個查詢串，要求使用的記憶體不能超過 1G。
(1) 請描述你解決這個問題的思路；
(2) 請給出主要的處理流程，演算法，以及演算法的複雜度。
採用 trie 樹，關鍵字域存該查詢串出現的次數，沒有出現為 0。最後用 10 個元素的最小推來對出現頻率進行排序。
13、一共有 N 個機器，每個機器上有 N 個數。每個機器最多存 O(N) 個數並對它們操作。如何找到 個數中的中數？方案 1： 先大體估計一下這些數的範圍，比如這裡假設這些數都是 32 位無符號整數（共有 個）。我們把 0 到 的整數劃分為 N 個範圍段，每個段包含 個整數。比如，第一個段位 0 到 ，第二段為 到 ，…，第 N 個段為 到 。然後，掃描每個機器上的 N 個數，把屬於第一個區段的數放到第一個機器上，屬於第二個區段的數放到第二個機器上，…，屬於第 N 個區段的數放到第 N 個機器上。注意這個過程每個機器上儲存的數應該是 O(N) 的。下面我們依次統計每個機器上數的個數，一次累加，直到找到第 k 個機器，在該機器上累加的數大於或等於 ，而在第 k-1 個機器上的累加數小於 ，並把這個數記為 x。那麼我們要找的中位數在第 k 個機器中，排在第 位。然後我們對第 k 個機器的數排序，並找出第 個數，即為所求的中位數。複雜度是 的。
方案 2： 先對每臺機器上的數進行排序。排好序後，我們採用歸併排序的思想，將這 N 個機器上的數歸併起來得到最終的排序。找到第 個便是所求。複雜度是 的。
14、最大間隙問題。給定 n 個實數 ，求著 n 個實數在實軸上向量 2 個數之間的最大差值，要求線性的時間演算法。
最先想到的方法就是先對這 n 個數據進行排序，然後一遍掃描即可確定相鄰的最大間隙。但該方法不能滿足線性時間的要求。故採取如下方法：
1) 找到 n 個數據中最大和最小資料 max 和 min。
2)用 n-2 個點等分割槽間 [min,max]，即將[min, max] 等分為 n-1 個區間（前閉後開區間），將這些區間看作桶，編號為 ，且桶 的上界和桶 i+1 的下屆相同，即每個桶的大小相同。每個桶的大小為： 。實際上，這些桶的邊界構成了一個等差數列（首項為 min，公差為 ），且認為將 min 放入第一個桶，將 max 放入第 n-1 個桶。
3) 將 n 個數放入 n-1 個桶中：將每個元素 分配到某個桶（編號為 index），其中 ，並求出分到每個桶的最大最小資料。
4) 最大間隙：除最大最小資料 max 和 min 以外的 n-2 個數據放入 n-1 個桶中，由抽屜原理可知至少有一個桶是空的，又因為每個桶的大小相同，所以最大間隙不會在同一桶中出現，一定是某個桶的上界和氣候某個桶的下界之間隙，且該量筒之間的桶（即便好在該連個便好之間的桶）一定是空桶。也就是說，最大間隙在桶 i 的上界和桶 j 的下界之間產生 ，一遍掃描即可完成。
15、將多個集合合併成沒有交集的集合：給定一個字串的集合，格式如：要求將其中交集不為空的集合合併，要求合併完成的集合之間無交集，例如上例應輸出 。
(1) 請描述你解決這個問題的思路；
(2) 給出主要的處理流程，演算法，以及演算法的複雜度；
(3) 請描述可能的改進。
採用並查集。首先所有的字串都在單獨的並查集中。然後依掃描每個集合，順序合併將兩個相鄰元素合併。例如，對於 ，首先檢視 aaa 和 bbb 是否在同一個並查集中，如果不在，那麼把它們所在的並查集合並，然後再看 bbb 和 ccc 是否在同一個並查集中，如果不在，那麼也把它們所在的並查集合並。接下來再掃描其他的集合，當所有的集合都掃描完了，並查集代表的集合便是所求。複雜度應該是 O(NlgN) 的。改進的話，首先可以記錄每個節點的根結點，改進查詢。合併的時候，可以把大的和小的進行合，這樣也減少複雜度。
16、最大子序列與最大子矩陣問題陣列的最大子序列問題：給定一個數組，其中元素有正，也有負，找出其中一個連續子序列，使和最大。
方案 1： 這個問題可以動態規劃的思想解決。設 表示以第 i 個元素 結尾的最大子序列，那麼顯然 。基於這一點可以很快用程式碼實現。最大子矩陣問題：給定一個矩陣（二維陣列），其中資料有大有小，請找一個子矩陣，使得子矩陣的和最大，並輸出這個和。
方案 2： 可以採用與最大子序列類似的思想來解決。如果我們確定了選擇第 i 列和第 j 列之間的元素，那麼在這個範圍內，其實就是一個最大子序列問題。如何確定第 i 列和第 j 列可以詞用暴搜的方法進行。
大資料量的問題是很多面試筆試中經常出現的問題，比如 baidu、google、騰訊這樣的一些涉及到海量資料的公司經常會問到。下面的方法是我對海量資料的處理方法進行了一個一般性的總結，當然這些方法可能並不能完全覆蓋所有的問題，但是這樣的一些方法也基本可以處理絕大多數遇到的問題。下面的一些問題基本直接來源於公司的面試筆試題目，方法不一定最優，如果你有更好的處理方法，歡迎與我討論。
1、Bloom filter
適用範圍： 可以用來實現資料字典，進行資料的判重，或者集合求交集
基本原理及要點：
對於原理來說很簡單, 位陣列 +k 個獨立 hash 函式。將 hash 函式對應的值的位陣列置 1，查詢時如果發現所有 hash 函式對應位都是 1 說明存在，很明顯這 個過程並不保證查詢的結果是 100% 正確的。同時也不支援刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個 counter 陣列代替位陣列，就可以支援刪除了。
還有一個比較重要的問題，如 何根據輸入元素個數 n，確定位陣列 m 的大小及 hash 函式個數。當 hash 函式個數k=(ln2)(m/n) 時錯誤率最小。在錯誤率不大於 E 的情況 下，m 至少要等於 nlg(1/E) 才能表示任意 n 個元素的集合。但 m 還應該更大些，因為還要保證 bit 數組裡至少一半為 0，則 m 應 該 >=nlg(1/E)lge 大概就是 nlg(1/E)1.44 倍 (lg 表示以 2 為底的對數)。
舉個例子我們假設錯誤率為 0.01，則此時 m 應大概是 n 的 13 倍。這樣 k 大概是 8 個。
注意這裡 m 與 n 的單位不同，m 是 bit 為單位，而 n 則是以元素個數為單位 (準確的說是不同元素的個數)。通常單個元素的長度都是有很多 bit 的。所以使用 bloom filter 記憶體上通常都是節省的。
擴充套件： Bloom filter 將集合中的元素對映到位陣列中，用 k（k 為雜湊函式個數）個對映位是否全 1 表示元素在不在這個集合中。Countingbloom filter（CBF）將位陣列中的每一位擴充套件為一個 counter，從而支援了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF 採用 counter 中的最小值來近似表示元素的出現頻率。
問題例項： 給你 A、B 兩個檔案，各存放 50 億條 URL，每條 URL 佔用 64 位元組，記憶體限制是 4G，讓你找出 A,B 檔案共同的 URL。如果是三個乃至 n 個檔案呢？
根據這個問題我們來計算下記憶體的佔用，4G=2^32 大概是 40 億8 大概是 340 億，n=50 億，如果按出錯率 0.01 算需要的大概是 650 億個 bit。現在可用的是 340 億，相差並不多，這樣可能會使出錯率上升些。另外如果這些 urlip 是一一對應的，就可以轉換成 ip，則大大簡單了。
2、Hashing
基本原理及要點：
hash 函式選擇，針對字串，整數，排列，具體相應的 hash 方法。
碰撞處理，一種是 open hashing，也稱為拉鍊法；另一種就是 closedhashing，也稱開地址法，opened addressing。
擴充套件： d-lefthashing 中的 d 是多個的意思，我們先簡化這個問題，看一看 2-left hashing。2-left hashing 指的是將一個雜湊表分成長度相等的兩半，分別叫做 T1 和 T2，給 T1 和 T2 分別配備一個雜湊函式，h1 和 h2。在儲存一個新的 key 時，同 時用兩個雜湊函式進行計算，得出兩個地址 h1[key] 和 h2[key]。這時需要檢查 T1 中的 h1[key] 位置和 T2 中的 h2[key] 位置，哪一個位置已經儲存的（有碰撞的）key 比較多，然後將新 key 儲存在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都儲存了一個 key，就把新 key 儲存在左邊的 T1 子表中，2-left 也由此而來。在查詢一個 key 時，必須進行兩次 hash，同時查詢兩個位置。
問題例項：
1)、海量日誌資料，提取出某日訪問百度次數最多的那個 IP。
IP 的數目還是有限的，最多 2^32 個，所以可以考慮使用 hash 將 ip 直接存入記憶體，然後進行統計。
3、bit-map
基本原理及要點： 使用 bit 陣列來表示某些元素是否存在，比如 8 位電話號碼
擴充套件： bloom filter 可以看做是對 bit-map 的擴充套件
問題例項：
1) 已知某個檔案內包含一些電話號碼，每個號碼為 8 位數字，統計不同號碼的個數。
8 位最多 99 999 999，大概需要 99m 個 bit，大概 10 幾 m 位元組的記憶體即可。
2)2.5 億個整數中找出不重複的整數的個數，記憶體空間不足以容納這 2.5 億個整數。
將 bit-map 擴充套件一下，用 2bit 表示一個數即可，0 表示未出現，1 表示出現一次，2 表示出現 2 次及以上。或者我們不用 2bit 來進行表示，我們用兩個 bit-map 即可模擬實現這個 2bit-map。
4、堆
適用範圍： 海量資料前 n 大，並且 n 比較小，堆可以放入記憶體
基本原理及要點： 最大堆求前 n 小，最小堆求前 n 大。方法，比如求前 n 小，我們比較當前元素與最大堆裡的最大元素，如果它小於最大元素，則應該替換那個最大元 素。這樣最後得到的 n 個元素就是最小的 n 個。適合 大資料 量，求前 n 小，n 的大小比較小的情況，這樣可以掃描一遍即可得到所有的前 n 元素，效率很高。
擴充套件： 雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。
問題例項：
1)100w 個數中找最大的前 100 個數。
用一個 100 個元素大小的最小堆即可。
5、雙層桶劃分
適用範圍： 第 k 大，中位數，不重複或重複的數字
基本原理及要點： 因為元素範圍很大，不能利用直接定址表，所以透過多次劃分，逐步確定範圍，然後最後在一個可以接受的範圍內進行。可以透過多次縮小，雙層只是一個例子。
問題例項：
1) 2.5 億個整數中找出不重複的整數的個數，記憶體空間不足以容納這 2.5 億個整數。
有點像鴿巢原理，整數個數為 2^32, 也就是，我們可以將這 2^32 個數，劃分為 2^8 個區域 (比如用單個檔案代表一個區域)，然後將資料分離到不同的區域，然後不同的區域在利用 bitmap 就可以直接解決了。也就是說只要有足夠的磁碟空間，就可以很方便的解決。
2) 5 億個 int 找它們的中位數。
這個例子比上面那個更明顯。首先我們將 int 劃分為 2^16 個區域，然後讀取資料統計落到各個區域裡的數的個數，之後我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然後第二次掃描我們只統計落在這個區域中的那些數就可以了。
實 際上，如果不是 int 是 int64，我們可以經過 3 次這樣的劃分即可降低到可以接受的程度。即可以先將 int64 分成 2^24 個區域，然後確定區域的第幾大數，在將該區域分成 2^20 個子區域，然後確定是子區域的第幾大數，然後子區域裡的數的個數只有 2^20，就可以直接利用 direct addr table 進行統計了。
6、 資料庫 索引
適用範圍： 大資料量的增刪改查
基本原理及要點： 利用資料的設計實現方法，對海量資料的增刪改查進行處理。
7、倒排索引 (Inverted index)
適用範圍： 搜尋引擎，關鍵字查詢
基本原理及要點： 為何叫倒排索引？一種索引方法，被用來儲存在全文搜尋下某個單詞在一個文件或者一組文件中的儲存位置的對映。
以英文為例，下面是要被索引的文字：
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
我們就能得到下面的反向檔案索引：
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
檢索的條件 "what","is" 和 "it" 將對應集合的交集。
正向索引開發出來用來儲存每個文件的單詞的列表。正向索引的查詢往往滿足每個文件有序頻繁的全文查詢和每個單詞在校驗文件中的驗證這樣的查詢。在正向索引 中，文件佔據了中心的位置，每個文件指向了一個它所包含的索引項的序列。也就是說文件指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文件，很 容易看到這個反向的關係。
問題例項： 文件檢索系統，查詢那些檔案包含了某單詞，比如常見的學術論文的關鍵字搜尋。
8、外排序
適用範圍： 大資料的排序，去重 。
基本原理及要點： 外排序的歸併方法，置換選擇 敗者樹原理，最優歸併樹 。
問題例項： 有一個 1G 大小的一個檔案，裡面每一行是一個詞，詞的大小不超過 16 個位元組，記憶體限制大小是 1M。返回頻數最高的 100 個詞。
這個資料具有很明顯的特點，詞的大小為 16 個位元組，但是記憶體只有 1m 做 hash 有些不夠，所以可以用來排序。記憶體可以當輸入緩衝區使用。
9、trie 樹
適用範圍： 資料量大，重複多，但是資料種類小可以放入記憶體
基本原理及要點： 實現方式，節點孩子的表示方式
擴充套件： 壓縮實現。
問題例項：
1)、有 10 個檔案，每個檔案 1G， 每個檔案的每一行都存放的是使用者的 query，每個檔案的 query 都可能重複。要你按照 query 的頻度排序 。
2)、1000 萬字符串，其中有些是相同的 ( 重複), 需要把重複的全部去掉，保留沒有重複的字串。請問怎麼設計和實現？
3)、尋找熱門查詢：查詢串的重複度比較高，雖然總數是 1 千萬，但如果除去重複後，不超過 3 百萬個，每個不超過 255 位元組。
10、分散式處理 mapreduce
適用範圍： 資料量大，但是資料種類小可以放入記憶體
基本原理及要點： 將資料交給不同的機器去處理，資料劃分，結果歸約。
問題例項：
1)、The canonical example applicationof MapReduce is a process to count the appearances of
each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);
void reduce(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially witha "1" value by the Map function, using the word as the result key.The framework puts together all the pairs with the same key and feeds them tothe same call to Reduce, thus this function just needs to sum all of its inputvalues to find the total appearances of that word.
2)、海量資料分佈在 100 臺電腦中，想個辦法高效統計出這批資料的 TOP10。
3)、一共有 N 個機器，每個機器上有 N 個數。每個機器最多存 O(N) 個數並對它們操作。如何找到 N^2 個數的中數 (median)？
經典問題分析：
上千萬 or 億資料（有重複），統計其中出現次數最多的前 N 個數據, 分兩種情況：可一次讀入記憶體，不可一次讀入。
可用思路：trie 樹 + 堆，資料庫索引，劃分子集分別統計，hash，分散式計算，近似統計，外排序
所謂的是否能一次讀入記憶體，實際上應該指去除重複後的資料量。如果去重後資料可以放入記憶體，我們可以為資料建立字典，比如透過 map，hashmap，trie，然後直接進行統計即可。當然在更新每條資料的出現次數的時候，我們可以利用一個堆來維護出現次數最多的前 N 個數據，當 然這樣導致維護次數增加，不如完全統計後在求前 N 大效率高。
如果資料無法放入記憶體。一方面我們可以考慮上面的字典方法能否被改進以適應這種情形，可以做的改變就是將字典存放到硬碟上，而不是記憶體，這可以參考資料庫的儲存方法。
當然還有更好的方法，就是可以採用分散式計算，基本上就是 map-reduce 過程，首先可以根據資料值或者把資料 hash(md5) 後的值，將資料按照範 圍劃分到不同的機子，最好可以讓資料劃分後可以一次讀入記憶體，這樣不同的機子負責處理各種的數值範圍，實際上就是 map。得到結果後，各個機子只需拿出各 自的出現次數最多的前 N 個數據，然後彙總，選出所有的資料中出現次數最多的前 N 個數據，這實際上就是 reduce 過程。
實際上可能想直 接將資料均分到不同的機子上進行處理，這樣是無法得到正確的解的。因為一個數據可能被均分到不同的機子上，而另一個則可能完全聚集到一個機子上，同時還可能存在具有相同數目的資料。比如我們要找出現次數最多的前 100 個，我們將 1000 萬的資料分佈到 10 臺機器上，找到每臺出現次數最多的前 100 個，歸併之後這樣不能保證找到真正的第 100 個，因為比如出現次數最多的第 100 個可能有 1 萬個，但是它被分到了 10 臺機子，這樣在每臺上只有 1 千 個，假設這些機子排名在 1000 個之前的那些都是單獨分佈在一臺機子上的，比如有 1001 個，這樣本來具有 1 萬個的這個就會被淘汰，即使我們讓每臺機子選 出出現次數最多的 1000 個再歸併，仍然會出錯，因為可能存在大量個數為 1001 個的發生聚集。因此不能將資料隨便均分到不同機子上，而是要根據 hash 後的值將它們對映到不同的機子上處理，讓不同的機器處理一個數值範圍。
而外排序的方法會消耗大量的 IO，效率不會很高。而上面的分散式方法，也可以用於單機版本，也就是將總的資料根據值的範圍，劃分成多個不同的子檔案，然後逐個處理。處理完畢之後再對這些單詞的及其出現頻率進行一個歸併。實際上就可以利用一個外排序的歸併過程。
另外還可以考慮近似計算，也就是我們可以透過結合自然語言屬性，只將那些真正實際中出現最多的那些詞作為一個字典，使得這個規模可以放入記憶體。
從海量資料中找出中位數
題目： 在一個檔案中有 10G 個整數，亂序排列，要求找出中位數。記憶體限制為 2G。只寫出思路即可（記憶體限制為 2G 的意思就是，可以使用 2G 的空間來執行程式，而不考慮這臺機器上的其他軟體的佔用記憶體）。
關於中位數：資料排序後，位置在最中間的數值。即將資料分成兩部分，一部分大於該數值，一部分小於該數值。中位數的位置：當樣本數為奇數時，中位數 =(N+1)/2 ; 當樣本數為偶數時，中位數為 N/2 與 1+N/2 的均值（那麼 10G 個數的中位數，就第 5G 大的數與第 5G+1 大的數的均值了）。
分析：明顯是一道工程性很強的題目，和一般的查詢中位數的題目有幾點不同。
1、原資料不能讀進記憶體，不然可以用快速選擇，如果數的範圍合適的話還可以考慮桶排序或者計數排序，但這裡假設是 32 位整數，仍有 4G 種取值，需要一個 16G 大小的陣列來計數。
2、若看成從 N 個數中找出第 K 大的數，如果 K 個數可以讀進記憶體，可以利用最小或最大堆，但這裡 K=N/2，有 5G 個數，仍然不能讀進記憶體。
3、接上，對於 N 個數和 K 個數都不能一次讀進記憶體的情況，《程式設計之美》裡給出一個方案：解法：首先假設 k 是 32 位無符號整數。
1) 讀一遍 10G 個整數，把整數對映到 256M 個區段中，用一個 64 位無符號整數給每個相應區段記數。說明：整數範圍是 0 - 2^32 - 1，一共有 4G 種取值，對映到 256M 個區段，則每個區段有 16（4 G/256M =16）種值，每 16 個值算一段， 0~15 是第 1 段，16~31 是第 2 段，……2^32-16~2^32-1 是第 256M 段。一個 64 位無符號整數最大值是 0~8G-1，這裡先不考慮溢位的情況。總共佔用記憶體 256M×8B=2GB。
2)從前到後對每一段的計數累加，當累加的和超過 5G 時停止，找出這個區段（即累加停止時達到的區段，也是中位數所在的區段）的數值範圍，設為 [a，a+15]，同時記錄累加到前一個區段的總數，設為 m。然後，釋放除這個區段佔用的記憶體。
3)再讀一遍 10G 個整數，把在 [a，a+15] 內的每個值計數，即有 16 個計數。
4) 對新的計數依次累加，每次的和設為 n，當 m+n 的值超過 5G 時停止，此時的這個計數所對應的數就是中位數。
總結：
1）以上方法只要讀兩遍整數，對每個整數也只是常數時間的操作，總體來說是線性時間。
2）考慮其他情況。
若是有符號的整數，只需改變對映即可。若是 64 位整數，則增加每個區段的範圍，那麼在第二次讀數時，要考慮更多的計數。如果某個計數溢位，那麼可認定所在的區段或代表整數為所求，這裡只需做好相應的處理。噢，忘了還要找第 5G+1 大的數了，相信有了以上的成果，找到這個數也不難了吧。
3）時空權衡。
花費 256 個區段也許只是恰好配合 2GB 的記憶體（其實也不是，呵呵）。可以增大區段範圍，減少區段數目，節省一些記憶體，雖然增加第二部分的對單個數值的計數，但第一部分對每個區段的計數加快了（總體改變？？待測）。
4）對映時儘量用位操作，由於每個區段的起點都是 2 的整數冪，對映起來也很方便。
1、有 1 億個浮點數，請找出其中對大的 10000 個。提示：假設每個浮點數佔 4 個位元組，1 億個浮點數就要站到相當大的空間，因此不能一次將全部讀入記憶體進行排序。
可以發現如果一次讀入那麼機器的記憶體肯定是受不了的，因此我們只有想其他方法解決，解決方式為了高效還是得符合一定的該機率解決，結果並不一定準確，但是應該可以作對大部分的資料。
我們可以把 1 億個浮點數分組為 100W 個一組，這樣就分為了 100 個組，第一次在每個組中找出最大的 1W 個數，第二次查詢的時候就是 100W 個數中再找出最大的 1W 個數。
PS:100W 個數中再找出最大的 1W 個數用類似快排的思想搞定。
還有一種更效率的思路是：
1)讀入的頭 10000 個數，直接建立二叉排序樹。O(1)
2)對以後每個讀入的數，比較是否比前 10000 個數中最小的大。(N 次比較) 如果小的話接著讀下面的數。O(N)
3) 如果大，查詢二叉排序樹，找到應當插入的位置。
5) 重複步驟 2，直到 10 億個數全都讀完。
6) 按照中序遍歷輸出當前二叉排序樹中的所有 10000 個數字。
基本上演算法的時間複雜度是 O(N) 次比較
演算法的空間複雜度是 10000(常數)
基於上面的想法，可以用最小堆來實現，這樣沒加入一個比 10000 個樹中最小的數大時的複雜度為 log10000.
2、有一篇英文文章 (也就是說每個單詞之間由空格分隔)，請找出“csdn”這個單詞出現的次數，要求效率最高，並寫出演算法的時間級。
可以把單詞看成一個 N 進位制數，CSDN 相當於 ('c'-'a')N^3+('s'-'a') N^2+('d'-'a')N+('n'-'a'), 然後查詢這個數出現的次數就是答案, 也可以建立一顆字典樹，然後去計數！
PS:N 可以取 32，64 等
3. 假設有 1kw 個身份證號，以及他們對應的資料。身份證號可能重複，要求找出出現次數最多的身份證號。
簡單進行 hash 搞定，O(n)，如果資料量再擴大我就不知道怎麼搞了，用磁碟的話，IO 資料是接受不了的。
4、百度每天都會接受數億的查詢請求, 如何在這麼多的查詢 (Query) 中找出高頻的 Query 是一個不小的挑戰. 而你的任務則更加艱鉅, 你需要在極其有限的資源下來找出這些高頻的 Query.(使用記憶體不得多於 1MB) 。輸入檔案是一行一個 Query，以檔案結束符結尾。每個 Query 位元組數 L(一個漢字兩個位元組)滿足：0<=16. 輸入大小不超過 1GB（包括換行符）。 輸出你認為最高頻的 100 個 query. 每行一個, 不能有重複, 不能多輸出, 但可以少輸出(見樣例).
hash，然後建立 hash[103][100] 的節點的表，每次找出出現次數最少的進行替換。
1、像搜尋的輸入資訊是一個字串，統計 300 萬輸入資訊中的最熱門的前十條，我們每次輸入的一個字串為不超過 255byte, 記憶體使用只有 1G,
請描述思想，寫出演算法（ C 語言 ），空間和時間複雜度，
2、國內的一些帖吧，如 baidu, 有幾十萬個主題，假設每一個主題都有上億的跟帖子，怎麼樣設計這個系統速度最好，請描述思想，寫出算髮（c 語言），空間和時間複雜度
第一題：全部存入記憶體也是可以的 300w255<1G, 當然進行字串 hash，然後進行統計
第二題：思想多級索引，第一級對主題進行索引，第二級對帖子，可以用一些複雜的資料結構維護，比方說用 B+ 樹進行維護。
題目描述：若有很大一組資料，資料的個數是 N(每個數佔 4 個位元組)，記憶體大小為 M 個位元組，其中 M<4N，使得不能在現有記憶體情況下透過直接排序找到這 N 個數的中位數。
騰訊海量資料面試題
1、在一個檔案中有 10G 個整數，亂序排列，要求找出中位數。記憶體限制為 2G。只寫出思路即可。
海量資料處理的問題。10G 個數，中位數就是第 5G、第 5G+1 個數。回想一下，一般情況下求中位數的做法：類似於快排的 partition，找到一個數，使比它小的數的個數佔到總數的一半就行。所以，可以把數值空間分段，然後統計每一段中資料的個數，這樣就可以很容易的確定中位數在那一段。找個該段後，資料量已經急劇減小了，剩下的問題就好處理了。這種方法可以說是桶排序的思想，也可以說是 hash 的思想。下面具體分析一下：
因為要統計每一段中資料的個數，所以可以用一個 unsigned int 型。unsignedint 一般佔 4 個位元組，可以計數到 2^32-1，大約是 4G。題目中有 10G 個數，如果有很多數落在同一個段中，unsigned int 肯定不夠用。所以，這裡的計數用要 8 位元組的 long long。即，相當於有一個數組，陣列是 long long 性，陣列的每一個元素，代表了一個數據段內的資料個數。這個陣列有多大？為了充分利用 2G 記憶體，陣列大小 2G/8= 256M。即，有陣列 long long cnt[256M].
假設題目中的 10G 個數都是 4 位元組的 int。如何把這 10G 個整數，對映到 cnt[256M] 的陣列中。可以使用計算機中的虛擬地址到物理地址的轉換。取 int 的高 28 位作為陣列下標的索引值，這樣就可以完成對映。
整個演算法的流程：
掃描 10G 個整數，對每個整數，取高 28 位，對映到陣列的某個元素上
給陣列的這個元素加 1，表示找到一個屬於該資料段的元素
掃描完 10G 個整數後，陣列 cnt 中就記錄了每段中元素的個數
從第一段開始，將元素個數累計，直到值剛好小於 5G，則中位數就在該段
這時對 10G 個整數再掃描一遍，記錄該段中每個元素的個數。直至累計到 5G 即可。
2、一個檔案中有 40 億個整數，每個整數為四個位元組，記憶體為 1GB，寫出一個演算法：求出這個檔案裡的整數里不包含的一個整數。
方法一：
使用點陣圖。4 位元組的 int，有 4G 個不同的值。每個值，對應 1bit，則共需 4G/8 =512M 記憶體。初始狀態，對 512M 的點陣圖清零。然後，對這 40 億個整數進行統計。如果某個值出現了，那麼就把這個值對應的 bit 置位。最後，掃描點陣圖，找到一個沒有被置位的 bit 即可。
方法二 ：
分段統計。Long long cnt[512M/8=64M] 對應數值空間的 64M 個數據段。每個資料段包含 64 個不同值，用一個 longlong 作為這個資料段內的點陣圖，點陣圖佔 64M8=512M。
這樣掃描一遍 40 億個整數後，從陣列中找到一個計數小於 64 的元素，然後檢視它的點陣圖，找出未出現的元素。
方法二平均效能應該比方法一快，但它佔的記憶體很恐怖。其實，這兩種方法都不是很實際，總共 1G 的記憶體，演算法就消耗 512M 甚至 1G，那剩下的系統程式怎麼辦？OS 都跑不起來了吧。
3、騰訊伺服器每秒有 2w 個 QQ 號同時上線，找出 5min 內重新登入的 qq 號並打印出來。
這應該是道面試題，面試官隨口問了一下。主要是看思路吧。
最簡單的想法：直接用 STL 的 set。從某一時刻開始計時，每登陸一個 QQ，把它放入 set，如果已存則直接列印。直到 5min 後，就可以 over 了。下面來簡單分析一下演算法的複雜度：
空間複雜度：用 str 儲存每個 QQ 號，假設 QQ 號有 20 位，理想情況下每個 QQ 佔 20Byte。則 5min 內的 QQ：2w 60 5 = 600w 個，需要的儲存空間 600w 20byte = 12000w byte = 120M，這樣的儲存應該可以忍受吧。
時間複雜度：STL 的 set 是用二叉樹（更確切的說是：紅黑樹）實現的，查詢效率是 O(lgn)，應該還是挺快的吧。
呃，有人說不讓用 STL。那就自己設計一個數據結構唄。該用什麼資料結構呢？想了想，還是繼續用樹，這裡用一個 trie tree 吧。節點內容包括 QQ 號、指向子節點的指標（這裡有 10 個，認為 QQ 由 0---9 的數字組成）。登陸時間要不要？考慮這樣一個問題：是否需要把所有的 QQ 都儲存在記憶體中？隨著時間的增加，登陸的 QQ 會越來越多，比較好的方法是把長時間不登陸的 QQ 釋放掉。所以需要記錄登陸時間，以便於釋放長期不登陸的 QQ。