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

　　9、三個警察和三個囚徒的過河問題

　　三個警察和三個囚徒共同旅行。一條河擋住了去路，河邊有一條船，但是每次只能載2人。存在如下的危險：無論在河的哪邊，當囚徒人數多于警察的人數時，將有警察被囚徒殺死。問題：請問如何確定渡河方案，才能保證6人安全無損的過河。

　　回答：警察囚徒過去，警察回來

　　囚徒囚徒過去，囚徒回來

　　警察警察過去，警察囚徒回來

　　警察警察過去，囚徒回來

　　囚徒囚徒過去，囚徒回來

　　囚徒囚徒過去

　　10、從300萬字符串中找到最熱門的10條

　　搜索的輸入信息是一個字符串，統計300萬輸入信息中的最熱門的前10條，我們每次輸入的一個字符串為不超過255byte，內存使用只有1G。請描述思想，寫出算法(c語言)，空間和時間復雜度。

　　答案：

　　300萬個字符串最多(假設沒有重復，都是最大長度)占用內存3M1K/4=0.75G。所以可以將所有字符串都存放在內存中進行處理。

　　可以使用key為字符串(事實上是字符串的hash值)，值為字符串出現次數的hash來統計每個每個字符串出現的次數。并用一個長度為10的數組/鏈表來存儲目前出現次數最多的10個字符串。

　　這樣空間和時間的復雜度都是O(n)。

　　11、如何找出字典中的兄弟單詞。給定一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么定義b是a的兄弟單詞。現在給定一個字典，用戶輸入一個單詞，如何根據字典找出這個單詞有多少個兄弟單詞?

　　答案：

　　使用hash_map和鏈表。

　　首先定義一個key，使得兄弟單詞有相同的key，不是兄弟的單詞有不同的key。例如，將單詞按字母從小到大重新排序后作為其key，比如bad的key為abd，good的key為dgoo。

　　使用鏈表將所有兄弟單詞串在一起，hash_map的key為單詞的key，value為鏈表的起始地址。

　　開始時，先遍歷字典，將每個單詞都按照key加入到對應的鏈表當中。當需要找兄弟單詞時，只需求取這個單詞的key，然后到hash_map中找到對應的鏈表即可。

　　這樣創建hash_map時時間復雜度為O(n)，查找兄弟單詞時時間復雜度是O(1)。

　　12、找出數組中出現次數超過一半的數，現在有一個數組，已知一個數出現的次數超過了一半，請用O(n)的復雜度的算法找出這個數。

　　答案1：

　　創建一個hash_map，key為數組中的數，value為此數出現的次數。遍歷一遍數組，用hash_map統計每個數出現的次數，并用兩個值存儲目前出現次數最多的數和對應出現的次數。

　　這樣可以做到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為正且未知。現在第一個空間的數被誤設置為-1。已經知道被修改的數不是最小的。請找出被修改的數字是多少。

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

　　回答：

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

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

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

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