給定ab兩個文件各存放億個url每個url各占字節內存限制是G讓你找出ab文件共同的url？
方案可以估計每個文件安的大小為G×=G遠遠大於內存限制的G所以不可能將其完全加載到內存中處理考慮采取分而治之的方法
遍歷文件a對每個url求取然後根據所取得的值將url分別存儲到個小文件（記為）中這樣每個小文件的大約為M
遍歷文件b采取和a相同的方式將url分別存儲到小文件中（記為）這樣處理後所有可能相同的url都在對應的小文件（）中不對應的小文件不可能有相同的url然後我們只要求出對小文件中相同的url即可
求每對小文件中相同的url時可以把其中一個小文件的url存儲到hash_set中然後遍歷另一個小文件的每個url看其是否在剛才構建的hash_set中如果是那麼就是共同的url存到文件裡面就可以了
方案如果允許有一定的錯誤率可以使用Bloom filterG內存大概可以表示億bit將其中一個文件中的url使用Bloom filter映射為這億bit然後挨個讀取另外一個文件的url檢查是否與Bloom filter如果是那麼該url應該是共同的url（注意會有一定的錯誤率）
讀者反饋@crowgns
hash後要判斷每個文件大小如果hash分的不均衡有文件較大還應繼續hash分文件換個hash算法第二次再分較大的文件一直分到沒有較大的文件為止這樣文件標號可以用A表示（第一次hash編號為文件較大所以參加第二次hash編號為）
由於存在第一次hash如果有大文件不能用直接set的方法建議對每個文件都先用字符串自然順序排序然後具有相同hash編號的（如都是而不能a編號是b編號是和）可以直接從頭到尾比較一遍對於層級不一致的如ab有層級淺的要和層級深的每個文件都比較一次才能確認每個相同的uri
有個文件每個文件G每個文件的每一行存放的都是用戶的query每個文件的query都可能重復要求你按照query的頻度排序
方案
順序讀取個文件按照hash(query)%的結果將query寫入到另外個文件（記為）中這樣新生成的文件每個的大小大約也G（假設hash函數是隨機的）
找一台內存在G左右的機器依次對用hash_map(query query_count)來統計每個query出現的次數利用快速/堆/歸並排序按照出現次數進行排序將排序好的query和對應的query_cout輸出到文件中這樣得到了個排好序的文件（記為）
對這個文件進行歸並排序（內排序與外排序相結合）
方案
一般query的總量是有限的只是重復的次數比較多而已可能對於所有的query一次性就可以加入到內存了這樣我們就可以采用trie樹/hash_map等直接來統計每個query出現的次數然後按出現次數做快速/堆/歸並排序就可以了
（讀者反饋@店小二原文第二個例子中找一台內存在G左右的機器依次對用hash_map(query query_count)來統計每個query出現的次數由於query會重復作為key的話應該使用hash_multimaphash_map不允許key重復此反饋是否正確待日後考證）
方案
與方案類似但在做完hash分成多個文件後可以交給多個文件來處理采用分布式的架構來處理（比如MapReduce）最後再進行合並
有一個G大小的一個文件裡面每一行是一個詞詞的大小不超過字節內存限制大小是M返回頻數最高的個詞
方案順序讀文件中對於每個詞x取然後按照該值存到個小文件（記為）中這樣每個文件大概是k左右如果其中的有的文件超過了M大小還可以按照類似的方法繼續往下分知道分解得到的小文件的大小都不超過M對每個小文件統計每個文件中出現的詞以及相應的頻率（可以采用trie樹/hash_map等）並取出出現頻率最大的個詞（可以用含個結點的最小堆）並把詞及相應的頻率存入文件這樣又得到了個文件下一步就是把這個文件進行歸並（類似與歸並排序）的過程了
海量日志數據提取出某日訪問百度次數最多的那個IP
方案首先是這一天並且是訪問百度的日志中的IP取出來逐個寫入到一個大文件中注意到IP是位的最多有^個IP同樣可以采用映射的方法比如模把整個大文件映射為個小文件再找出每個小文中出現頻率最大的IP（可以采用hash_map進行頻率統計然後再找出頻率最大的幾個）及相應的頻率然後再在這個最大的IP中找出那個頻率最大的IP即為所求
在億個整數中找出不重復的整數內存不足以容納這億個整數
方案采用Bitmap（每個數分配bit表示不存在表示出現一次表示多次無意義）進行共需內存^*bit=GB內存還可以接受然後掃描這億個整數查看Bitmap中相對應位如果是變變保持不變所描完事後查看bitmap把對應位是的整數輸出即可
方案也可采用上題類似的方法進行劃分小文件的方法然後在小文件中找出不重復的整數並排序然後再進行歸並注意去除重復的元素
海量數據分布在台電腦中想個辦法高效統計出這批數據的TOP
方案
在每台電腦上求出TOP可以采用包含個元素的堆完成（TOP小用最大堆TOP大用最小堆）比如求TOP大我們首先取前個元素調整成最小堆如果發現然後掃描後面的數據並與堆頂元素比較如果比堆頂元素大那麼用該元素替換堆頂然後再調整為最小堆最後堆中的元素就是TOP大
求出每台電腦上的TOP後然後把這台電腦上的TOP組合起來共個數據再利用上面類似的方法求出TOP就可以了
（更多可以參考第三章尋找最小的k個數以及第三章續Top K算法問題的實現）
讀者反饋@QinLeopard
第題的方法中是不是不能保證每個電腦上的前十條肯定包含最後頻率最高的前十條呢？
比如說第一個文件中A() B() C() D()
第二個文件中A()B()C()D()
第三個文件中: A() B() C() D()
如果要選Top() 選出來的結果是A但結果應該是B
@July我想這位讀者可能沒有明確提議本題目中的TOP是指最大的個數而不是指出現頻率最多的個數但如果說現在有另外一提要你求頻率最多的 個相當於求訪問次數最多的個IP地址那道題即是本文中上面的第題特此說明
怎麼在海量數據中找出重復次數最多的一個？
方案先做hash然後求模映射為小文件求出每個小文件中重復次數最多的一個並記錄重復次數然後找出上一步求出的數據中重復次數最多的一個就是所求（具體參考前面的題）
上千萬或上億數據（有重復）統計其中出現次數最多的錢N個數據
方案上千萬或上億的數據現在的機器的內存應該能存下所以考慮采用hash_map/搜索二叉樹/紅黑樹等來進行統計次數然後就是取出前N個出現次數最多的數據了可以用第題提到的堆機制完成
萬字符串其中有些是重復的需要把重復的全部去掉保留沒有重復的字符串請怎麼設計和實現？
方案這題用trie樹比較合適hash_map也應該能行
一個文本文件大約有一萬行每行一個詞要求統計出其中最頻繁出現的前個詞請給出思想給出時間復雜度分析
方案這題是考慮時間效率用trie樹統計每個詞出現的次數時間復雜度是O(n*le)（le表示單詞的平准長度）然後是找出出現最頻繁的前個詞可以用堆來實現前面的題中已經講到了時間復雜度是O(n*lg)所以總的時間復雜度是O(n*le)與O(n*lg)中較大的哪一個
一個文本文件找出前個經常出現的詞但這次文件比較長說是上億行或十億行總之無法一次讀入內存問最優解
方案首先根據用hash並求模將文件分解為多個小文件對於單個文件利用上題的方法求出每個文件件中個最常出現的詞然後再進行歸並處理找出最終的個最常出現的詞
w個數中找出最大的個數
方案在前面的題中我們已經提到了用一個含個元素的最小堆完成復雜度為O(w*lg)
方案采用快速排序的思想每次分割之後只考慮比軸大的一部分知道比軸大的一部分在比多的時候采用傳統排序算法排序取前個復雜度為O(w*)
方案采用局部淘汰法選取前個元素並排序記為序列L然後一次掃描剩余的元素x與排好序的個元素中最小的元素比如果比這個最小的要大那麼把這個最小的元素刪除並把x利用插入排序的思想插入到序列L中依次循環知道掃描了所有的元素復雜度為O(w*)
尋找熱門查詢
搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來每個查詢串的長度為字節假設目前有一千萬個記錄這些查詢串的重復讀比較高雖然總數是千萬但是如果去除重復和不超過百萬個一個查詢串的重復度越高說明查詢它的用戶越多也就越熱門請你統計最熱門的個查詢串要求使用的內存不能超過G
() 請描述你解決這個問題的思路
() 請給出主要的處理流程算法以及算法的復雜度
方案采用trie樹關鍵字域存該查詢串出現的次數沒有出現為最後用個元素的最小推來對出現頻率進行排序
關於此問題的詳細解答請參考此文的第節第三章續Top K算法問題的實現
一共有N個機器每個機器上有N個數每個機器最多存O(N)個數並對它們操作如何找到N^個數中的中數？
方案先大體估計一下這些數的范圍比如這裡假設這些數都是位無符號整數（共有^個）我們把到^的整數劃分為N個范圍段每個段包含（^）/N個整數比如第一個段位到^/N第二段為（^）/N到（^）/N…第N個段為（^）（N）/N到^然後掃描每個機器上的N個數把屬於第一個區段的數放到第一個機器上屬於第二個區段的數放到第二個機器上…屬於第N個區段的數放到第N個機器上注意這個過程每個機器上存儲的數應該是O(N)的下面我們依次統計每個機器上數的個數一次累加直到找到第k個機器在該機器上累加的數大於或等於（N^）/而在第k個機器上的累加數小於（N^）/並把這個數記為x那麼我們要找的中位數在第k個機器中排在第（N^）/x位然後我們對第k個機器的數排序並找出第（N^）/x個數即為所求的中位數的復雜度是O（N^）的
方案先對每台機器上的數進行排序排好序後我們采用歸並排序的思想將這N個機器上的數歸並起來得到最終的排序找到第（N^）/個便是所求復雜度是O（N^*lgN^）的
最大間隙問題
給定n個實數求著n個實數在實軸上向量個數之間的最大差值要求線性的時間算法
方案最先想到的方法就是先對這n個數據進行排序然後一遍掃描即可確定相鄰的最大間隙但該方法不能滿足線性時間的要求故采取如下方法
找到n個數據中最大和最小數據max和min
用n個點等分區間[min max]即將[min max]等分為n個區間（前閉後開區間）將這些區間看作桶編號為且桶i的上界和桶i+的下屆相同即每個桶的大小相同每個桶的大小為實際上這些桶的邊界構成了一個等差數列（首項為min公差為）且認為將min放入第一個桶將max放入第n個桶
將n個數放入n個桶中將每個元素x[i] 分配到某個桶（編號為index）其中並求出分到每個桶的最大最小數據
最大間隙除最大最小數據max和min以外的n個數據放入n個桶中由抽屜原理可知至少有一個桶是空的又因為每個桶的大小相同所以最大間隙不會在同一桶中出現一定是某個桶的上界和氣候某個桶的下界之間隙且該量筒之間的桶（即便好在該連個便好之間的桶）一定是空桶也就是說最大間隙在桶i的上界和桶j的下界之間產生j>=i+一遍掃描即可完成
將多個集合合並成沒有交集的集合
給定一個字符串的集合格式如要求將其中交集不為空的集合合並要求合並完成的集合之間無交集例如上例應輸出
() 請描述你解決這個問題的思路
() 給出主要的處理流程算法以及算法的復雜度
() 請描述可能的改進
方案采用並查集首先所有的字符串都在單獨的並查集中然後依掃描每個集合順序合並將兩個相鄰元素合並例如對於首先查看aaa和bbb是否在同一個並查集中如果不在那麼把它們所在的並查集合並然後再看bbb和ccc是否在同一個並查集中如果不在那麼也把它們所在的並查集合並接下來再掃描其他的集合當所有的集合都掃描完了並查集代表的集合便是所求復雜度應該是O(NlgN)的改進的話首先可以記錄每個節點的根結點改進查詢合並的時候可以把大的和小的進行合這樣也減少復雜度
最大子序列與最大子矩陣問題
數組的最大子序列問題給定一個數組其中元素有正也有負找出其中一個連續子序列使和最大
方案這個問題可以動態規劃的思想解決設b[i]表示以第i個元素a[i]結尾的最大子序列那麼顯然基於這一點可以很快用代碼實現
最大子矩陣問題給定一個矩陣（二維數組）其中數據有大有小請找一個子矩陣使得子矩陣的和最大並輸出這個和
方案可以采用與最大子序列類似的思想來解決如果我們確定了選擇第i列和第j列之間的元素那麼在這個范圍內其實就是一個最大子序列問題如何確定第i列和第j列可以詞用暴搜的方法進行
From:http://tw.wingwit.com/Article/program/sjjg/201405/30744.html
