騰訊三面:40?億個(gè)?QQ?號(hào)碼如何去重?
今天,我們來聊一道常見的考題,也出現(xiàn)在騰訊面試的三面環(huán)節(jié),非常有意思。具體的題目如下:文件中有40億個(gè)QQ號(hào)碼,請(qǐng)?jiān)O(shè)計(jì)算法對(duì)QQ號(hào)碼去重,相同的QQ號(hào)碼僅保留一個(gè),內(nèi)存限制1G.這個(gè)題目的意思應(yīng)該很清楚了,比較直白。為了便于大家理解,我來畫個(gè)動(dòng)圖玩玩,希望大家喜歡。能否做對(duì)這道題目,很大程度上就決定了能否拿下騰訊的offer,有一定的技巧性,一起來看下吧。在原題中,實(shí)際有40億個(gè)QQ號(hào)碼,為了方便起見,在圖解和敘述時(shí),僅以4個(gè)QQ為例來說明。
方法一:排序
很自然地,最簡(jiǎn)單的方式是對(duì)所有的QQ號(hào)碼進(jìn)行排序,重復(fù)的QQ號(hào)碼必然相鄰,保留第一個(gè),去掉后面重復(fù)的就行。原始的QQ號(hào)為:排序后的QQ號(hào)為:去重就簡(jiǎn)單了:可是,面試官要問你,去重一定要排序嗎?顯然,排序的時(shí)間復(fù)雜度太高了,無(wú)法通過騰訊面試。方法二:hashmap
既然直接排序的時(shí)間復(fù)雜度太高,那就用hashmap吧,具體思路是把QQ號(hào)碼記錄到hashmap中:mapFlag[123]?=?true
mapFlag[567]?=?true
mapFlag[123]?=?true
mapFlag[890]?=?true
由于hashmap的去重性質(zhì),可知實(shí)際自動(dòng)變成了:
mapFlag[123]?=?true
mapFlag[567]?=?true
mapFlag[890]?=?true
很顯然,只有123,567,890存在,所以這也就是去重后的結(jié)果。
方法三:文件切割
顯然,這是海量數(shù)據(jù)問題。看過很多面經(jīng)的求職者,自然想到文件切割的方式,避免內(nèi)存過大。可是,絞盡腦汁思考,要么使用文件間的歸并排序,要么使用桶排序,反正最終是能排序的。既然排序好了,那就能實(shí)現(xiàn)去重了,貌似就萬(wàn)事大吉了。我只能坦白地說,高興得有點(diǎn)早哦。接著,面試官又要問你:這么多的文件操作,效率自然不高啊。顯然,無(wú)法通過騰訊面試。方法四:bitmap
來看絕招!我們可以對(duì)hashmap進(jìn)行優(yōu)化,采用bitmap這種數(shù)據(jù)結(jié)構(gòu),可以順利地同時(shí)解決時(shí)間問題和空間問題。在很多實(shí)際項(xiàng)目中,bitmap經(jīng)常用到。我看了不少組件的源碼,發(fā)現(xiàn)很多地方都有bitmap實(shí)現(xiàn),bitmap圖解如下:這是一個(gè)unsigned char類型,可以看到,共有8位,取值范圍是[0, 255],如上這個(gè)unsigned char的值是255,它能標(biāo)識(shí)0~7這些數(shù)字都存在。同理,如下這個(gè)unsigned char類型的值是254,它對(duì)應(yīng)的含義是:1~7這些數(shù)字存在,而數(shù)字0不存在:由此可見,一個(gè)unsigned char類型的數(shù)據(jù),可以標(biāo)識(shí)0~7這8個(gè)整數(shù)的存在與否。以此類推:- 一個(gè)unsigned int類型數(shù)據(jù)可以標(biāo)識(shí)0~31這32個(gè)整數(shù)的存在與否。
- 兩個(gè)unsigned int類型數(shù)據(jù)可以標(biāo)識(shí)0~63這64個(gè)整數(shù)的存在與否。
bitmapFlag[123]?=?1
bitmapFlag[567]?=?1
bitmapFlag[123]?=?1
bitmapFlag[890]?=?1
實(shí)際上就是:
bitmapFlag[123]?=?1
bitmapFlag[567]?=?1
bitmapFlag[890]?=?1
然后從小到大遍歷所有正整數(shù)(4字節(jié)),當(dāng)bitmapFlag值為1時(shí),就表明該數(shù)是存在的。