14、設(shè)計DNS服務(wù)器中cache的數(shù)據(jù)結(jié)構(gòu)。

　　要求設(shè)計一個DNS的Cache結(jié)構(gòu)，要求能夠滿足每秒5000以上的查詢，滿足IP數(shù)據(jù)的快速插入，查詢的速度要快。(題目還給出了一系列的數(shù)據(jù)，比如：站點數(shù)總共為5000萬，IP地址有1000萬，等等)

　　回答：

　　DNS服務(wù)器實現(xiàn)域名到IP地址的轉(zhuǎn)換。

　　每個域名的平均長度為25個字節(jié)(估計值)，每個IP為4個字節(jié)，所以Cache的每個條目需要大概30個字節(jié)。

　　總共50M個條目，所以需要1.5G個字節(jié)的空間�？梢苑胖迷趦�(nèi)存中。(考慮到每秒5000次操作的限制，也只能放在內(nèi)存中。)

　　可以考慮的數(shù)據(jù)結(jié)構(gòu)包括hash_map，字典樹，紅黑樹等等。

　　15、找出給定字符串對應(yīng)的序號。

　　序列Seq=[a,b,…z,aa,ab…az,ba,bb,…bz,…,za,zb,…zz,aaa,…]類似與excel的排列，任意給出一個字符串s=[a-z]+(由a-z字符組成的任意長度字符串)，請問s是序列Seq的第幾個。

　　回答：

　　注意到每滿26個就會向前進(jìn)一位，類似一個26進(jìn)制的問題。

　　比如ab，則位置為261+2;

　　比如za，則位置為2626+1;

　　比如abc，則位置為26261+262+3;

　　16、找出第k大的數(shù)字所在的位置。寫一段程序，找出數(shù)組中第k大小的數(shù)，輸出數(shù)所在的位置。例如{2，4，3，4，7}中，第一大的數(shù)是7，位置在4。第二大、第三大的數(shù)都是4，位置在1、3隨便輸出哪一個均可。

　　答案：

　　先找到第k大的數(shù)字，然后再遍歷一遍數(shù)組找到它的位置。所以題目的難點在于如何最高效的找到第k大的數(shù)。

　　我們可以通過快速排序，堆排序等高效的排序算法對數(shù)組進(jìn)行排序，然后找到第k大的數(shù)字。這樣總體復(fù)雜度為O(NlogN)。

　　我們還可以通過二分的思想，找到第k大的數(shù)字，而不必對整個數(shù)組排序。從數(shù)組中隨機(jī)選一個數(shù)t，通過讓這個數(shù)和其它數(shù)比較，我們可以將整個數(shù)組分成了兩部分并且滿足，{x,xx,...,t}<{y,yy,...}。

　　在將數(shù)組分成兩個數(shù)組的過程中，我們還可以記錄每個子數(shù)組的大小。這樣我們就可以確定第k大的數(shù)字在哪個子數(shù)組中。

　　然后我們繼續(xù)對包含第k大數(shù)字的子數(shù)組進(jìn)行同樣的劃分，直到找到第k大的數(shù)字為止。

　　平均來說，由于每次劃分都會使子數(shù)組縮小到原來1/2，所以整個過程的復(fù)雜度為O(N)。

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

　　答案：

　　unsigned int的取值范圍是0到2^32-1。我們可以申請連續(xù)的2^32/8=512M的內(nèi)存，用每一個bit對應(yīng)一個unsigned int數(shù)字。首先將512M內(nèi)存都初始化為0，然后每處理一個數(shù)字就將其對應(yīng)的bit設(shè)置為1。當(dāng)需要查詢時，直接找到對應(yīng)bit，看其值是0還是1即可。

　　18、在一個文件中有10G個整數(shù)，亂序排列，要求找出中位數(shù)。內(nèi)存限制為2G。

　　回答：

　　不妨假設(shè)10G個整數(shù)是64bit的。

　　2G內(nèi)存可以存放256M個64bit整數(shù)。

　　我們可以將64bit的整數(shù)空間平均分成256M個取值范圍，用2G的內(nèi)存對每個取值范圍內(nèi)出現(xiàn)整數(shù)個數(shù)進(jìn)行統(tǒng)計。這樣遍歷一邊10G整數(shù)后，我們便知道中數(shù)在那個范圍內(nèi)出現(xiàn)，以及這個范圍內(nèi)總共出現(xiàn)了多少個整數(shù)。

　　如果中數(shù)所在范圍出現(xiàn)的整數(shù)比較少，我們就可以對這個范圍內(nèi)的整數(shù)進(jìn)行排序，找到中數(shù)。如果這個范圍內(nèi)出現(xiàn)的整數(shù)比較多，我們還可以采用同樣的方法將此范圍再次分成多個更小的范圍(256M=2^28，所以最多需要3次就可以將此范圍縮小到1，也就找到了中數(shù))。

　　19、時分秒針在一天之類重合多少次?(24小時)

　　2次

　　而時針和分針重合了22次。

　　20、將多個集合合并成沒有交集的集合。

　　給定一個字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}要求將其中交集不為空的集合合并，要求合并完成后的集合之間無交集，例如上例應(yīng)輸出{aaabbbcccdddhhh}，{eeefff}，{ggg}。

　　(1)請描述你解決這個問題的思路;

　　(2)請給出主要的處理流程，算法，以及算法的復(fù)雜度

　　(3)請描述可能的改進(jìn)。

　　回答：

　　集合使用hash_set來表示，這樣合并時間復(fù)雜度比較低。

　　1、給每個集合編號為0，1，2，3...

　　2、創(chuàng)建一個hash_map，key為字符串，value為一個鏈表，鏈表節(jié)點為字符串所在集合的編號。遍歷所有的集合，將字符串和對應(yīng)的集合編號插入到hash_map中去。

　　3、創(chuàng)建一個長度等于集合個數(shù)的int數(shù)組，表示集合間的合并關(guān)系。例如，下標(biāo)為5的元素值為3，表示將下標(biāo)為5的集合合并到下標(biāo)為3的集合中去。開始時將所有值都初始化為-1，表示集合間沒有互相合并。在集合合并的過程中，我們將所有的字符串都合并到編號較小的集合中去。

　　遍歷第二步中生成的hash_map，對于每個value中的鏈表，首先找到最小的集合編號(有些集合已經(jīng)被合并過，需要順著合并關(guān)系數(shù)組找到合并后的集合編號)，然后將鏈表中所有編號的集合都合并到編號最小的集合中(通過更改合并關(guān)系數(shù)組)。

　　4、現(xiàn)在合并關(guān)系數(shù)組中值為-1的集合即為最終的集合，它的元素來源于所有直接或間接指向它的集合。

　　算法的復(fù)雜度為O(n)，其中n為所有集合中的元素個數(shù)。

　　題目中的例子：

　　0:{aaabbbccc}

　　1:{bbbddd}

　　2:{eeefff}

　　3:{ggg}

　　4:{dddhhh}

　　生成的hash_map，和處理完每個值后的合并關(guān)系數(shù)組分別為

　　aaa:0。[-1,-1,-1,-1,-1]

　　bbb:0,1。[-1,0,-1,-1,-1]

　　ccc:0。[-1,0,-1,-1,-1]

　　ddd:1,4。[-1,0,-1,-1,0]

　　eee:2。[-1,0,-1,-1,0]

　　fff:2。[-1,0,-1,-1,0]

　　ggg:3。[-1,0,-1,-1,0]

　　hhh:4。[-1,0,-1,-1,0]

　　所以合并完后有三個集合，第0，1，4個集合合并到了一起，