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

　　3、一個大的含有50M個URL的記錄，一個小的含有500個URL的記錄，找出兩個記錄里相同的URL。

　　回答：

　　首先使用包含500個url的文件創建一個hash_set。

　　然后遍歷50M的url記錄，如果url在hash_set中，則輸出此url并從hash_set中刪除這個url。

　　所有輸出的url就是兩個記錄里相同的url。

　　4、海量日志數據，提取出某日訪問百度次數最多的那個IP。

　　回答：

　　IP地址最多有2^32=4G種取值可能，所以不能完全加載到內存中。

　　可以考慮分而治之的策略，按照IP地址的hash(IP)%1024值，將海量日志存儲到1024個小文件中。每個小文件最多包含4M個IP地址。

　　對于每個小文件，可以構建一個IP作為key，出現次數作為value的hash_map，并記錄當前出現次數最多的1個IP地址。

　　有了1024個小文件中的出現次數最多的IP，我們就可以輕松得到總體上出現次數最多的IP。

　　5、有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。如何按照query的頻度排序?

　　回答：

　　1)讀取10個文件，按照hash(query)%10的結果將query寫到對應的文件中。這樣我們就有了10個大小約為1G的文件。任意一個query只會出現在某個文件中。

　　2)對于1)中獲得的10個文件，分別進行如下操作

　　-利用hash_map(query，query_count)來統計每個query出現的次數。

　　-利用堆排序算法對query按照出現次數進行排序。

　　-將排序好的query輸出的文件中。

　　這樣我們就獲得了10個文件，每個文件中都是按頻率排序好的query。

　　3)對2)中獲得的10個文件進行歸并排序，并將最終結果輸出到文件中。

　　6、螞蟻爬桿問題

　　有一根27厘米長的細木桿，在第3厘米，7厘米，11厘米，17厘米，23厘米這五個位置上各有一只螞蟻，木桿很細，不能同時通過兩只螞蟻，開始時，螞蟻的頭朝向左還是右是任意的，他們只會朝前走或掉頭，但不會后退，當兩只螞蟻相遇后，螞蟻會同時掉頭朝反方向走，假設螞蟻們每秒鐘可以走1厘米的距離。求所有螞蟻都離開木桿的最小時間和最大時間。

　　答案：

　　兩只螞蟻相遇后，各自掉頭朝相反方向走。如果我們不考慮每個螞蟻的具體身份，這和兩只螞蟻相遇后，打個招呼繼續向前走沒有什么區別。

　　所有螞蟻都離開木桿的最小時間為

　　max(min(3,27-3),min(7,27-7), min(11,27-11), min(17,27-17),min(23,27-23))=11

　　所有螞蟻都離開木桿的最大時間為

　　max(max(3,27-3),max(7,27-7), max(11,27-11), max(17,27-17),max(23,27-23))=24

　　7、當在瀏覽器中輸入一個url后回車，后臺發生了什么?比如輸入url后，你看到了百度的首頁，那么這一切是如何發生的呢?

　　回答：

　　簡單來說有以下步驟：

　　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從登陸到退出會向一個日志文件中記下登陸時間和退出時間，要求寫一個算法統計一天中論壇的用戶在線分布，取樣粒度為秒。

　　回答：

　　一天總共有360024=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]。

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