## 本章海量數據的習題 **1** 有100W個關鍵字，長度小于等于50字節。用高效的算法找出top10的熱詞，并對內存的占用不超過1MB。 提示：老題，與caopengcs討論后，得出具體思路為： - 先把100W個關鍵字hash映射到小文件，根據題意，100W*50B = 50*10^6B = 50M，而內存只有1M，故干脆搞一個hash函數 % 50，分解成50個小文件； - 針對對每個小文件依次運用hashmap(key，value)完成每個key的value次數統計，后用堆找出每個小文件中value次數最大的top 10； -最后依次對每兩小文件的top 10歸并，得到最終的top 10。 此外，很多細節需要注意下，舉個例子，如若hash映射后導致分布不均的話，有的小文件可能會超過1M，故為保險起見，你可能會說根據數據范圍分解成50~500或更多的小文件，但到底是多少呢？我覺得這不重要，勿糾結答案，雖準備在平時，但關鍵還是看臨場發揮，保持思路清晰關注細節即可。 **2** 單機5G內存，磁盤200T的數據，分別為字符串，然后給定一個字符串，判斷這200T數據里面有沒有這個字符串，怎么做？ 如果查詢次數會非常的多, 怎么預處理？ 提示：如果數據是200g且允許少許誤差的話，可以考慮用布隆過濾器Bloom Filter。但本題是200T，得另尋良策，具體解法請讀者繼續思考。 **3** 現在有一個大文件，文件里面的每一行都有一個group標識（group很多，但是每個group的數據量很小），現在要求把這個大文件分成十個小文件，要求： - 1、同一個group的必須在一個文件里面； - 2、切分之后，要求十個小文件的數據量盡可能均衡。 **7** 服務器內存1G，有一個2G的文件，里面每行存著一個QQ號（5-10位數），怎么最快找出出現過最多次的QQ號。 **8** 盡量高效的統計一片英文文章（總單詞數目）里出現的所有英文單詞，按照在文章中首次出現的順序打印輸出該單詞和它的出現次數。 **9** 在人人好友里，A和B是好友，B和C是好友，如果A　和C不是好友，那么C是A的二度好友，在一個有10萬人的數據庫里，如何在時間０（ｎ）里，找到某個人的十度好友。 **12** 海量記錄，記錄形式如下： TERMID URLNOCOUNT urlno1 urlno2 ..., urlnon，請問怎么考慮資源和時間這兩個因素，實現快速查詢任意兩個記錄的交集，并集等，設計相關的數據結構和算法。 **14** 有一億個整數，請找出最大的1000個，要求時間越短越好，空間占用越少越好。 **18** 10億個int型整數，如何找出重復出現的數字。 **19** 有2G的一個文本文檔，文件每行存儲的是一個句子，每個單詞是用空格隔開的。問：輸入一個句子，如何找到和它最相似的前10個句子。 提示：可用倒排文檔。 **20** 某家視頻網站，每天有上億的視頻被觀看，現在公司要請研發人員找出最熱門的視頻。 該問題的輸入可以簡化為一個字符串文件，每一行都表示一個視頻id，然后要找出出現次數最多的前100個視頻id，將其輸出，同時輸出該視頻的出現次數。 - 1.假設每天的視頻播放次數為3億次，被觀看的視頻數量為一百萬個，每個視頻ID的長度為20字節，限定使用的內存為1G。請簡述做法，再寫代碼。 - 2.假設每個月的視頻播放次數為100億次，被觀看的視頻數量為1億，每個視頻ID的長度為20字節，一臺機器被限定使用的內存為1G。 提示：萬變不離其宗，分而治之/Hash映射 + Hash統計 + 堆/快速/歸并排序。 **21** 有一個log文件，里面記錄的格式為： QQ號 時間 flag 123456 14：00：00 0 123457 14：00：01 1 其中flag=0表示登錄 flag=1表示退出 問：統計一天平均在線的QQ數。 **22** 一個文本，一萬行，每行一個詞，統計出現頻率最高的前10個詞（詞的平均長度為Len）。并分析時間復雜度。 **23** 在一個文件中有 10G 個整數，亂序排列，要求找出中位數。內存限制為 2G。只寫出思路即可。 **24** 一個url指向的頁面里面有另一個url,最終有一個url指向之前出現過的url或空，這兩種情形都定義為null。這樣構成一個單鏈表。給兩條這樣單鏈表，判斷里面是否存在同樣的url。url以億級計，資源不足以hash。 **25** 一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。 **26** 1000萬字符串，其中有些是重復的，需要把重復的全部去掉，保留沒有重復的字符串。請怎么設計和實現？ **27** 有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要你按照query的頻度排序。 **28** 現有一200M的文本文件，里面記錄著IP地址和對應地域信息，如 202.100.83.56 北京 北京大學 202.100.83.120 北京 人民大學 202.100.83.134 北京 中國青年政治學院 211.93.120.45 長春市 長春大學 211.93.120.129 吉林市 吉林大學 211.93.120.200 長春 長春KTV 現有6億個IP地址，請編寫程序，讀取IP地址便轉換成IP地址相對應的城市，要求有較好的時間復雜度和空間復雜度。