小史是一個應屆生，雖然學的是電子專業(yè)，但是自己業(yè)余時間看了很多互聯(lián)網(wǎng)與編程方面的書，一心想進BAT。

今天他就去BAT中的一家面試了。

簡單的自我介紹后，面試官給了小史一個問題。

【面試現(xiàn)場】

題目：我有40億個整數(shù)，再給一個新的整數(shù)，我需要判斷新的整數(shù)是否在40億個整數(shù)中，你會怎么做？

【請教大神】

小史回到學校，把面試的情況和計算機學院的呂老師說了一下。

小史忙拉著呂老師問，為什么我說分8次加載數(shù)據(jù)，面試官會說太慢了呢？

呂老師：哈哈，從磁盤加載數(shù)據(jù)是磁盤io操作，是非常慢的，你每次都要加載這么大的數(shù)據(jù)，還要8次，我估計你找一個數(shù)的時間可以達到分鐘甚至小時級了。

小史：那如果是你，你會怎么辦呢？

呂老師：其實面試官已經(jīng)提示得比較明顯了，他說給你一批機器，就是暗示你可以用分布式算法。你把數(shù)據(jù)分散在8臺機器上，然后來一個新的數(shù)據(jù)，8臺機器一起找，最后再匯總結(jié)果就行了。

小史：這樣的話能快多少？

呂老師：這樣應該能達到秒級。小史，你可以自己分析分析。

小史：我想想……哦，這樣做的話，因為每臺機器都可以一次性把數(shù)據(jù)讀入內(nèi)存，在比較的時候不用來回加載數(shù)據(jù)了，所以可以節(jié)省加載數(shù)據(jù)的開銷！這真是個好辦法。

【更好方案】

呂老師：其實這并不是最好方法，我這還有一種毫秒級的方法，想不想知道啊？

小史：當然想啊，快教教我。

小史：哦，對哦，這樣我就申請40億個位就好了，新的數(shù)轉(zhuǎn)換成一個位，然后判斷一下這個位是0還是1就行了。

呂老師：小史啊，考慮問題要考慮清楚啊，如果是40億個位，那么這40億個位哪些是0，哪些是1呢？來了一個新的數(shù)，怎么判斷是否在40億個位之中？

小史：我想想，對啊，40億個位，40億個數(shù)，那么每個位都是1，這。。。

呂老師：其實你可以想想，32位int的范圍，總共就是2的32次方，大概42億多點。所以你可以申請2的32次方個位。

小史：意思是我把整個整數(shù)范圍都覆蓋了，哦，對哦。這樣一來，就可以做了，1代表第一個位，2代表第二個位，2的32次方代表最后一個位。40億個數(shù)中，存在的數(shù)就在相應的位置1，其他位就是0。

呂老師：沒錯，那來了一個新的數(shù)呢？

小史：新的數(shù)就去找相應的位，比如來了一個1234，就找一下第1234位，如果是1就存在，是0就不存在啦。

呂老師：沒錯，那么這樣的話，需要多大內(nèi)存呢？

小史：我想想啊，2的32次方個位，相當于2的29次方個字節(jié)，哇，才500MB，真是節(jié)省了不少內(nèi)存呢。

小史：這么厲害的算法，你是怎么想到的？

呂老師：其實這是一種非常有名的大數(shù)據(jù)算法，叫位圖法，英文名叫bitmap。顧名思義，就是用位來表示狀態(tài)，從而節(jié)省空間。明天正好我有一節(jié)課，就講位圖法，你可以來聽一聽。

【呂老師的課】

第二天，呂老師開始上課，他一開始就拋出了小史遇到的面試題。

呂老師：同學們，這道題是BAT公司的一道面試題，大家有什么思路嗎？

話音剛落，蛋哥就站起來回答。蛋哥是呂老師最得意的門生，以思維活躍著稱。

蛋哥：我覺得可以這樣。首先，32位int的范圍是42億，40億整數(shù)中肯定有一些是連續(xù)的，我們可以先對數(shù)據(jù)進行一個外部排序，然后用一個初始的數(shù)和一個長度構(gòu)成一個數(shù)據(jù)結(jié)構(gòu)，來表示一段連續(xù)的數(shù)，舉個例子。

如果數(shù)據(jù)是1 2 3 4 6 7……這種的，那么可以用(1,4)和(6,2)來表示，這樣一來，連續(xù)的數(shù)都變成了2個數(shù)表示。

來了一個新數(shù)之后，就用二分法進行查找了。

這樣一來，最差情況就是2億多的斷點，也就是2億多的結(jié)構(gòu)體，每個結(jié)構(gòu)體8個字節(jié)，大概16億字節(jié)，1.6GB，在內(nèi)存中可以放下。

呂老師：嗯，非常好，不僅給出了方案，還能主動分析空間和可行性。

小史聽完后深感佩服，問題的解決方法絕對不止一種，只要肯動腦筋，即使沒有學過bitmap算法，也能有別的方法來解決問題。

【課后】

下課后，小史又找到呂老師。

呂老師：但是你的理解能力還是很強的，很多東西一聽就懂，這可不是誰都能做到的。

多多關(guān)注這個公眾號，多看一看一線互聯(lián)網(wǎng)面試現(xiàn)場，我相信你一定有收獲的。

面試現(xiàn)場是互聯(lián)網(wǎng)偵察推出的一個新的板塊，旨在回放真實的面試過程，并對面試題進行全面解析，提供多種思路，比較優(yōu)劣，希望對大家的面試有所幫助。

PS：這道題是小編面百度時碰到的一個問題，多年后自己做面試官，也喜歡用這道題考查候選人。