當(dāng)前位置:首頁(yè) > 公眾號(hào)精選 > 程序員小灰
[導(dǎ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ì)這道題...


今天,我們來聊一道常見的考題,也出現(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ù)雜度太高了,無法通過騰訊面試。

方法二: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í)際要存40億QQ號(hào)碼,1G的內(nèi)存夠分配這么多空間嗎?顯然不行,無法通過騰訊面試。

方法三:文件切割

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

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

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

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

方法四: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ù)的存在與否。
顯然,可以推導(dǎo)出來:512MB大小足夠標(biāo)識(shí)所有QQ號(hào)碼的存在與否,請(qǐng)注意:QQ號(hào)碼的理論最大值為2^32 - 1,大概是43億左右。

接下來的問題就很簡(jiǎn)單了:用512MB的unsigned int數(shù)組來記錄文件中QQ號(hào)碼的存在與否,形成一個(gè)bitmap,比如:

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ù)是存在的。

而且,從上面的過程可以看到,自動(dòng)實(shí)現(xiàn)了去重。顯然,這種方式可以通過騰訊的面試。

擴(kuò)展練習(xí)一

文件中有40億個(gè)互不相同的QQ號(hào)碼,請(qǐng)?jiān)O(shè)計(jì)算法對(duì)QQ號(hào)碼進(jìn)行排序,內(nèi)存限制1G.

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

請(qǐng)注意,這里必須限制40億個(gè)QQ號(hào)碼互不相同。通過bitmap記錄,客觀上就自動(dòng)完成了排序功能。

擴(kuò)展練習(xí)二

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

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

擴(kuò)展練習(xí)三

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

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

擴(kuò)展練習(xí)四

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

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

因?yàn)镼Q號(hào)碼的個(gè)數(shù)是43億左右(理論值2^32 - 1),所以80億個(gè)QQ號(hào)碼必然存在相同的QQ號(hào)碼。

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

- EOF -


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

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

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

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

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

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

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

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

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

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

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

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

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

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

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

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

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

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

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