1、 更多課程傳送門： HYPERLINK /explore?utm_source=weibo&utm_medium=weibo&utm_campaign=YWGxiaoyuanword 點(diǎn)這里 百度2012實(shí)習(xí)生校園招聘筆試題閱讀次數(shù): 42次 發(fā)布時(shí)間: 2012-05-08 10:39:44發(fā)布人: pengzl來(lái)源: 網(wǎng)絡(luò)轉(zhuǎn)載1、給一個(gè)單詞a，如果通過(guò)交換單詞中字母的順序可以得到另外的單詞b，那么b是a的兄弟單詞，比如的單詞army和mary互為兄弟單詞。現(xiàn)在要給出一種解決方案，對(duì)于用戶輸入的單詞，根據(jù)給定的字典找出輸入單詞有哪些兄弟單詞。請(qǐng)具體說(shuō)明數(shù)據(jù)結(jié)構(gòu)和查詢流程，要求時(shí)間和空間效率盡

2、可能地高。字典樹(shù)的典型應(yīng)用2、系統(tǒng)中維護(hù)了若干數(shù)據(jù)項(xiàng)，我們對(duì)數(shù)據(jù)項(xiàng)的分類可以分為三級(jí)，首先我們按照一級(jí)分類方法將數(shù)據(jù)項(xiàng)分為A、B、C.若干類別，每個(gè)一級(jí)分類方法產(chǎn)生的類別又可以按照二級(jí)分類方法分為a、b、c.若干子類別，同樣，二級(jí)分類方法產(chǎn)生的類別又可以按照是三級(jí)分類方法分為i、ii、iii.若干子類別，每個(gè)三級(jí)分類方法產(chǎn)生的子類別中的數(shù)據(jù)項(xiàng)從1開(kāi)始編號(hào)。我們需要對(duì)每個(gè)數(shù)據(jù)項(xiàng)輸出日志，日志的形式是key_value對(duì)，寫(xiě)入日志的時(shí)候，用戶提供三級(jí)類別名稱、數(shù)據(jù)項(xiàng)編號(hào)和日志的key，共五個(gè)key值，例如，write_log（A,a,i,1,key1），獲取日志的時(shí)候，用戶提供三級(jí)類別名稱、數(shù)據(jù)項(xiàng)

3、編號(hào)，共四個(gè)key值，返回對(duì)應(yīng)的所有的key_value對(duì)，例如get_log（A,a,i,1,key1），請(qǐng)描述一種數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)這些日志，并計(jì)算出寫(xiě)入日志和讀出日志的時(shí)間復(fù)雜度。3、C和C+中如何動(dòng)態(tài)分配和釋放內(nèi)存？他們的區(qū)別是什么？malloc/free和new/delete的區(qū)別4、數(shù)組al0,mid-1和almid,num-1是各自有序的，對(duì)數(shù)組al0,num-1的兩個(gè)子有序段進(jìn)行merge，得到al0,num-1整體有序。要求空間復(fù)雜度為O(1)。注：ali元素是支持b.html-x.html.-NULL。問(wèn)：對(duì)于爬蟲(chóng)分別從/x1.html和/x2.html兩個(gè)入口開(kāi)始獲得兩個(gè)單向

4、鏈表，得到這兩個(gè)單向鏈表后，如何判斷他們是否抓取到了相同的URL？（假設(shè)頁(yè)面URL上百億，存儲(chǔ)資源有限，無(wú)法用hash方法判斷是否包含相同的URL）請(qǐng)先描述相應(yīng)的算法，再給出相應(yīng)的代碼實(shí)現(xiàn)。（只需給出判斷方法代碼，無(wú)需爬蟲(chóng)代碼）兩個(gè)單向鏈表的相交問(wèn)題。算法與程序設(shè)計(jì)二、4、有一種結(jié)構(gòu)如下圖所示，它由層的嵌套組成，一個(gè)父層中只能包含垂直方向上或者是水平方向上并列的層，例如，層1可以包含2、3、4三個(gè)垂直方向上的層，層2可以包含5和6兩個(gè)水平方向的層，在空層中可以包含數(shù)據(jù)節(jié)點(diǎn)，所謂的空層是指不包含子層的層，每個(gè)空層可以包含若干個(gè)數(shù)據(jù)節(jié)點(diǎn)，也可以一個(gè)都不包含。在這種結(jié)構(gòu)上面，我們從垂直方向上劃一條線

5、，我們約定每一個(gè)子層中我們只能經(jīng)過(guò)一個(gè)數(shù)據(jù)節(jié)點(diǎn)，在這種情況下，每條線可以經(jīng)過(guò)多個(gè)數(shù)據(jù)節(jié)點(diǎn)，也可以不經(jīng)過(guò)任何數(shù)據(jù)節(jié)點(diǎn)，例如，線1經(jīng)過(guò)了3、5、8三個(gè)數(shù)據(jù)節(jié)點(diǎn)，線2只經(jīng)過(guò)了14個(gè)數(shù)據(jù)節(jié)點(diǎn)。（1）給出函數(shù)，實(shí)現(xiàn)判斷兩個(gè)數(shù)據(jù)節(jié)點(diǎn)，是否可能同時(shí)被線劃中，給出具體的代碼。（2）給出函數(shù)，輸出所有一條線可以劃中的數(shù)據(jù)節(jié)點(diǎn)序列， 可以給出偽代碼實(shí)現(xiàn)。思路：（1）判斷兩個(gè)數(shù)所屬的同一層次的相同矩形框的下一層次矩形框是水平排列的還是垂直排列的，垂直排列在能在一條線上，水平排列則不能。（2）用回溯算法求出所有在一條直線上的字符串，用兩字符串是否在同一直線上進(jìn)行剪枝操作。系統(tǒng)設(shè)計(jì)題1、相信大家都使用過(guò)百度搜索框的suggestion功能，百度搜索框中的suggestion提示功能如何實(shí)現(xiàn)？請(qǐng)給出實(shí)現(xiàn)思路和主要的數(shù)據(jù)結(jié)構(gòu)、算法。有什么優(yōu)化思路可以使得時(shí)間和空間效率最高？應(yīng)用字典樹(shù)來(lái)求前綴和TOP K對(duì)熱詞進(jìn)行統(tǒng)計(jì)排序2、兩個(gè)200G大小的文件A和B，AB文件里內(nèi)容均為無(wú)序的一行一個(gè)