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

　　回答：

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

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

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

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

　　回答：

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

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

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

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

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

　　回答：

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

　　2)對(duì)于1)中獲得的10個(gè)文件，分別進(jìn)行如下操作

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

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

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

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

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

　　6、螞蟻爬桿問(wèn)題

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

　　答案：

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

　　所有螞蟻都離開(kāi)木桿的最小時(shí)間為

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

　　所有螞蟻都離開(kāi)木桿的最大時(shí)間為

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

　　7、當(dāng)在瀏覽器中輸入一個(gè)url后回車(chē)，后臺(tái)發(fā)生了什么?比如輸入url后，你看到了百度的首頁(yè)，那么這一切是如何發(fā)生的呢?

　　回答：

　　簡(jiǎn)單來(lái)說(shuō)有以下步驟：

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

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

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

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

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

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

　　數(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兩棵樹(shù)相等當(dāng)且僅當(dāng)RootA->c==RootB-->c,而且A和B的左右子樹(shù)相等或者左右互換相等。

　　遞歸方法：

　　[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;

　　}

　　時(shí)間復(fù)雜度：

　　在樹(shù)的第0層，有1個(gè)節(jié)點(diǎn)，我們會(huì)進(jìn)行1次函數(shù)調(diào)用;

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

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

　　....

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

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

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

　　回答：

　　一天總共有360024=86400秒。

　　定義一個(gè)長(zhǎng)度為86400的整數(shù)數(shù)組intdelta[86400]，每個(gè)整數(shù)對(duì)應(yīng)這一秒的人數(shù)變化值，可能為正也可能為負(fù)。開(kāi)始時(shí)將數(shù)組元素都初始化為0。

　　然后依次讀入每個(gè)用戶的登錄時(shí)間和退出時(shí)間，將與登錄時(shí)間對(duì)應(yīng)的整數(shù)值加1，將與退出時(shí)間對(duì)應(yīng)的整數(shù)值減1。

　　這樣處理一遍后數(shù)組中存儲(chǔ)了每秒中的人數(shù)變化情況。

　　定義另外一個(gè)長(zhǎng)度為86400的整數(shù)數(shù)組intonline_num[86400]，每個(gè)整數(shù)對(duì)應(yīng)這一秒的論壇在線人數(shù)。

　　假設(shè)一天開(kāi)始時(shí)論壇在線人數(shù)為0，則第1秒的人數(shù)online_num[0]=delta[0]。第n+1秒的人數(shù)online_num[n]=online_num[n-1]+delta[n]。

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