當(dāng)前位置：首頁 > 公眾號精選 > 小林coding

40億個QQ號碼如何去重？

時間：2021-12-08 17:28:48
關(guān)鍵字： BITMAP    UNSIGNED    內(nèi)存    騰訊   
手機看文章

掃描二維碼
隨時隨地手機看文章

[導(dǎo)讀]今天，我們來聊一道常見的考題，也出現(xiàn)在騰訊面試的三面環(huán)節(jié)，非常有意思。具體的題目如下：文件中有40億個QQ號碼，請設(shè)計算法對QQ號碼去重，相同的QQ號碼僅保留一個，內(nèi)存限制1G.?這個題目的意思應(yīng)該很清楚了，比較直白。為了便于大家理解，我來畫個動圖玩玩，希望大家喜歡。能否做對這道...


今天，我們來聊一道常見的考題，也出現(xiàn)在騰訊面試的三面環(huán)節(jié)，非常有意思。具體的題目如下：

文件中有40億個QQ號碼，請設(shè)計算法對QQ號碼去重，相同的QQ號碼僅保留一個，內(nèi)存限制1G.?

這個題目的意思應(yīng)該很清楚了，比較直白。為了便于大家理解，我來畫個動圖玩玩，希望大家喜歡。


能否做對這道題目，很大程度上就決定了能否拿下騰訊的offer，有一定的技巧性，一起來看下吧。

在原題中，實際有40億個QQ號碼，為了方便起見，在圖解和敘述時，僅以4個QQ為例來說明。


方法一：排序

很自然地，最簡單的方式是對所有的QQ號碼進行排序，重復(fù)的QQ號碼必然相鄰，保留第一個，去掉后面重復(fù)的就行。

原始的QQ號為：


排序后的QQ號為：


去重就簡單了：


可是，面試官要問你，去重一定要排序嗎？顯然，排序的時間復(fù)雜度太高了，無法通過騰訊面試。


方法二：hashmap

既然直接排序的時間復(fù)雜度太高，那就用hashmap吧，具體思路是把QQ號碼記錄到hashmap中：

mapFlag[123] = truemapFlag[567] = truemapFlag[123] = truemapFlag[890] = true由于hashmap的去重性質(zhì)，可知實際自動變成了：
mapFlag[123] = truemapFlag[567]?=?truemapFlag[890] = true很顯然，只有123，567，890存在，所以這也就是去重后的結(jié)果。可是，面試官又要問你了：實際要存40億QQ號碼，1G的內(nèi)存夠分配這么多空間嗎？顯然不行，無法通過騰訊面試。


方法三：文件切割

顯然，這是海量數(shù)據(jù)問題?？催^很多面經(jīng)的求職者，自然想到文件切割的方式，避免內(nèi)存過大。

可是，絞盡腦汁思考，要么使用文件間的歸并排序，要么使用桶排序，反正最終是能排序的。

既然排序好了，那就能實現(xiàn)去重了，貌似就萬事大吉了。我只能坦白地說，高興得有點早哦。

接著，面試官又要問你：這么多的文件操作，效率自然不高啊。顯然，無法通過騰訊面試。


方法四：bitmap

來看絕招！我們可以對hashmap進行優(yōu)化，采用bitmap這種數(shù)據(jù)結(jié)構(gòu)，可以順利地同時解決時間問題和空間問題。

在很多實際項目中，bitmap經(jīng)常用到。我看了不少組件的源碼，發(fā)現(xiàn)很多地方都有bitmap實現(xiàn)，bitmap圖解如下：


這是一個unsigned char類型，可以看到，共有8位，取值范圍是[0, 255]，如上這個unsigned char的值是255，它能標(biāo)識0~7這些數(shù)字都存在。

同理，如下這個unsigned char類型的值是254，它對應(yīng)的含義是：1~7這些數(shù)字存在，而數(shù)字0不存在：


由此可見，一個unsigned char類型的數(shù)據(jù)，可以標(biāo)識0~7這8個整數(shù)的存在與否。以此類推：

  • 一個unsigned int類型數(shù)據(jù)可以標(biāo)識0~31這32個整數(shù)的存在與否。

  • 兩個unsigned int類型數(shù)據(jù)可以標(biāo)識0~63這64個整數(shù)的存在與否。


顯然，可以推導(dǎo)出來：512MB大小足夠標(biāo)識所有QQ號碼的存在與否，請注意：QQ號碼的理論最大值為2^32 - 1，大概是43億左右。

接下來的問題就很簡單了：用512MB的unsigned int數(shù)組來記錄文件中QQ號碼的存在與否，形成一個bitmap，比如：

bitmapFlag[123] = 1bitmapFlag[567] = 1bitmapFlag[123] = 1bitmapFlag[890] = 1實際上就是：
bitmapFlag[123] = 1bitmapFlag[567]?=?1bitmapFlag[890] = 1然后從小到大遍歷所有正整數(shù)(4字節(jié))，當(dāng)bitmapFlag值為1時，就表明該數(shù)是存在的。而且，從上面的過程可以看到，自動實現(xiàn)了去重。顯然，這種方式可以通過騰訊的面試。



擴展練習(xí)一

文件中有40億個互不相同的QQ號碼，請設(shè)計算法對QQ號碼進行排序，內(nèi)存限制1G.?

很顯然，直接用bitmap, 標(biāo)記這40億個QQ號碼的存在性，然后從小到大遍歷正整數(shù)，當(dāng)bitmapFlag的值為1時，就輸出該值，輸出后的正整數(shù)序列就是排序后的結(jié)果。

請注意，這里必須限制40億個QQ號碼互不相同。通過bitmap記錄，客觀上就自動完成了排序功能。


擴展練習(xí)二

文件中有40億個互不相同的QQ號碼，求這些QQ號碼的中位數(shù)，內(nèi)存限制1G.?

我知道，一些刷題經(jīng)驗豐富的人，最開始想到的肯定是用堆或者文件切割，這明顯是犯了本本主義錯誤。直接用bitmap排序，當(dāng)場搞定中位數(shù)。


擴展練習(xí)三

文件中有40億個互不相同的QQ號碼，求這些QQ號碼的top-K，內(nèi)存限制1G.?

我知道，很多人背誦過top-K問題，信心滿滿，想到用小頂堆或者文件切割，這明顯又是犯了本本主義錯誤。直接用bitmap排序，當(dāng)場搞定top-K問題。


擴展練習(xí)四

文件中有80億個QQ號碼，試判斷其中是否存在相同的QQ號碼，內(nèi)存限制1G.?

我知道，一些吸取了經(jīng)驗教訓(xùn)的人肯定說，直接bitmap啊。然而，又一次錯了。根據(jù)容斥原理可知：

因為QQ號碼的個數(shù)是43億左右(理論值2^32 - 1)，所以80億個QQ號碼必然存在相同的QQ號碼。



海量數(shù)據(jù)的問題，要具體問題具體分析，不要眉毛胡子一把抓。有些人完全不刷題，肯定不行。有些人刷題后不加思考，不會變通，也是不行的。好了，先說這么多。我們也會一步一個腳印，爭取每篇文章講清講透一件事，也希望大家閱讀后有所收獲，心情愉快。


本站聲明： 本文章由作者或相關(guān)機構(gòu)授權(quán)發(fā)布，目的在于傳遞更多信息，并不代表本站贊同其觀點，本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者，如若文章內(nèi)容侵犯您的權(quán)益，請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息，不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司，隨著阿維塔和賽力斯的入局，華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字： 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布，該公司與Amazon Web Services （AWS）簽訂了...

關(guān)鍵字： AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V，這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具，可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字： 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運行，同時企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險，如企業(yè)系統(tǒng)復(fù)雜性的增加，頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性，提升韌性，成...

關(guān)鍵字： 亞馬遜 解密 控制平面 BSP

8月30日消息，據(jù)媒體報道，騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字： 騰訊 編碼器 CPU

8月28日消息，今天上午，2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行，華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字： 華為 12nm EDA 半導(dǎo)體

8月28日消息，在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上，華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱，數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字： 華為 12nm 手機 衛(wèi)星通信

要點： 有效應(yīng)對環(huán)境變化，經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措，毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著，戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng)，提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略，塑強核心競爭優(yōu)勢...

關(guān)鍵字： 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日，由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字： VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上，軟通動力信息技術(shù)（集團）股份有限公司（以下簡稱"軟通動力"）與長三角投資（上海）有限...

關(guān)鍵字： BSP 信息技術(shù)
關(guān)閉