❶ 騰訊三面：40億個QQ號碼如何去重
今天，我們來聊一道常見的考題，也出現在騰訊面試的三面環節，非常有意思。具體的題目如下：
文件中有40億個QQ號碼，請設計演算法對QQ號碼去重，相同的QQ號碼僅保留一個，內存限制1G.
這個題目的意思應該很清楚了，比較直白。為了便於大家理解，我來畫個動圖玩玩，希望大家喜歡。
能否做對這道題目，很大程度上就決定了能否拿下騰訊的offer，有一定的技巧性，一起來看下吧。
在原題中，實際有40億個QQ號碼，為了方便起見，在圖解和敘述時，僅以4個QQ為例來說明。
方法一：排序
很自然地，最簡單的方式是對所有的QQ號碼進行排序，重復的QQ號碼必然相鄰，保留第一個，去掉後面重復的就行。
原始的QQ號為：
排序後的QQ號為：
去重就簡單了：
可是，面試官要問你，去重一定要排序嗎？顯然，排序的時間復雜度太高了，無法通過騰訊面試。
方法二：hashmap
既然直接排序的時間復雜度太高，那就用hashmap吧，具體思路是把QQ號碼記錄到hashmap中：
mapFlag[123] = truemapFlag[567] = truemapFlag[123] = truemapFlag[890] = true
由於hashmap的去重性質，可知實際自動變成了：
mapFlag[123] = truemapFlag[567] = truemapFlag[890] = true
很顯然，只有123，567，890存在，所以這也就是去重後的結果。
可是，面試官又要問你了：實際要存40億QQ號碼，1G的內存夠分配這么多空間嗎？顯然不行，無法通過騰訊面試。
方法三：文件切割
顯然，這是海量數據問題。看過很多面經的求職者，自然想到文件切割的方式，避免內存過大。
可是，絞盡腦汁思考，要麼使用文件間的歸並排序，要麼使用桶排序，反正最終是能排序的。
既然排序好了，那就能實現去重了，貌似就萬事大吉了。我只能坦白地說，高興得有點早哦。
接著，面試官又要問你：這么多的文件操作，效率自然不高啊。顯然，無法通過騰訊面試。
方法四：bitmap
來看絕招！我們可以對hashmap進行優化，採用bitmap這種數據結構，可以順利地同時解決時間問題和空間問題。
在很多實際項目中，bitmap經常用到。我看了不少組件的源碼，發現很多地方都有bitmap實現，bitmap圖解如下：
這是一個unsigned char類型，可以看到，共有8位，取值范圍是[0, 255]，如上這個unsigned char的值是255，它能標識0~7這些數字都存在。
同理，如下這個unsigned char類型的值是254，它對應的含義是：1~7這些數字存在，而數字0不存在：
由此可見，一個unsigned char類型的數據，可以標識0~7這8個整數的存在與否。以此類推：
一個unsigned int類型數據可以標識0~31這32個整數的存在與否。
兩個unsigned int類型數據可以標識0~63這64個整數的存在與否。
顯然，可以推導出來：512MB大小足夠標識所有QQ號碼的存在與否，請注意：QQ號碼的理論最大值為2^32 - 1，大概是43億左右。
接下來的問題就很簡單了：用512MB的unsigned int數組來記錄文件中QQ號碼的存在與否，形成一個bitmap，比如：
bitmapFlag[123] = 1bitmapFlag[567] = 1bitmapFlag[123] = 1bitmapFlag[890] = 1
實際上就是：
bitmapFlag[123] = 1bitmapFlag[567] = 1bitmapFlag[890] = 1
然後從小到大遍歷所有正整數(4位元組)，當bitmapFlag值為1時，就表明該數是存在的。而且，從上面的過程可以看到，自動實現了去重。顯然，這種方式可以通過騰訊的面試。