騰訊三面：40億個QQ號碼如何去重？
我們來聊一道常見的考題，也出現(xiàn)在騰訊面試的三面環(huán)節(jié)，非常有意思。具體的題目如下：
文件中有40億個QQ號碼，請?jiān)O(shè)計(jì)算法對QQ號碼去重，相同的QQ號碼僅保留一個，內(nèi)存限制1G.?
這個題目的意思應(yīng)該很清楚了，比較直白。為了便于大家理解，我來畫個動圖玩玩，希望大家喜歡。
能否做對這道題目，很大程度上就決定了能否拿下騰訊的offer，有一定的技巧性，一起來看下吧。
在原題中，實(shí)際有40億個QQ號碼，為了方便起見，在圖解和敘述時，僅以4個QQ為例來說明。
方法一：排序
很自然地，最簡單的方式是對所有的QQ號碼進(jìn)行排序，重復(fù)的QQ號碼必然相鄰，保留第一個，去掉后面重復(fù)的就行。
原始的QQ號為：
排序后的QQ號為：
去重就簡單了：
可是，面試官要問你，去重一定要排序嗎？顯然，排序的時間復(fù)雜度太高了，無法通過騰訊面試。
方法二：hashmap
既然直接排序的時間復(fù)雜度太高，那就用hashmap吧，具體思路是把QQ號碼記錄到hashmap中：
mapFlag[123] = truemapFlag[567] = truemapFlag[123] = truemapFlag[890] = true
由于hashmap的去重性質(zhì)，可知實(shí)際自動變成了：
mapFlag[123] = truemapFlag[567] = truemapFlag[890] = true
很顯然，只有123，567，890存在，所以這也就是去重后的結(jié)果。
可是，面試官又要問你了：實(shí)際要存40億QQ號碼，1G的內(nèi)存夠分配這么多空間嗎？顯然不行，無法通過騰訊面試。
方法三：文件切割
顯然，這是海量數(shù)據(jù)問題?？催^很多面經(jīng)的求職者，自然想到文件切割的方式，避免內(nèi)存過大。
可是，絞盡腦汁思考，要么使用文件間的歸并排序，要么使用桶排序，反正最終是能排序的。
既然排序好了，那就能實(shí)現(xiàn)去重了，貌似就萬事大吉了。我只能坦白地說，高興得有點(diǎn)早哦。
接著，面試官又要問你：這么多的文件操作，效率自然不高啊。顯然，無法通過騰訊面試。
方法四：bitmap
來看絕招！我們可以對hashmap進(jìn)行優(yōu)化，采用bitmap這種數(shù)據(jù)結(jié)構(gòu)，可以順利地同時解決時間問題和空間問題。
在很多實(shí)際項(xiàng)目中，bitmap經(jīng)常用到。我看了不少組件的源碼，發(fā)現(xiàn)很多地方都有bitmap實(shí)現(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ù)的存在與否。
bitmapFlag[123] = 1bitmapFlag[567] = 1bitmapFlag[123] = 1bitmapFlag[890] = 1
bitmapFlag[123] = 1bitmapFlag[567] = 1bitmapFlag[890] = 1
擴(kuò)展練習(xí)一
擴(kuò)展練習(xí)二
擴(kuò)展練習(xí)三
擴(kuò)展練習(xí)四
最后推薦一個Go+語言的發(fā)布會，有興趣可以看看。
推薦閱讀:
入門:?最全的零基礎(chǔ)學(xué)Python的問題? |?零基礎(chǔ)學(xué)了8個月的Python??|?實(shí)戰(zhàn)項(xiàng)目?|學(xué)Python就是這條捷徑
干貨:爬取豆瓣短評，電影《后來的我們》?|?38年NBA最佳球員分析?|? ?從萬眾期待到口碑撲街！唐探3令人失望? |?笑看新倚天屠龍記?|?燈謎答題王?｜用Python做個海量小姐姐素描圖?｜碟中諜這么火，我用機(jī)器學(xué)習(xí)做個迷你推薦系統(tǒng)電影
趣味:彈球游戲? |?九宮格? |?漂亮的花?|?兩百行Python《天天酷跑》游戲!
AI:?會做詩的機(jī)器人?|?給圖片上色?|?預(yù)測收入?|?碟中諜這么火，我用機(jī)器學(xué)習(xí)做個迷你推薦系統(tǒng)電影
小工具:?Pdf轉(zhuǎn)Word，輕松搞定表格和水??！?|?一鍵把html網(wǎng)頁保存為pdf！|??再見PDF提取收費(fèi)！?|?用90行代碼打造最強(qiáng)PDF轉(zhuǎn)換器，word、PPT、excel、markdown、html一鍵轉(zhuǎn)換?|?制作一款釘釘?shù)蛢r機(jī)票提示器！?｜60行代碼做了一個語音壁紙切換器天天看小姐姐！｜
年度爆款文案
6).30個Python奇淫技巧集?
點(diǎn)閱讀原文，看200個Python案例！