方案3：
與方案1類似，但在做完hash，分成多個文件后，可以交給多個文件來處理，采用分布式的架構(gòu)來處理（比如MapReduce），最后再進(jìn)行合并。
5、 給定a、b兩個文件，各存放50億個url，每個url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？
方案1：可以估計每個文件安的大小為5G×64=320G，遠(yuǎn)遠(yuǎn)大于內(nèi)存限制的4G。所以不可能將其完全加載到內(nèi)存中處理。考慮采取分而治之的方法。
遍歷文件a，對每個url求取hash(url)00，然后根據(jù)所取得的值將url分別存儲到1000個小文件（記為a0,a1,…,a999）中。這樣每個小文件的大約為300M。
遍歷文件b，采取和a相同的方式將url分別存儲到1000小文件（記為b0,b1,…,b999）。這樣處理后，所有可能相同的url都在對應(yīng)的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，不對應(yīng)的小文件不可能有相同的url。然后我們只要求出1000對小文件中相同的url即可。
求每對小文件中相同的url時，可以把其中一個小文件的url存儲到hash_set中。然后遍歷另一個小文件的每個url，看其是否在剛才構(gòu)建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
方案2：如果允許有一定的錯誤率，可以使用Bloom filter，4G內(nèi)存大概可以表示340億bit。將其中一個文件中的url使用Bloom filter映射為這340億bit，然后挨個讀取另外一個文件的url，檢查是否與Bloom filter，如果是，那么該url應(yīng)該是共同的url（注意會有一定的錯誤率）。
Bloom filter日后會在本BLOG內(nèi)詳細(xì)闡述。
6、在2.5億個整數(shù)中找出不重復(fù)的整數(shù)，注，內(nèi)存不足以容納這2.5億個整數(shù)。
方案1：采用2-Bitmap（每個數(shù)分配2bit，00表示不存在，01表示出現(xiàn)一次，10表示多次，11無意義）進(jìn)行，共需內(nèi)存2^32 * 2 bit=1 GB內(nèi)存，還可以接受。然后掃描這2.5億個整數(shù)，查看Bitmap中相對應(yīng)位，如果是00變01，01變10，10保持不變。所描完事后，查看bitmap，把對應(yīng)位是01的整數(shù)輸出即可。
方案2：也可采用與第1題類似的方法，進(jìn)行劃分小文件的方法。然后在小文件中找出不重復(fù)的整數(shù)，并排序。然后再進(jìn)行歸并，注意去除重復(fù)的元素。
7、騰訊面試題：給40億個不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中？
與上第6題類似，我的第一反應(yīng)時快速排序+二分查找。以下是其它更好的方法：
方案1：oo，申請512M的內(nèi)存，一個bit位代表一個unsigned int值。讀入40億個數(shù)，設(shè)置相應(yīng)的bit位，讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在。
方案2：這個問題在《編程珠璣》里有很好的描述，大家可以參考下面的思路，探討一下：
又因為2^32為40億多，所以給定一個數(shù)可能在，也可能不在其中；
這里我們把40億個數(shù)中的每一個用32位的二進(jìn)制來表示
假設(shè)這40億個數(shù)開始放在一個文件中。
然后將這40億個數(shù)分成兩類:
1.最高位為0
2.最高位為1
并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=20億，而另一個>=20億（這相當(dāng)于折半了）；
與要查找的數(shù)的最高位比較并接著進(jìn)入相應(yīng)的文件再查找
再然后把這個文件為又分成兩類:
1.次最高位為0
2.次最高位為1
并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=10億，而另一個>=10億（這相當(dāng)于折半了）；
與要查找的數(shù)的次最高位比較并接著進(jìn)入相應(yīng)的文件再查找。
…….
以此類推，就可以找到了,而且時間復(fù)雜度為O(logn)，方案2完。
附：這里，再簡單介紹下，位圖方法：
使用位圖法判斷整形數(shù)組是否存在重復(fù)
判斷集合中存在重復(fù)是常見編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時我們通常希望少進(jìn)行幾次掃描，這時雙重循環(huán)法就不可取了。
位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個長度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到5就給新數(shù)組的第六個元素置1，這樣下次再遇到5想置位時發(fā)現(xiàn)新數(shù)組的第六個元素已經(jīng)是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這種給新數(shù)組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效率還能提高一倍。
更多詳細(xì)信息，請您微信關(guān)注“計算網(wǎng)”公眾號：
