百度軟件工程師面試題大全(3)

　　這樣可以做到O(n)的時間復雜度和O(n)的空間復雜度，滿足題目的要求。

　　但是沒有利用“一個數出現的次數超過了一半”這個特點。也許算法還有提高的空間。

　　答案2：

　　使用兩個變量A和B，其中A存儲某個數組中的數，B用來計數。開始時將B初始化為0。

　　遍歷數組，如果B=0，則令A等于當前數，令B等于1;如果當前數與A相同，則B=B+1;如果當前數與A不同，則令B=B-1。遍歷結束時，A中的數就是要找的數。

　　這個算法的時間復雜度是O(n)，空間復雜度為O(1)。

　　13、找出被修改過的數字

　　n個空間(其中n<1M)，存放a到a+n-1的數，位置隨機且數字不重復，a為正且未知?，F在第一個空間的數被誤設置為-1。已經知道被修改的數不是最小的。請找出被修改的數字是多少。

　　例如：n=6，a=2，原始的串為5,3,7,6,2,4?，F在被別人修改為-1,3,7,6,2,4?，F在希望找到5。

　　回答：

　　由于修改的數不是最小的，所以遍歷第二個空間到最后一個空間可以得到a的值。

　　a到a+n-1這n個數的和是total=na+(n-1)n/2。

　　將第二個至最后一個空間的數累加獲得sub_total。

　　那么被修改的數就是total-sub_total。

　　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，則位置為26*1+2;

　　比如za，則位置為26*26+1;

　　比如abc，則位置為26*26*1+26*2+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，表示集合間沒有互相合并。在集合合并的過程中，我們將所有的字符串都合并到編號較小的集合中去。

原文轉自：http://www.anti-gravitydesign.com