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

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

　　回答：

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

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

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

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

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

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

　　回答：

　　注意到每滿26個(gè)就會(huì)向前進(jìn)一位，類似一個(gè)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隨便輸出哪一個(gè)均可。

　　答案：

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

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

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

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

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

　　平均來(lái)說(shuō)，由于每次劃分都會(huì)使子數(shù)組縮小到原來(lái)1/2，所以整個(gè)過(guò)程的復(fù)雜度為O(N)。

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

　　答案：

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

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

　　回答：

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

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

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

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

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

　　2次

　　而時(shí)針和分針重合了22次。

　　20、將多個(gè)集合合并成沒有交集的集合。

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

　　(1)請(qǐng)描述你解決這個(gè)問題的思路;

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

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

　　回答：

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

　　1、給每個(gè)集合編號(hào)為0，1，2，3...

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

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

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

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

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

　　題目中的例子：

　　0:{aaabbbccc}

　　1:{bbbddd}

　　2:{eeefff}

　　3:{ggg}

　　4:{dddhhh}

　　生成的hash_map，和處理完每個(gè)值后的合并關(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]

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