百度軟件工程師筆試題和面試題答案大全(四)

　　14、設計DNS服務器中cache的數據結構。

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

　　回答：

　　DNS服務器實現域名到IP地址的轉換。

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

　　總共50M個條目，所以需要1.5G個字節的空間。可以放置在內存中。(考慮到每秒5000次操作的限制，也只能放在內存中。)

　　可以考慮的數據結構包括hash_map，字典樹，紅黑樹等等。

　　15、找出給定字符串對應的序號。

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

　　回答：

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

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

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

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

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

　　答案：

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

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

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

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

　　然后我們繼續對包含第k大數字的子數組進行同樣的劃分，直到找到第k大的數字為止。

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

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

　　答案：

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

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

　　回答：

　　不妨假設10G個整數是64bit的。

　　2G內存可以存放256M個64bit整數。

　　我們可以將64bit的整數空間均分成256M個取值范圍，用2G的內存對每個取值范圍內出現整數個數進行統計。這樣遍歷一邊10G整數后，我們便知道中數在那個范圍內出現，以及這個范圍內總共出現了多少個整數。

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

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

　　2次

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

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

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

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

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

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

　　回答：

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

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

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

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

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

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

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

　　題目中的例子：

　　0:{aaabbbccc}

　　1:{bbbddd}

　　2:{eeefff}

　　3:{ggg}

　　4:{dddhhh}

　　生成的hash_map，和處理完每個值后的合并關系數組分別為

　　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個集合合并到了一起，