百度筆試題及答案

1、百度筆試題及答案更多面試題，百度面試筆試題解答答案專家回答：第一題簡(jiǎn)評(píng)百度的主要業(yè)務(wù)是搜索，搜索的基本原理如下1 編寫爬蟲程序到互聯(lián)網(wǎng)上抓取網(wǎng)頁(yè)海量的網(wǎng)頁(yè)。2 將抓取來的網(wǎng)頁(yè)通過抽取， 以一定的格式保存在能快速檢索的文件系統(tǒng)中。3 把用戶輸入的字符串進(jìn)行拆分成關(guān)鍵字去文件系統(tǒng)中查詢并返回結(jié)果。由以上 3 點(diǎn)可見，字符串的分析，抽取在搜索引擎中的地位是何等重要。因此，百度的筆試面試題中，出現(xiàn)這樣的題就變得理所當(dāng)然了。以下是該題的 java 實(shí)現(xiàn)，代碼如下：程序代碼程序代碼import java.*;import java.io.*;import java.util.*;/* * author t

2、zy *在j2sdk1.4.2下測(cè)試通過*/public class FileNameStatprivate String srcPath;/要統(tǒng)計(jì)的文件路徑private Map statMap;/ 用于統(tǒng)計(jì)的 public FileNameStat(String srcPath) mapthis.srcPath=srcPath;軟件開發(fā)網(wǎng).mscto.statMap=new TreeMap();/*獲得要統(tǒng)計(jì)的 URL的文件名 */public String getFileName(String urlString)URL url=null;String filePath=null;Str

3、ing fileName=null;tryurl=new URL(urlString);filePath=url.getPath();int index=0;if (index=filePath.lastIndexOf("/")!=-1)fileName=filePath.substring(index+1);elsefileName=""catch(MalformedURLException e)return fileName;/*統(tǒng)計(jì)指定文件名的個(gè)數(shù) */public void stat(String filename)Integer count=n

4、ull;if(statMap.get(filename)!=null)count=(Integer)statMap.get(filename);count=new Integer(Value()+1);elsecount=new Integer(1);statMap.put(filename,count);/*統(tǒng)計(jì)的主方法 */public void start() throwsFileNotFoundException,IOExceptionBufferedReader bfin=new BufferedReader(new FileReader(this.srcPath)

5、;String temp=null;while(temp=bfin.readLine()!=null)stat(getFileName(temp);/*輸出統(tǒng)計(jì)結(jié)果 */public void result()Iterator it=statMap.entrySet().iterator();while(it.hasNext()Map.Entry entry=(Map.Entry)(it.next();System.out.println(entry.getKey().equals("")?"空文件名":entry.getKey() + "的個(gè)

6、數(shù)是 " + entry.getValue(); public static void main(String args) throws ExceptionFileNameStatfns=new FileNameStat("src.txt");/指定成待統(tǒng)計(jì)文件fns.start();fns.result();第二題簡(jiǎn)評(píng)：這道題也與百度的業(yè)務(wù)有關(guān)，百度現(xiàn)在除了搜索外，還有貼吧，知道，博客等重要產(chǎn)品。 同時(shí)也在積極的探索社區(qū)化，包括前不久宣布進(jìn)軍電子商務(wù)領(lǐng)域， 搜索之外的這些產(chǎn)品， 其主要功能的實(shí)現(xiàn)主要是對(duì)數(shù)據(jù)庫(kù)的操作。 因此，想進(jìn)入百度，也需要對(duì)數(shù)據(jù)庫(kù)有一定的認(rèn)識(shí)

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

8、主題有0 個(gè)或多個(gè)回復(fù)帖子，一個(gè)回復(fù)帖子對(duì)應(yīng)一個(gè)主題 ( 一對(duì)多關(guān)系 );用戶 - 回復(fù)貼：一個(gè)用戶可以回0 個(gè)或多個(gè)帖，一個(gè)帖子對(duì)應(yīng)一個(gè)用戶 ( 一對(duì)多關(guān)系 ) 。還存在對(duì)回復(fù)貼的回復(fù)，這個(gè)考慮用fatherId來表示。4 ，由于三個(gè)關(guān)系 “用戶 - 主題帖，主題帖 - 回復(fù)帖，用戶 - 回復(fù)貼” 都是一對(duì)多關(guān)系，根據(jù)表設(shè)計(jì)一般原則，可以將這兩個(gè)關(guān)系獨(dú)立建立表，也可以不另外建表而將一對(duì)多的關(guān)系體現(xiàn)在實(shí)體表中;然而，表間的連接查詢是非常耗資源的，所以應(yīng)盡量減少表間連接，那么對(duì)三個(gè)關(guān)系不應(yīng)該分別建表，而是把用戶的id 作為主題表和回帖表的外鍵，把主題貼id 作為回帖表的外鍵。5 ，鑒于以上考慮，

9、該論壇的三個(gè)表如下所示表名： t_user_info (用戶信息表 )字段名類型 缺省值中文含義約束 備注id Int用戶編號(hào) PRI Auto_incrementName Varchar(30)用戶名Email Varchar(50)Phone Varchar(30)Addr Varchar(200)其他字段略，根據(jù)需要添加表名： main_content_info (主題帖信息表 )字段名類型 缺省值中文含義約束 備注id Int貼編號(hào) PRI Auto_incrementTitle Varchar(200)發(fā)帖標(biāo)題Content Text發(fā)帖內(nèi)容UserID Int用戶編號(hào)外鍵其他字段略

10、，根據(jù)需要添加表名： sub_content_info (回復(fù)貼信息表 )字段名類型 缺省值中文含義約束 備注id Int貼編號(hào) PRI Auto_incrementTitle Varchar(200)發(fā)帖標(biāo)題Content Text發(fā)帖內(nèi)容UserID Int用戶編號(hào)外鍵FatherID Int父編號(hào)MainID Int主題帖編號(hào)外鍵其他字段略，根據(jù)需要添加6 ，符合范式分析：上述表中每個(gè)字段不可再分，首先滿足1NF;然后數(shù)據(jù)庫(kù)表中的每個(gè)實(shí)例或行都是可以被惟一地區(qū)分(id) ，不存在部分依賴，因此滿足2NF;t_user_info (用戶信息表 ) 和 main_content_info (

11、主題帖信息表) 不存在任何傳遞依賴，至少屬于BF;但是 sub_content_info (回復(fù)貼信息表 ) 不滿足 3NF,因?yàn)榇嬖谌缦聜鬟f依賴： id->FatherID,FatherID->MainID。范式并不是越高越好， sub_content_info表只滿足 2NF卻更有效率，也是當(dāng)今論壇較主流的設(shè)計(jì)。第三題簡(jiǎn)評(píng)：如何對(duì)海量數(shù)據(jù)進(jìn)行快速檢索， 這是搜索引擎的必需考慮的問題。這又涉及到數(shù)據(jù)結(jié)構(gòu)和算法。 因此，要想進(jìn)入百度，就必須熟悉一些基本的算法和數(shù)據(jù)結(jié)構(gòu)。 思路及解決方案如下：1: 設(shè)計(jì)用 TRIE 樹實(shí)現(xiàn)關(guān)鍵詞到其對(duì)應(yīng) id 的快速詞典查找TRIE樹的每一個(gè)節(jié)點(diǎn)為一

12、個(gè)包含256 個(gè)元素的數(shù)組，同時(shí)指針指向其下一級(jí)節(jié)點(diǎn)節(jié)點(diǎn)定義如下：struct trienodeint id;struct trienode *child256;TRIENODE;如果 TRIE 樹的某個(gè)節(jié)點(diǎn)的指針為 NULL，說明從跟節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑構(gòu)成文件 B 中的一個(gè)關(guān)鍵詞，在其節(jié)點(diǎn)的 id 保存該關(guān)鍵詞的 id; 如果指針不為 NULL，則 id 對(duì)應(yīng)為 0 或者一個(gè)無窮大的整數(shù)，標(biāo)志從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑不是一個(gè)完整的關(guān)鍵詞。將關(guān)鍵詞轉(zhuǎn)化為二進(jìn)制無符號(hào) char 型數(shù)組，即對(duì)于漢字等雙字節(jié)字符視為兩個(gè)無符號(hào) char 型整數(shù)，每個(gè)元素的取值范圍在0 到 255 之間。2 ：生成

13、文件 b 的 TRIE 樹步驟 1：依次讀取文件 b 的每一行，對(duì)每一行執(zhí)行步驟 2 到步驟 5 步驟 2：讀取關(guān)鍵詞 id 和關(guān)鍵詞，令為 key步驟 3：依次讀取 key 的每一個(gè)字符，對(duì)每一個(gè)字符，執(zhí)行步驟4;步驟 4：如果該字符對(duì)應(yīng)的指針為 NULL，則創(chuàng)建其兒子節(jié)點(diǎn) ; 步驟 5：為當(dāng)前節(jié)點(diǎn)的對(duì)應(yīng)字符 id 置為關(guān)鍵詞 id3 ：根據(jù) A 文件生成 C文件步驟 1：依次讀取文件 A的每一行，對(duì)每一行執(zhí)行步驟 2 到步驟 5 步驟 2：分別獲取當(dāng)前行關(guān)鍵詞、 ip 地址和時(shí)間步驟 3：令關(guān)鍵詞 key=c1c2.cm ，對(duì) c1 到 cm每個(gè)字符，執(zhí)行步驟 4步驟4：獲取根節(jié)點(diǎn)的第c1個(gè)元素指針，轉(zhuǎn)移到節(jié)點(diǎn)node1，根據(jù)node1 的第c2個(gè)元素指針，轉(zhuǎn)移到node2.根據(jù)nodem的第cm個(gè)元素，獲取關(guān)鍵詞的id步驟5：往文件c 中寫入一行數(shù)據(jù)，格式為關(guān)鍵詞的id、ip地址和時(shí)間生成文件 B 的 TRIE 樹過程時(shí)間復(fù)雜度為 O(n*m)，其中 n 為文件 b 行數(shù)，m為文件 b 關(guān)鍵詞的最大長(zhǎng)度。 TRIE 的空間復(fù)雜度為 O(n*m)， n 和 m含義同上，但由于實(shí)際應(yīng)用中關(guān)鍵詞之間可能會(huì)有很多前綴相同現(xiàn)象，所以實(shí)際耗費(fèi)空間并不