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