1. 給40億個不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中？

引出Bitmap
舉一個小例子，有一個無序整形數(shù)組{8,4,9}，也就占用內(nèi)存34=12字節(jié)，這很正常，但如果有1億個這樣的數(shù)呢？1億4/(102410241024)=0.372G左右。如果對該數(shù)據(jù)做查找，那內(nèi)存壓力很大，我們想要高性能地解決這個問題，就得引出Bitmap。

Bitmap概念
一個byte占8個bit，如果每一個bit的值就是有或沒有，也就是二進(jìn)制的0或1。那就可用bit的0或1代表某數(shù)組值有或沒有。0代表該數(shù)值沒有出現(xiàn)過，1代表該數(shù)組值出現(xiàn)過。具體如下圖：

bitmap.png

那1億的數(shù)據(jù)現(xiàn)在所需的空間0.372G/32，一個原占32bit的數(shù)據(jù)現(xiàn)在只占用1bit，節(jié)省了不少內(nèi)存。

應(yīng)用和代碼
疑問：一個數(shù)怎么快速定位它的索引，也就是說搞清楚byte[index]的索引號index是多少，位置號position是哪一位。

例子：例如add(14)。14已經(jīng)超出byte[0]的映射范圍，在byte[1]的范圍內(nèi)。那怎么快速定位它的索引號？如果找到它的索引號，又怎么找到它的位置號？Index(N)代表N的索引號，Position(N)代表N的位置號。

公式：
Index(N) = N/8 = N >> 3;
Position(N) = N%8 = N & 7;

例子：
add(int num)向Bitmap里add數(shù)據(jù)該怎么辦?
上面已分析了，add的目的是為了將所在的位置從0變成1，其他位置不變。
（圖中間，不是“作與操作”，是“作或操作”?！癮|=b”表示a和b作或操作，結(jié)果賦給a。）

代碼：

public void add(int num)
{
    int index=num>>3;
    int position=num&7;
    byte[index] |= 1<<position;//如圖，將1左移position位，使目標(biāo)位置1
}

總結(jié)： Bitmap是簡單快速的數(shù)據(jù)結(jié)構(gòu)，常用于空間的優(yōu)化。
解題：一個bit位代表一個unsigned int值。讀入40億個數(shù)，設(shè)置相應(yīng)的bit位。由于2^{32=42.9+億，那么2}32bit才能存下40億個數(shù)，也就需要2^32=4Gb=0.5GB=512M內(nèi)存。讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在。

2. 在2.5億個整數(shù)找出不重復(fù)的整數(shù)，內(nèi)存不足以容納著2.5億個整數(shù)。

2-Bitmap
每個數(shù)分配2bit，00表示不存在，01表示出現(xiàn)一次，10表示多次，其他同Bitmap。

方案1：使用2-Bitmap
每個數(shù)分配2bit，00表示不存在，01表示出現(xiàn)一次，10表示多次，11無意義。然后遍歷修改Bitmap中的對應(yīng)位，如果是00則變01，01則變10，10則保持不變。遍歷修改完后，最后遍歷輸出對應(yīng)位是01的整數(shù)。

#include <cstdio>
#include <iostream>
using namespace std;
 
unsigned char bitmap[1005];
 
//x表示一個整數(shù)，num表示bitmap中已經(jīng)擁有x的個數(shù)
//由于我們只能用2個bit來存儲x的個數(shù)，所以num的個數(shù)最多為3
void set(int x,int num){
    int m = x >> 2;
    int n = x & 3;
 
    //將x對于為值上的個數(shù)值先清零，但是有要保證其他位置上的數(shù)不變
    bitmap[m] &= ~((0x3<<(2*n)) & 0xFF);
    //重新對x的個數(shù)賦值
    bitmap[m] |= ((num&3)<<(2*n) & 0xFF);
}
 
void clear(int x){
    int m = x >> 2;
    int n = x & 3;
    bitmap[m] &= ~((0x3<<(2*n)) & 0xFF);
}
 
unsigned char get(int x){
    int m = x >> 2;
    int n = x & 3;
 
    return (bitmap[m] & (0x3<<(2*n))) >> (2*n);
}
 
void add(int x){
    int num = get(x);
    set(x,num+1);

方案2：分治法
先將2.5億個數(shù)劃分成 2.5億/2 個組，每個組里2個整數(shù)，再在每個組里去掉重復(fù)的整數(shù)后進(jìn)行排序，然后再進(jìn)行歸并，最終便可得到只出現(xiàn)過一次的整數(shù)。

3. top k 問題: 海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。

主要問題：
IP地址最多有2^32=4G種取值情況，所以不能完全加載到內(nèi)存中處理

解決方案：

采用映射的方法，比如模1000，把整個大文件映射為1000個小文件

再找出每個小文中出現(xiàn)頻率最大的IP（可以采用hash_map進(jìn)行頻率統(tǒng)計，然后再找出頻率最大的幾個）及相應(yīng)的頻率。然后再在這1000個最大的IP中，找出那個頻率最大的IP

4.統(tǒng)計最熱門的10個查詢串

搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)。
假設(shè)目前有一千萬個記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個。一個查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。），請你統(tǒng)計最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G。

主要問題：

內(nèi)存不能超過1G，一千萬條記錄，每條記錄是255Byte，很顯然要占據(jù)2.375G內(nèi)存，這個條件就不滿足要求了。

解決方案：多路歸并排序

外部排序指的是大文件的排序，當(dāng)待排序的文件很大時，無法將整個文件的所有記錄同時調(diào)入內(nèi)存進(jìn)行排序，只能將文件存放在外存，這種排稱為外部排序。外部排序的過程主要是依據(jù)數(shù)據(jù)的內(nèi)外存交換和“內(nèi)部歸并”兩者結(jié)合起來實現(xiàn)的。

外部排序最常用的算法是多路歸并排序，即將原文件分解成多個能夠一次性裝入內(nèi)存的部分分別把每一部分調(diào)入內(nèi)存完成排序。然后，對已經(jīng)排序的子文件進(jìn)行歸并排序。

我們可以采用歸并排序，因為歸并排序有一個比較好的時間復(fù)雜度O(NlgN)。排完序之后我們再對已經(jīng)有序的Query文件進(jìn)行遍歷，統(tǒng)計每個Query出現(xiàn)的次數(shù)，再次寫入文件中。綜合分析一下，排序的時間復(fù)雜度是O(NlgN)，而遍歷的時間復(fù)雜度是O(N)

總體時間復(fù)雜度：O(N+NlgN)=O（NlgN）。

5.有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。

分析：
（1）分文件（在外存中進(jìn)行）

順序讀文件中，對于每個詞x，取hash(x)%5000，然后按照該值存到5000個小文件（記為x0,x1,...x4999）中。這樣每個文件大概是200k左右。
如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M。

（2）文件內(nèi)排序（內(nèi)存中）
對每個小文件，統(tǒng)計每個文件中出現(xiàn)的詞以及相應(yīng)的頻率（可以采用trie樹/hash_map等），并取出出現(xiàn)頻率最大的100個詞（可以用含100個結(jié)點(diǎn)的最小堆），并把100個詞及相應(yīng)的頻率存入文件，這樣又得到了5000個文件。

（3）歸并
下一步就是把這5000個文件進(jìn)行歸并（類似與歸并排序）的過程了。

6.有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復(fù)。要求你按照query的頻度排序。

（1）讀取文件，重復(fù)的合并到一個文件中

順序讀取10個文件，按照hash(query)%10的結(jié)果將query寫入到另外10個文件（記為）中。這樣新生成的文件每個的大小大約也1G（假設(shè)hash函數(shù)是隨機(jī)的）。

（2）排序
找一臺內(nèi)存在2G左右的機(jī)器，依次對用hash_map(query, query_count)來統(tǒng)計每個query出現(xiàn)的次數(shù)。利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序。將排序好的query和對應(yīng)的query_cout輸出到文件中。這樣得到了10個排好序的文件（記為）。

（3）歸并
對這10個文件進(jìn)行歸并排序（內(nèi)排序與外排序相結(jié)合）。