1. 首頁 > 生活百科 > >

大數據面試題2021

數據生活經驗

每晚10點，捕獲技術思考和創業資源洞察

“分而治之”( Divide and conquer)方法(又稱“分治術”)  ， 是有效算法設計中普遍采用的一種技術 。
有一個1G大小的一個文件 ， 里面每一行是一個英文單詞 ， 詞的大小不超過16字節，內存限制是1M 。請設計一個算法思路，返回頻數最高的100個詞.
初步一看，要處理的文件大小1G，可內存卻只有1M 。我們知道1G的文件用1M的內存空間處理不太現實 。按照1M的上限來計算，假設每個單詞都為16個字節，那么1M的內存可以處理多少個單詞？
我們來計算下 ， 1M = 1024 KB = 1024 * 1024 B。1M / 16B = 2^16個單詞，那么1G大概有多少個單詞呢？有2^26個單詞，但是實際中應該不止，因為我們是按照最大單詞長度來計算的 ， 有可能有的單詞只有兩個字母 。
大數據面試題2021

文章插圖
方案1大概思路：
  1. 分而治之/hash映射：順序讀文件中，對于每個詞x，取hash(x)%5000，然后按照該值存到5000個小文件（記為x0,x1,...x4999）中 。這樣每個文件大概是200k左右 。如果其中的有的文件超過了1M大小 ， 還可以按照類似的方法繼續往下分 ， 直到分解得到的小文件的大小都不超過1M 。
  2. hash統計：對每個小文件，采用trie樹/hash_map等統計每個文件中出現的詞以及相應的頻率 。
  3. 堆/歸并排序：取出出現頻率最大的100個詞（可以用含100個結點的最小堆） ， 并把100個詞及相應的頻率存入文件，這時我們又得到了5000個文件 。最后把這5000個文件進行歸并（類似與歸并排序）的過程 。
【大數據面試題2021】類似這樣的方案應該有很多，我們共同去研究學習，經驗都是個人實踐總結出來的 ， 以上僅代表個人觀點 。以此分享給大家，不足之處望大家留言補充 。