2014校園招聘大禮包2013筆試題

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

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

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

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

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