百度java開發(fā)面試題
筆試是很多企業(yè)在招聘人才的時候應(yīng)用的手段之一，百度也是如此的。本文是關(guān)于百度java開發(fā)面試題，歡迎閱讀學(xué)習(xí)。
第一題
簡評
百度的主要業(yè)務(wù)是搜索，搜索的基本原理如下
1.編寫爬蟲程序到互聯(lián)網(wǎng)上抓取網(wǎng)頁海量的網(wǎng)頁。
2.將抓取來的網(wǎng)頁通過抽取，以一定的格式保存在能快速檢索的文件系統(tǒng)中。
3.把用戶輸入的字符串進行拆分成關(guān)鍵字去文件系統(tǒng)中查詢并返回結(jié)果。
由以上3點可見，字符串的分析，抽取在搜索引擎中的地位是何等重要。
因此，百度的筆試面試題中，出現(xiàn)這樣的題就變得理所當然了。
以下是該題的java實現(xiàn)，代碼如下：
程序代碼 程序代碼
import java.net.*;
import java.io.*;
import java.util.*;
/** * @author tzy * 在j2sdk1.4.2下測試通過 */
public class FileNameStat{
private String srcPath;//要統(tǒng)計的'文件路徑
private Map statMap;//用于統(tǒng)計的map
public FileNameStat(String srcPath)
{
this.srcPath=srcPath; 軟件開發(fā)網(wǎng) www.mscto.com
statMap=new TreeMap();
}
/*獲得要統(tǒng)計的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)計指定文件名的個數(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)計的主方法*/
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)計結(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()) + “的個數(shù)是” + entry.getValue());
}
}
public static void main(String[] args) throws Exception
{
FileNameStat fns=new FileNameStat(“src.txt”);//指定成待統(tǒng)計文件
fns.start();
fns.result();
}
}
第二題
簡評：
這道題也與百度的業(yè)務(wù)有關(guān)，百度現(xiàn)在除了搜索外，還有貼吧，知道，博客等重要產(chǎn)品�！ ⊥瑫r也在積極的探索社區(qū)化，包括前不久宣布進軍電子商務(wù)領(lǐng)域，搜索之外的這些產(chǎn)品，其主要功能的實現(xiàn)主要是對數(shù)據(jù)庫的操作�！ ∫虼耍脒M入百度，也需要對數(shù)據(jù)庫有一定的認識�！ 崿F(xiàn)思路及數(shù)據(jù)庫設(shè)計： 1，該論壇主要有兩個實體對象，用戶和帖子;對于帖子對象，有一個問題：回復(fù)的帖子是否應(yīng)該跟主題帖子存放在同一個表里?
考慮到每天更新10萬帖子，說明帖子數(shù)比較多，為了方便主題的呈現(xiàn)，我一般都把主題貼和回帖分別放在不同的表中，把主題貼和回帖分開可以提高查詢效率(300萬的訪問量每天)。
2，按照1中的思路，該論壇由兩個對象(用戶和帖子)變成三個實體對象，分別是用戶，主題帖子，回復(fù)帖子;
3，上述三個對象存在三個關(guān)系，分別是：
用戶–主題帖，一個用戶可以發(fā)0個或多個帖子，一個帖子對應(yīng)一個用戶(一對多關(guān)系)，
主題帖–回復(fù)帖：一個主題有0個或多個回復(fù)帖子，一個回復(fù)帖子對應(yīng)一個主題(一對多關(guān)系);
用戶–回復(fù)貼：一個用戶可以回0個或多個帖，一個帖子對應(yīng)一個用戶(一對多關(guān)系)。
還存在對回復(fù)貼的回復(fù)，這個考慮用fatherId來表示。
4，由于三個關(guān)系 “用戶–主題帖，主題帖–回復(fù)帖，用戶–回復(fù)貼” 都是一對多關(guān)系，根據(jù)表設(shè)計一般原則，可以將這兩個關(guān)系獨立建立表，也可以不另外建表而將一對多的關(guān)系體現(xiàn)在實體表中;然而，表間的連接查詢是非常耗資源的，所以應(yīng)盡量減少表間連接，那么對三個關(guān)系不應(yīng)該分別建表，而是把用戶的id作為主題表和回帖表的外鍵，把主題貼id作為回帖表的外鍵。
5，鑒于以上考慮，該論壇的三個表如下所示
表名：t_user_info (用戶信息表)
字段名 類型 缺省值 中文含義 約束 備注
id Int 用戶編號 PRI Auto_increment
Name Varchar(30) 用戶名
Email Varchar(50)
Phone Varchar(30)
Addr Varchar(200)
其他字段略，根據(jù)需要添加 表名：main_content_info (主題帖信息表)
字段名 類型 缺省值 中文含義 約束 備注
id Int 貼編號 PRI Auto_increment
Title Varchar(200) 發(fā)帖標題
Content Text 發(fā)帖內(nèi)容
UserID Int 用戶編號 外鍵
其他字段略，根據(jù)需要添加
表名：sub_content_info (回復(fù)貼信息表)
字段名 類型 缺省值 中文含義 約束 備注
id Int 貼編號 PRI Auto_increment
Title Varchar(200) 發(fā)帖標題
Content Text 發(fā)帖內(nèi)容
UserID Int 用戶編號 外鍵
FatherID Int 父編號
MainID Int 主題帖編號 外鍵
其他字段略，根據(jù)需要添加
6，符合范式分析：
上述表中每個字段不可再分，首先滿足1NF;
然后數(shù)據(jù)庫表中的每個實例或行都是可以被惟一地區(qū)分(id)，不存在部分依賴，因此滿足2NF;
t_user_info (用戶信息表)和main_content_info (主題帖信息表)不存在任何傳遞依賴，至少屬于BCNF;
但是sub_content_info (回復(fù)貼信息表)不滿足3NF,因為存在如下傳遞依賴：id–>FatherID,FatherID–>MainID。
范式并不是越高越好，sub_content_info表只滿足2NF卻更有效率，也是當今論壇較主流的設(shè)計。
第三題
簡評：
如何對海量數(shù)據(jù)進行快速檢索，這是搜索引擎的必需考慮的問題。這又涉及到數(shù)據(jù)結(jié)構(gòu)和算法。 因此，要想進入百度，就必須熟悉一些基本的算法和數(shù)據(jù)結(jié)構(gòu)�！ ∷悸芳敖鉀Q方案如下：
1: 設(shè)計用TRIE樹實現(xiàn)關(guān)鍵詞到其對應(yīng)id的快速詞典查找
TRIE樹的每一個節(jié)點為一個包含256個元素的數(shù)組，同時指針指向其下一級節(jié)點
節(jié)點定義如下：
struct trienode
{
int id;
struct trienode *child[256];
}TRIENODE;
如果TRIE樹的某個節(jié)點的指針為NULL，說明從跟節(jié)點到當前節(jié)點的路徑構(gòu)成文件B中的一個關(guān)鍵詞，
在其節(jié)點的id保存該關(guān)鍵詞的id;如果指針不為NULL，則id對應(yīng)為0或者一個無窮大的整數(shù)，標志從根節(jié)點
到當前節(jié)點的路徑不是一個完整的關(guān)鍵詞。
將關(guān)鍵詞轉(zhuǎn)化為二進制無符號char型數(shù)組，即對于漢字等雙字節(jié)字符視為兩個無符號char型整數(shù)，
每個元素的取值范圍在0到255之間。
2：生成文件b的TRIE樹
步驟1：依次讀取文件b的每一行，對每一行執(zhí)行步驟2到步驟5
步驟2：讀取關(guān)鍵詞id和關(guān)鍵詞，令為key
步驟3：依次讀取key的每一個字符，對每一個字符，執(zhí)行步驟4;
步驟4：如果該字符對應(yīng)的指針為NULL，則創(chuàng)建其兒子節(jié)點;
步驟5：為當前節(jié)點的對應(yīng)字符id置為關(guān)鍵詞id
3：根據(jù)A文件生成C文件
步驟1：依次讀取文件A的每一行，對每一行執(zhí)行步驟2到步驟5
步驟2：分別獲取當前行關(guān)鍵詞、ip地址和時間
步驟3：令關(guān)鍵詞key=c1c2…cm，對c1到cm每個字符，執(zhí)行步驟4
步驟4：獲取根節(jié)點的第c1個元素指針，轉(zhuǎn)移到節(jié)點node1，
根據(jù)node1的第c2個元素指針，轉(zhuǎn)移到node2…
根據(jù)nodem的第cm個元素，獲取關(guān)鍵詞的id
步驟5：往文件c中寫入一行數(shù)據(jù)，格式為關(guān)鍵詞的id、ip地址和時間
4：復(fù)雜度分析
生成文件B的TRIE樹過程時間復(fù)雜度為O(n*m)，其中n為文件b行數(shù)，m為文件b關(guān)鍵詞的最大長度。TRIE的空間復(fù)雜度為O(n*m)，n和m含義同上，但由于實際應(yīng)用中關(guān)鍵詞之間可能會有很多前綴相同現(xiàn)象，所以實際耗費空間并不會很高。
生成C文件的時間復(fù)雜度同樣為O(n*m)，n為文件a行數(shù)，m為文件a關(guān)鍵詞的最大長度，因為有了TRIE樹之后，給定一個關(guān)鍵詞獲得其id的時間復(fù)雜度為關(guān)鍵詞長度。生成C文件的過程除了TRIE樹空間外基本不需要太多額外的空間，空間復(fù)雜度為O(1)，由于系統(tǒng)有1G的可用內(nèi)存，TRIE占用的空間在幾十兆到200M之間(與關(guān)鍵詞集合有關(guān))，因此本方法完全可行。
【百度java開發(fā)面試題】相關(guān)文章：
公司JAVA開發(fā)面試題06-03
java前端開發(fā)面試題05-09
2016年Java開發(fā)崗位面試題02-16
java開發(fā)面試題型與技巧12-31
百度Java研發(fā)面試題分析07-31
百度android開發(fā)面試題05-20
16年Java開發(fā)崗位面試題匯總07-12