當前位置：高考升學網(wǎng) > 招聘筆試題 > 正文

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

更新：2023-09-16 00:49:33 高考升學網(wǎng)

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

　　回答：

　　首先使用包含500個url的文件創(chuàng)建一個hash_set。

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

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

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

　　回答：

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

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

　　對于每個小文件，可以構(gòu)建一個IP作為key，出現(xiàn)次數(shù)作為value的hash_map，并記錄當前出現(xiàn)次數(shù)最多的1個IP地址。

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

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

　　回答：

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

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

　　-利用hash_map(query，query_count)來統(tǒng)計每個query出現(xiàn)的次數(shù)。

　　-利用堆排序算法對query按照出現(xiàn)次數(shù)進行排序。

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

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

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

　　6、螞蟻爬桿問題

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

　　答案：

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

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

　　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后回車，后臺發(fā)生了什么?比如輸入url后，你看到了百度的首頁，那么這一切是如何發(fā)生的呢?

　　回答：

　　簡單來說有以下步驟：

　　1、查找域名對應(yīng)的IP地址。這一步會依次查找瀏覽器緩存，系統(tǒng)緩存，路由器緩存，ISPDNS緩存，根域名服務(wù)器。

　　2、向IP對應(yīng)的服務(wù)器發(fā)送請求。

　　3、服務(wù)器響應(yīng)請求，發(fā)回網(wǎng)頁內(nèi)容。

　　4、瀏覽器解析網(wǎng)頁內(nèi)容。

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

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

　　數(shù)據(jù)結(jié)構(gòu)為：

　　[cpp] view plaincopytypedef struct TreeNode

　　{

　　char c;

　　TreeNode leftchild;

　　TreeNode rightchild;

　　}TreeNode;

　　函數(shù)接口為：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個節(jié)點，我們會進行1次函數(shù)調(diào)用;

　　在樹的第1層，有2個節(jié)點，我們可能會進行4次函數(shù)調(diào)用;

　　在樹的第2層，有4個節(jié)點，我們可能會進行16次函數(shù)調(diào)用;

　　....

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

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

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

　　回答：

　　一天總共有360024=86400秒。