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

　　回答：

　　簡單來說有以下步驟：

　　1、查找域名對應的IP地址。這一步會依次查找瀏覽器緩存，系統緩存，路由器緩存，ISPDNS緩存，根域名服務器。

　　2、向IP對應的服務器發送請求。

　　3、服務器響應請求，發回網頁內容。

　　4、瀏覽器解析網頁內容。

　　當然，由于網頁可能有重定向，或者嵌入了圖片，AJAX，其它子網頁等等，這4個步驟可能反復進行多次才能將最終頁面展示給用戶。

　　8、判斷兩棵樹是否相等，請實現兩棵樹是否相等的比較，相等返回1，否則返回其他值，并說明算法復雜度。

　　數據結構為：

　　[cpp] view plaincopytypedef struct TreeNode

　　{

　　char c;

　　TreeNode *leftchild;

　　TreeNode *rightchild;

　　}TreeNode;

　　函數接口為：int CompTree(TreeNode* tree1,TreeNode* tree2);

　　注：A、B兩棵樹相等當且僅當RootA->c==RootB-->c,而且A和B的左右子樹相等或者左右互換相等。

　　遞歸方法：

　　[cpp] view plaincopybool CompTree(TreeNode *tree1, TreeNode *tree2)

　　{

　　if(tree1 == NULL && tree2 == NULL)

　　return true;

　　if(tree1 == NULL || tree2 == NULL)

　　return false;

　　if(tree1->c != tree2->c)

　　return false;

　　if( (CompTree(tree1->leftchild, tree2->leftchild) && CompTree(tree1->rightchild, tree2->rightchild)) || CompTree(tree1->leftchild, tree2->rightchild) && CompTree(tree1->rightchild, tree2->leftchild))

　　return true;

　　}

　　時間復雜度：

　　在樹的第0層，有1個節點，我們會進行1次函數調用;

　　在樹的第1層，有2個節點，我們可能會進行4次函數調用;

　　在樹的第2層，有4個節點，我們可能會進行16次函數調用;

　　....

　　在樹的第x層，有2^x個節點，我們可能會進行(2^x)^2次函數調用;

　　所以假設總節點數為n，則算法的復雜度為O(n^2)。

　　騰訊面試題：求一個論壇的在線人數，假設有一個論壇，其注冊ID有兩億個，每個ID從登陸到退出會向一個日志文件中記下登陸時間和退出時間，要求寫一個算法統計一天中論壇的用戶在線分布，取樣粒度為秒。

　　回答：

　　一天總共有3600*24=86400秒。

　　定義一個長度為86400的整數數組intdelta[86400]，每個整數對應這一秒的人數變化值，可能為正也可能為負。開始時將數組元素都初始化為0。

　　然后依次讀入每個用戶的登錄時間和退出時間，將與登錄時間對應的整數值加1，將與退出時間對應的整數值減1。

　　這樣處理一遍后數組中存儲了每秒中的人數變化情況。

　　定義另外一個長度為86400的整數數組intonline_num[86400]，每個整數對應這一秒的論壇在線人數。

　　假設一天開始時論壇在線人數為0，則第1秒的人數online_num[0]=delta[0]。第n+1秒的人數online_num[n]=online_num[n-1]+delta[n]。

　　這樣我們就獲得了一天中任意時間的在線人數。

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

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

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

　　囚徒囚徒過去，囚徒回來

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

　　警察警察過去，囚徒回來

　　囚徒囚徒過去，囚徒回來

　　囚徒囚徒過去

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

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

　　答案：

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

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

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

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

　　答案：

　　使用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統計每個數出現的次數，并用兩個值存儲目前出現次數最多的數和對應出現的次數。

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