資訊專欄INFORMATION COLUMN
摘要：這幾天小秋去面試了，不過最近小秋學習了不少和位算法相關(guān)文章，例如面試現(xiàn)場如何判斷一個數(shù)是否在億個整數(shù)中算法技巧位運算裝逼指南對于算法題還是有點信心的，，，，于是，發(fā)現(xiàn)了如下對話。
這幾天小秋去面試了，不過最近小秋學習了不少和位算法相關(guān)文章，例如
【面試現(xiàn)場】如何判斷一個數(shù)是否在40億個整數(shù)中？
【算法技巧】位運算裝逼指南
對于算法題還是有點信心的，，，，于是，發(fā)現(xiàn)了如下對話。
20億級別面試官：如果我給你 2GB 的內(nèi)存，并且給你 20 億個 int 型整數(shù)，讓你來找出次數(shù)出現(xiàn)最多的數(shù)，你會怎么做？
小秋：（嗯？怎么感覺和之前的那道判斷一個數(shù)是否出現(xiàn)在這 40 億個整數(shù)中有點一樣？可是，如果還是采用 bitmap 算法的話，好像無法統(tǒng)計一個數(shù)出現(xiàn)的次數(shù)，只能判斷一個數(shù)是否存在），我可以采用哈希表來統(tǒng)計，把這個數(shù)作為 key，把這個數(shù)出現(xiàn)的次數(shù)作為 value，之后我再遍歷哈希表哪個數(shù)出現(xiàn)最多的次數(shù)最多就可以了。
面試官：你可以算下你這個方法需要花費多少內(nèi)存嗎？
小秋：key 和 value 都是 int 型整數(shù)，一個 int 型占用 4B 的內(nèi)存，所以哈希表的一條記錄需要占用 8B，最壞的情況下，這 20 億個數(shù)都是不同的數(shù)，大概會占用 16GB 的內(nèi)存。
面試官:你的分析是對的，然而我給你的只有 2GB 內(nèi)存。
小秋：（感覺這道題有點相似，不過不知為啥，沒啥思路，這下涼涼），目前沒有更好的方法。
面試官：按照你那個方法的話，最多只能記錄大概 2 億多條不同的記錄，2 億多條不同的記錄，大概是 1.6GB 的內(nèi)存。
小秋：（嗯？面試官說這話是在提示我？）我有點思路了，我可以把這 20 億個數(shù)存放在不同的文件，然后再來篩選。
面試題：可以具體說說嗎？
小秋：剛才你說，我的那個方法，最多只能記錄大概 2 億多條的不同記錄，那么我可以把這 20 億個數(shù)映射到不同的文件中去，例如，數(shù)值在 0 至 2億之間的存放在文件1中，數(shù)值在2億至4億之間的存放在文件2中....，由于 int 型整數(shù)大概有 42 億個不同的數(shù)，所以我可以把他們映射到 21 個文件中去，如圖
顯然，相同的數(shù)一定會在同一個文件中，我們這個時候就可以用我的那個方法，統(tǒng)計每個文件中出現(xiàn)次數(shù)最多的數(shù)，然后再從這些數(shù)中再次選出最多的數(shù)，就可以了。
面試官：嗯，這個方法確實不錯，不過，如果我給的這 20 億個數(shù)數(shù)值比較集中的話，例如都處于 1~20000000 之間，那么你都會把他們?nèi)坑成涞酵粋€文件中，你有優(yōu)化思路嗎？
小秋：那我可以先把每個數(shù)先做哈希函數(shù)映射，根據(jù)哈希函數(shù)得到的哈希值，再把他們存放到對應(yīng)的文件中，如果哈希函數(shù)設(shè)計到好的話，那么這些數(shù)就會分布的比較平均。（關(guān)于哈希函數(shù)的設(shè)計，我就不說了，我這只是提供一種思路）
40億級別面試官：那如果我把 20 億個數(shù)加到 40 億個數(shù)呢？
小秋：（這還不簡單，映射到42個文件唄）那我可以加大文件的數(shù)量啊。
面試官：那如果我給的這 40 億個數(shù)中數(shù)值都是一樣的，那么你的哈希表中，某個 key 的 value 存放的數(shù)值就會是 40 億，然而 int 的最大數(shù)值是 21 億左右，那么就會出現(xiàn)溢出，你該怎么辦？
小秋：（那我把 int 改為 long 不就得了，雖然會占用更多的內(nèi)存，那我可以把文件分多幾份唄，不過，這應(yīng)該不是面試官想要的答案），我可以把 value 初始值賦值為 負21億，這樣，如果 value 的數(shù)值是 21 億的話，就代表某個 key 出現(xiàn)了 42 億次了。
80億級別這里說明下，文件還是 21 個就夠了，因為 21 個文件就可以把每個文件的數(shù)值種類控制在 2億種了，也就是說，哈希表存放的記錄還是不會超過 2 億中。
面試官：反應(yīng)挺快哈，那我如果把 40 億增加到 80 億呢？
小秋：（我靠，這變本加厲?。?........我知道了，我可以一邊遍歷一遍判斷啊，如果我在統(tǒng)計的過程中，發(fā)現(xiàn)某個 key 出現(xiàn)的次數(shù)超過了 40 億次，那么，就不可能再有另外一個 key 出現(xiàn)的次數(shù)比它多了，那我直接把這個 key 返回就搞定了。
面試官：行，此次面試到此結(jié)束，回去等通知吧。
總結(jié)今天這篇文章主要講了大數(shù)據(jù)處理相關(guān)的一些問題，后面可能還會給大家找一些類似，但處理方式不同的題勒，大家如果覺得不錯，不妨：
1、點贊，讓更多的人也能看到這篇內(nèi)容（收藏不點贊，都是耍流氓 -_-）
2、關(guān)注我，讓我們成為長期關(guān)系
3、關(guān)注公眾號「苦逼的碼農(nóng)」，主要寫算法、計算機基礎(chǔ)之類的文章，里面已有100多篇原創(chuàng)文章，我也分享了很多視頻、書籍的資源，以及開發(fā)工具，歡迎各位的關(guān)注，第一時間閱讀我的文章。。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/7872.html
摘要：答案使用，申請一個長度為類型的，每個位置只表示或，該數(shù)組占用空間約。遍歷億個數(shù)，當前數(shù)為，落在區(qū)間，對應(yīng)。 過濾100億黑名單 題目 假設(shè)有100億個URL的黑名單，每個URL最多占用64B，設(shè)計一個過濾系統(tǒng)，判斷某條URL是否在黑名單里。 要求 不高于萬分之一的判斷失誤率；額外內(nèi)存不超過30GB 答案 100億個64B的URL需要640GB的內(nèi)存，顯然直接存哈希表不合理。考慮布隆過濾...
摘要：面試，是跳槽后第一個需要面對的問題而且不同公司面試的著重點不同但是卻有一個共同點基礎(chǔ)是必考的。對自動災(zāi)難恢復(fù)有要求的表。 貌似這一點適應(yīng)的行業(yè)最廣，但是我可以很肯定的說：當你從事Java一年后，重新找工作時，才會真實的感受到這句話。 工作第一年，往往是什么都充滿新鮮感，什么都學習，沖勁十足的一年；WEB行業(yè)知識更新特別快，今天一個框架的新版本，明天又是另一個新框架，有時往往根據(jù)項目的需...
摘要：面試，是跳槽后第一個需要面對的問題而且不同公司面試的著重點不同但是卻有一個共同點基礎(chǔ)是必考的。對自動災(zāi)難恢復(fù)有要求的表。 貌似這一點適應(yīng)的行業(yè)最廣，但是我可以很肯定的說：當你從事Java一年后，重新找工作時，才會真實的感受到這句話。 工作第一年，往往是什么都充滿新鮮感，什么都學習，沖勁十足的一年；WEB行業(yè)知識更新特別快，今天一個框架的新版本，明天又是另一個新框架，有時往往根據(jù)項目的需...
閱讀 1924·2023-04-26 01:02
閱讀 5065·2021-11-24 09:39
閱讀 1945·2019-08-30 15:44
閱讀 3127·2019-08-30 11:10
閱讀 1863·2019-08-30 10:49
閱讀 1146·2019-08-29 17:06
閱讀 678·2019-08-29 16:15
閱讀 976·2019-08-29 15:17
