百度筆試題及答案解析-百度筆試題及答案解析

1、百度筆試題及答案-百度筆試題及答【各位讀友，本文僅供參考，望各位讀 者知悉，如若喜歡或者需要本文，可點 擊下載下載本文，謝謝！】祝人家工作順利】百度java筆試題（含答案）更多面試題， 百度面試筆試題解答答案 專家回答: 第一題 簡評 百度的主要業(yè)務是搜索，搜索的基本原理如下1編寫爬蟲程序到互聯(lián)網(wǎng)上抓取網(wǎng)頁海量的網(wǎng)頁。2將抓取來的網(wǎng)頁通過抽取，定的格式保存在能快速檢索的文件系統(tǒng)3把用戶輸入的字符串進行拆分成關鍵字去文件系統(tǒng)中查詢并返回結果。由以3 點可見，字符串的分析，抽取在搜索引擎中的地位是何等重要。因此，百度的筆試面試題中，出現(xiàn)這樣的題就變得理所當然了。以下是該題的 java 實現(xiàn)，代碼如

2、下： 程序代碼 程序代碼import *;import *;import *;/* * author tzy * 在下測試通過 */public class FileNameStat private String srcPath;/ 要統(tǒng)計的文件路徑private Map statMap;/ 用于統(tǒng)計的 mappublic FileNameStat(StringsrcPath)=srcPath; 軟件開發(fā)網(wǎng)statMap=new TreeMap();/* 獲得要統(tǒng)計的 URL 的文件名 */publicStringgetFileName(String urlString)URL url=nul

3、l;String filePath=null;String fileName=null;try url=new URL(urlString);filePath=();int index=0;if (index=( “/ ”)!=-1)fileName=(index+1);elsefileName=catch(MalformedURLExceptione)return fileName;/* 統(tǒng)計指定文件名的個數(shù) */public void stat(String filename)Integer count=null;if(filename)!=null) count=(Integer)(fi

4、lename);count=new Integer()+1);else count=new Integer(1);(filename,count);/* 統(tǒng)計的主方法 */Iterator it=().iterator();FileNotFoundException,IOExceptionBufferedReader bfin=newBufferedReader(new FileReader();String temp=null;while(temp=()!=null) stat(getFileName(temp);/* 輸出統(tǒng)計結果 */ public void result()while(

5、)entry=()();().equals()?”空文件名” :() +的個數(shù)是” + ();public static voidmain(Stringargs) throws ExceptionFileNameStatfns=newFileNameStat( “);/ 指定成待統(tǒng)計文件();();第二題 簡評： 這道題也與百度的業(yè)務有關，百度現(xiàn)在除了搜索外，還有貼吧，知道，博 社區(qū)化，包括前不久宣布進軍電子商務 領域，搜索之外的這些產品，其主要功 能的實現(xiàn)主要是對數(shù)據(jù)庫的操作?？偷戎匾a品。同時也在積極的探索此，想進入百度，也需要對數(shù)據(jù)庫有 定的認識。 實現(xiàn)思路及數(shù)據(jù)庫設計：1 ，該論壇主要

6、有兩個實體對象， 用戶和 帖子 ;對于帖子對象，有一個問題：的帖子是否應該跟主題帖子存放在同 個表里?考慮到每天更新 10 萬帖子，說明帖子數(shù)比較多，為了方便主題的呈現(xiàn)，我般都把主題貼和回帖分別放在不同的 表中，把主題貼和回帖分開可以提高查 詢效率 （300 萬的訪問量每天 ）。2，按照 1 中的思路， 該論壇由兩個對象 （用戶和帖子 ）變成三個實體對象，別是用戶，主題帖子，復帖子 ;3，述三個對象存在三個關系，別是：用戶 - 主題帖，一個用戶可以發(fā)個或多個帖子，一個帖子對應一個用戶（一對多關系 ），題帖 -復帖：一個主題有 0 個或多個回復帖子，一個回復帖子對應個主題 （一對多關系 ）;用戶

7、-復貼：個用戶可以個或多個帖，一個帖子對應一個用戶 （對多關系 ）。還存在對回復貼的回復，這個考慮用 fatherId 來表示。4，由于三個關系 “用戶 - 主題帖，題帖 -復貼” 都是對多關系，根據(jù)表設計一般原則，可 以將這兩個關系獨立建立表，也可以不 另外建表而將一對多的關系體現(xiàn)在實體表中;然而，表間的連接查詢是非常耗資 源的，所以應盡量減少表間連接，那么 對三個關系不應該分別建表，而是把用 戶的 id 作為主題表和回帖表的外鍵，把題貼 id 作為回帖表的外鍵。5，鑒于以上考慮， 該論壇的三個表如下所示表名： t_user_info （ 用戶信息表 ）字段名 類型 缺省值中文含義 約束 備

8、注id Int用戶編號PRIAuto_incrementName Varchar(30)用戶名Email Varchar(50)Phone Varchar(30)Addr Varchar(200)其他字段略， 根據(jù)需要添加 表名：main_content_info ( 主題帖信息表 )字段名 類型 缺省值 中文含義 約束 備注id Int貼 編 號 PRIAuto_incrementTitle Varchar(200)發(fā)帖標題Content Text 發(fā)帖內容UserID Int用戶編號外鍵其他字段略，根據(jù)需要添加表名：sub_content_info (復貼信息表）字段名 類型缺省值 中文含

9、義約束 備注idInt貼 編 號 PRIAuto_incrementTitle Varchar(200)發(fā)帖標題ContentText發(fā)帖內容UserIDInt用戶編號FatherIDInt父編號MainIDInt題帖編號外鍵其他字段略，根據(jù)需要添加6，符合范式分析：述表中每個字段不可再分，首先滿足 1NF;然后數(shù)據(jù)庫表中的每個實例或行都是可以被惟一地區(qū)分 (id) ，不存在部分依 賴，因此滿足 2NF;t_user_info （ 用 戶 信 息 表 ） 和main_content_info（主題帖信息表 ）不存在任何傳遞依賴，至少屬于 BCNF;但是 sub_content_info （回復

10、貼信息表)不滿足3NF,因為存在如下傳遞依id->FatherID,FatherID->MainID。范式并不是越高越好，sub_content_info 表只滿足 2NF 卻更有效率，也是當今論壇較主流的設計。第三題 簡評： 如何對海量數(shù)據(jù)進行快速檢索，這是搜索引擎的必需考慮的問題。這又涉及到數(shù)據(jù)結構和算法。因此，要想進入百度，就必須熟悉一些基本的算法和數(shù)據(jù)結構。思路及解決方案如下：1: 設計用 TRIE 樹實現(xiàn)關鍵詞到其對應 id 的快速詞典查找TRIE 樹的每一個節(jié)點為一個包含256 個元素的數(shù)組，同時指針指向其下級節(jié)點點定義如下：struct trienodeint id;

11、struct trienode *child;TRIENODE;如果 TRIE 樹的某個節(jié)點的指針為NULL ，說明從跟節(jié)點到當前節(jié)點的路徑 構成文件 B 中的一個關鍵詞，在其節(jié)點的 id 保存該關鍵詞的 id;如果指針不為 NULL ，則 id 對應為 0 或 者一個無窮大的整數(shù)，標志從根節(jié)點到當前節(jié)點的路徑不是一個完整的關鍵詞。將關鍵詞轉化為二進制無符號 char型數(shù)組，即對于漢字等雙字節(jié)字符視為 兩個無符號 char 型整數(shù)，每個元素的取值范圍在 0 到 255 之2：生成文件 b 的 TRIE 樹 步驟 1 ：依次讀取文件 b 的每一行，對每一行執(zhí)行步驟 2 到步驟 5步驟 2：讀取關

12、鍵詞 id 和關鍵詞，令為 key步驟 3：依次讀取 key 的每一個字 符，對每一個字符，執(zhí)行步驟 4;步驟 4：如果該字符對應的指針為NULL ，則創(chuàng)建其兒子節(jié)點 ;步驟 5：為當前節(jié)點的對應字符 id置為關鍵詞 id3：根據(jù) A 文件生成 C 文件 步驟 1：依次讀取文件 A 的每一行，對每一行執(zhí)行步驟 2 到步驟 5步驟 2：分別獲取當前行關鍵詞、 ip地址和時間步驟 3 ：令關鍵詞 key=c1c2.cm對 c1 到 cm 每個字符，執(zhí)行步驟 4步驟 4：獲取根節(jié)點的第 c1 個元素指針，轉移到節(jié)點 node1 ，根據(jù) node1 的第 c2 個元素指針，轉移到 node2.根據(jù) n

13、odem 的第 cm 個元素，獲取關鍵詞的 id步驟 5：往文件c格式為關鍵詞的 id 、ip 地址和時間生成文件B的TRIE樹過程時間復雜度為 O(n*m) ，其中 n 為文件 b 行數(shù)，m 為文件 b 關鍵詞的最大長度。 TRIE 的 空間復雜度為 O(n*m) ，n 和 m 含義同，但由于實際應用中關鍵詞之間可能 會有很多前綴相同現(xiàn)象，所以實際耗費 空間并不會很高。生成 C 文件的時間復雜度同樣為O(n*m) ，n 為文件 a 行數(shù)， m 為文件 a關鍵詞的最大長度， 因為有了 TRIE 樹之 后，給定一個關鍵詞獲得其 id 的時間復 雜度為關鍵詞長度。生成 C 文件的過程除了 TRIE

14、 樹空間外基本不需要太多額 外的空間，空間復雜度為 O(1) ，由于系 統(tǒng)有 1G 的可用內存， TRIE 占用的空間 在幾十兆到 200M 之間 (與關鍵詞集合有關)，因此本方法完全可行。更多面試題，百度網(wǎng)上筆試題及答編程： 1 編程： 用 C 語言實現(xiàn)一個revert 函數(shù)，它的功能是將輸入的字符串在原串上倒序 后返。 編程： 2 編*src,size_t n) 。 memmove函數(shù)的功能是拷貝 src 所指的內存內容前 n 個字到 dest 所指的 地址。 英文拼寫糾錯： 3 英文拼寫糾錯：在用戶輸入英文單詞時，經(jīng)常發(fā)生錯誤，我們需要 對其進行糾錯。 假設已 經(jīng)有一個包含了 正確英文單

15、詞的詞典，請你設計一個拼 寫糾錯的程序。 請描述你解決這個問題 的思路； 請給出主要的處理流程， 算法， 以及算法的復雜度； 請描述可能的改 進。搜索引擎會通過日志文件把用戶每次檢 索使用的所有檢索串都記錄下來， 每個查詢串的長度為 1-255 字節(jié)。假設目前有一千萬個記錄， 這些查詢串的重復度比較高， 雖然總數(shù)是 1萬，但如果除去重復后，不超過 3 百萬個。一個 查 詢串的重復度越高，說明查詢它的用戶 越多，也就是越熱門。請你統(tǒng)計最熱 的 10 個查詢串，要求使用的內存不能 超過 1G。 請描述你解決這個問題的思路； 請給出主要的處理流程，算法，以 合并 給定一個字符串的集合，格式如：及算法

16、的復雜度。 集合合并：5 集合aaa bbb ccc ， bbb ddd ，eee fff ， ggg ， ddd hhh 要求將其中交集不 為空的集合合并， 要求合并完成后 的集 合之間無交集，例如上例應輸出 aaa bbb ccc ddd hhh ， eee fff ， ggg請描述你解決這個問題的思路； 請給出要的處理流程，算法，以及算法的復 雜度 請描述可能的改進。/ char *revert(char * str) int n=strlen(str); int i=0; char c; for(i=0;i c=str; str=str; str=c; return str; / 2v

17、oid * memmove(void *dest,constvoid*src,size_tn) assert(dest!=0)&&(src!=0); char * temp=(char * )dest; char * ss=(char * )src; int i=0; for(;i *temp =*ss ; /3 題 (1) 思路 : 字典以字母鍵樹組織，在用戶輸入同時匹配 (2) 流程 :!1!每輸入一個字母： 沿字典樹向下一層，a)若可以順利下行，則繼續(xù)至結束，給出結果；b)若該處不能匹配，糾錯處理， 給出拼寫建議 ,繼續(xù)至 a)；算法 : 1.在字典中查找單詞 1.在字典

18、中查找單詞 字典采用 27 叉樹組織 ,每個點對應一個字母 ,查找就是一個字母個字母匹配 .算法時間就是單詞的長度NIR!1!k. 2.糾錯算法 2.糾錯算法 情況 :當輸入的最后一個字母不能匹配時就提示出錯!1!簡化出錯處理，動態(tài)提示 可能 處理方 法：(a)當前字母前缺少了一個字母：搜索 樹上兩層到當前的匹配作為建議； (b)當前字母拼寫錯誤：當前字母的鍵盤相 鄰作為提示； 根據(jù)分析字典特征和用戶 單詞已輸入部分選擇 (a),(b) 處理 復雜性 分析：影響算法的效率主要是字典的實 現(xiàn)與糾錯處理(a)字典的實現(xiàn)已有成熟 的算法，改進不大，也不會成為瓶頸； (b)糾錯策略要簡單有效 ,如前述

19、情況，是線性復雜度； (3) 改進 (3) 改進 策略選擇 最是重要，可以采用統(tǒng)計學習的方法改/ 4 題 (1)思路 (1)思路：用哈希做思路 (2) 首先逐次讀入查詢串，算哈希值，保存在內存數(shù)組中，同時統(tǒng)計頻度 簡單不過了。哈希的設計是關鍵選出前十的頻度，取出對應的日 志串，心、/ / 5 題 思路：先將集合按照大 小排列后 ,優(yōu)先考慮小的集合是否與大的集合有交 思路 集。有就合并，如果小 集合與所有其他集合都沒有交集，則獨 立。獨立的集合 在下一輪的比較中不用 考慮。這樣就可以盡量減少字符串的比 較次數(shù)。當所有 集合都獨立的時候，就 終止處理流程： 處理流程：1.將集合按照大小排序，組成集

20、合合并待處理列表 2.選擇最小的集合，找出與之有交集的集 合，如果有，合并之；如果無，則與 其 它集合是獨立集合， 從待處理列表 中刪 除。 3.重復直到待處理列表為空 算法： 算法： 1。將集合按照大小從小到大排序,組成待處理的集合列表。 2。取出待處理集合列表中最小的集合，對于集合 的每個元素，依次在其他集合中搜索是 否有此元素存在： 1> 若存在，則將此 小集合與大集合合并，并根據(jù)大小插入 對應的位置 。轉 3。 2> 若不存在，則在該集合中取下一個元素。如果無下 個元素，即所有元素都 不存在于其他集 合。則表明此集合獨立，從待處理集合加入結 果集合列表。轉3。 3。如果待處

21、理集合列表不為空， 轉2。 如果待處理集合列表為空，成功退 出，則結果集合列表就是最終的輸出。算法復雜度分析： 算法復雜度分析： 假 設集合的個數(shù)為 n ，最大的集合元素為m 排 序 的 時 間 復 雜 度 可 以 達 到n*log(n) 然后對于元素在其他集合中 查找，最壞情況下為 *m 查找一個 集合 是否與其他集合有交集的最壞情況是m*m*(n-1) 合并的時間復雜度不會超過查找集合有交集的最壞情況。所以最 終最壞時間復雜度為 O(m*m*n*n) 需 要說明 的是：此算法的平均時間復雜度會很低， 因為無論是查找還是合 需要說明的是 并，都是處于最壞情況的概率很小，而 且排序后優(yōu)先用最小

22、集合作為判斷是否 獨立的對象，優(yōu)先與最大的集合進行比較，這些都最大的回避了最壞情況。 (3)可能的改進： (3) 可能的改進：可能的改進 首先可以實現(xiàn)將每個集合里面的 字符串按照字典序進行排列，這樣就可 以 將查找以及合并的效率增高。另外， 可能采取恰當?shù)臄?shù)據(jù)結構也可以將查找 以 及合并等操作的效率得到提高。百度 11 月 4 日網(wǎng)上筆試題及答案 （僅供百度 11 月 4 日網(wǎng)上筆試題及答案編程：1 用 C 語言實現(xiàn)一個 revert 函數(shù)，它的 功能是將輸入的字符串在原串上倒序后2 編程： 用 C 語 言 實 現(xiàn) 函 數(shù) void *memmove(void *dest,const void

23、 *src,size_tn)。 memmove函數(shù)的功能是拷貝 src所指的內存內容前 n 個字節(jié) 到 dest 所指的地址3 英文拼寫糾錯：在用戶輸入英文單詞時，經(jīng)常發(fā)生錯誤，我們需要對其進行糾錯。假設已經(jīng)有個包含了正確英文單詞的詞典，請你設計 個拼寫糾錯 的程序。請描述你解決這個問題的思路； 請給出主要的處理流程，算法，以及算 法的復雜度； 請描述可能的改進。4 尋找熱門查詢： 搜索引擎會通過日志文件把用戶每次檢 索使用的所有檢索串都記錄下來，每個 查詢串 的長度為 1-255 字節(jié)。假設目前有萬個記錄，這些查詢串的重復度比較高，雖然總數(shù)是1萬，但如果除去重復后，不超過3 百萬個 。一個查

24、詢串的重復度越高，說明查詢 它的用戶越多， 也就是越熱門。 請你統(tǒng)計最熱門的 10 個 查詢串，要求使用的內存不能超過 1G 。請描述你解決這個問題的思路； 請給出主要的處理流程，算法，以及算 法的復雜度。5 集合合并：給定一個字符串的集合，格式如：aaa bbb ccc ， bbb ddd ，eee fff ，ggg ， ddd hhh要求將其中交集不為空的集合合并，要 求合并完成后的集合之間無交集，例如例應輸出aaa bbb ccc ddd hhh ， eee fff ，ggg請描述你解決這個問題的思路； 請給出主要的處理流程，算法，以及算 法的復雜度請描述可能的改進。/1 char *r

25、evert(char * str) int n=strlen(str);int i=0;char c;for(i=0;i c=str;str=str;str=c;return str;/ void * memmove(void *dest,const void *src,size_t n) assert(dest!=0)&&(src!=0);char * temp=(char * )dest;char * ss=(char * )src;int i=0;for(;i *temp+=*ss+;return temp;/ /字典以字母鍵樹組織，在用戶輸入同時 匹配流程:每輸入一個字

26、母： 沿字典樹向下一層，a）若可以順利下行，則繼續(xù)至結束，給出結果；b） 若該處不能匹配，糾錯處理，給出拼NIR!1!寫建議 ,繼續(xù)至 a）；算法:1. 在字典中查找單詞字典采用 27 叉樹組織 ,每個節(jié)點對應個字母 ,查找就是一個字母個字母匹配 .算法時間就是單詞的長度NIR!1!k.2. 糾錯算法情況 :當輸入的最后一個字母不能匹配時NIR!1!就提示出錯 ,簡化出錯處理，動態(tài)提示可能 處理方法 :(a)當前字母前缺少了一個字母：搜索樹 (b) 當前字母拼寫錯誤：當前字母的鍵盤兩層到當前的匹配作為建議；NIR!1!相鄰作為提示； 根據(jù)分析字典特征和用戶單詞已輸入部 分選擇 (a),(b) 處理復雜性分析：影響算法的效率主要是字 典的實現(xiàn)與糾錯處理字典的實現(xiàn)已有成熟的算法， 改進不大， 也不會成為瓶頸；(b) 糾錯策略要簡單有效 ,如前述情況，是線性復雜度；(3)改進策略選擇最是重要，可以采用 統(tǒng)計學習的方法改進。/ /用哈希做(2)首先逐次讀入查詢串，算哈希值，保存 在內存數(shù)組中，同時統(tǒng)計頻度 選出前十的頻度，取出對應的日志串， 簡單不過了。哈希的設計是關鍵。/ /思路：先將集合按照大小排列后 ,優(yōu)先考慮小的集合是否與大的集合有交集。有就合并，如果小集合