- 相關(guān)推薦
百度java開發(fā)面試題
筆試是很多企業(yè)在招聘人才的時(shí)候應(yīng)用的手段之一，百度也是如此的。本文是關(guān)于百度java開發(fā)面試題，歡迎閱讀學(xué)習(xí)。
第一題
簡(jiǎn)評(píng)
百度的主要業(yè)務(wù)是搜索，搜索的基本原理如下
1.編寫爬蟲程序到互聯(lián)網(wǎng)上抓取網(wǎng)頁海量的網(wǎng)頁。
2.將抓取來的網(wǎng)頁通過抽取，以一定的格式保存在能快速檢索的文件系統(tǒng)中。
3.把用戶輸入的字符串進(jìn)行拆分成關(guān)鍵字去文件系統(tǒng)中查詢并返回結(jié)果。
由以上3點(diǎn)可見，字符串的分析，抽取在搜索引擎中的地位是何等重要。
因此，百度的筆試面試題中，出現(xiàn)這樣的題就變得理所當(dāng)然了。
以下是該題的java實(shí)現(xiàn)，代碼如下：
程序代碼 程序代碼
import java.net.*;
import java.io.*;
import java.util.*;
/** * @author tzy * 在j2sdk1.4.2下測(cè)試通過 */
public class FileNameStat{
private String srcPath;//要統(tǒng)計(jì)的文件路徑
private Map statMap;//用于統(tǒng)計(jì)的map
public FileNameStat(String srcPath)
{
this.srcPath=srcPath; 軟件開發(fā)網(wǎng) www.mscto.com
statMap=new TreeMap();
}
/*獲得要統(tǒng)計(jì)的URL的文件名*/
public String getFileName(String urlString)
{
URL url=null;
String filePath=null;
String fileName=null;
try
{
url=new URL(urlString);
filePath=url.getPath();
int index=0;
if ((index=filePath.lastIndexOf(“/”))!=-1)
{
fileName=filePath.substring(index+1);
}
else
{
fileName=”";
}
}
catch(MalformedURLException e)
{
}
return fileName;
}
/*統(tǒng)計(jì)指定文件名的個(gè)數(shù)*/
public void stat(String filename)
{
Integer count=null;
if(statMap.get(filename)!=null)
{
count=(Integer)statMap.get(filename);
count=new Integer(count.intValue()+1);
}
else
{
count=new Integer(1);
}
statMap.put(filename,count);
}
/*統(tǒng)計(jì)的主方法*/
public void start() throws FileNotFoundException,IOException
{
BufferedReader bfin=new BufferedReader(new FileReader(this.srcPath));
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è)數(shù)是” + entry.getValue());
}
}
public static void main(String[] args) throws Exception
{
FileNameStat fns=new FileNameStat(“src.txt”);//指定成待統(tǒng)計(jì)文件
fns.start();
fns.result();
}
}
第二題
簡(jiǎn)評(píng)：
這道題也與百度的業(yè)務(wù)有關(guān)，百度現(xiàn)在除了搜索外，還有貼吧，知道，博客等重要產(chǎn)品�！ ⊥瑫r(shí)也在積極的探索社區(qū)化，包括前不久宣布進(jìn)軍電子商務(wù)領(lǐng)域，搜索之外的這些產(chǎn)品，其主要功能的實(shí)現(xiàn)主要是對(duì)數(shù)據(jù)庫的操作�！ ∫虼耍脒M(jìn)入百度，也需要對(duì)數(shù)據(jù)庫有一定的認(rèn)識(shí)�！ �(shí)現(xiàn)思路及數(shù)據(jù)庫設(shè)計(jì)： 1，該論壇主要有兩個(gè)實(shí)體對(duì)象，用戶和帖子;對(duì)于帖子對(duì)象，有一個(gè)問題：回復(fù)的帖子是否應(yīng)該跟主題帖子存放在同一個(gè)表里?
考慮到每天更新10萬帖子，說明帖子數(shù)比較多，為了方便主題的呈現(xiàn)，我一般都把主題貼和回帖分別放在不同的表中，把主題貼和回帖分開可以提高查詢效率(300萬的訪問量每天)。
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è)主題有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，鑒于以上考慮，該論壇的三個(gè)表如下所示
表名：t_user_info (用戶信息表)
字段名 類型 缺省值 中文含義 約束 備注
id Int 用戶編號(hào) PRI Auto_increment
Name Varchar(30) 用戶名
Email Varchar(50)
Phone Varchar(30)
Addr Varchar(200)
其他字段略，根據(jù)需要添加 表名：main_content_info (主題帖信息表)
字段名 類型 缺省值 中文含義 約束 備注
id Int 貼編號(hào) PRI Auto_increment
Title Varchar(200) 發(fā)帖標(biāo)題
Content Text 發(fā)帖內(nèi)容
UserID Int 用戶編號(hào) 外鍵
其他字段略，根據(jù)需要添加
表名：sub_content_info (回復(fù)貼信息表)
字段名 類型 缺省值 中文含義 約束 備注
id Int 貼編號(hào) PRI Auto_increment
Title 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ù)庫表中的每個(gè)實(shí)例或行都是可以被惟一地區(qū)分(id)，不存在部分依賴，因此滿足2NF;
t_user_info (用戶信息表)和main_content_info (主題帖信息表)不存在任何傳遞依賴，至少屬于BCNF;
但是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)�！ ∷悸芳敖鉀Q方案如下：
1: 設(shè)計(jì)用TRIE樹實(shí)現(xiàn)關(guān)鍵詞到其對(duì)應(yīng)id的快速詞典查找
TRIE樹的每一個(gè)節(jié)點(diǎn)為一個(gè)包含256個(gè)元素的數(shù)組，同時(shí)指針指向其下一級(jí)節(jié)點(diǎn)
節(jié)點(diǎn)定義如下：
struct trienode
{
int id;
struct trienode *child[256];
}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：生成文件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)鍵詞id
3：根據(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í)間
4：復(fù)雜度分析
生成文件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)空間并不會(huì)很高。
生成C文件的時(shí)間復(fù)雜度同樣為O(n*m)，n為文件a行數(shù)，m為文件a關(guān)鍵詞的最大長(zhǎng)度，因?yàn)橛辛薚RIE樹之后，給定一個(gè)關(guān)鍵詞獲得其id的時(shí)間復(fù)雜度為關(guān)鍵詞長(zhǎng)度。生成C文件的過程除了TRIE樹空間外基本不需要太多額外的空間，空間復(fù)雜度為O(1)，由于系統(tǒng)有1G的可用內(nèi)存，TRIE占用的空間在幾十兆到200M之間(與關(guān)鍵詞集合有關(guān))，因此本方法完全可行。
【百度java開發(fā)面試題】相關(guān)文章：
java面試題及答案10-03
10個(gè)經(jīng)典的Java面試題集合09-20
iPhone軟件開發(fā)面試題10-23
2年工作經(jīng)驗(yàn)的java開發(fā)崗在深圳騰訊待遇大概在多少？09-23
Microsoft面試題09-04
iOS面試題07-10
公司面試題09-12
hibernate面試題10-18
英語面試題精選06-13