2021年百度公司人工智能機器學習/數據挖掘工程師面試題

簡答題

1. new 和 malloc 的區別。?

2. hash沖突是指什么？怎么解決？給兩種方法，寫出過程和優缺點。?

3. 命中的概率是 0.25，若要至少命中一次的概率不小于 0.75，則至少需要幾次？

第2題：

算法設計題

1. 用C/C++寫一個歸并排序。?

數據結構為struct Node{int v; Node *next};

接口為 Node * merge_sort(Node *);

??

2. 設計S型層次遍歷樹的算法，比如根節點是第一層，第二層從左至右遍歷，第三層從右至左遍歷，第四層再從左至右遍歷，以此類推。

舉例：應依次輸出 1 2 3 6 5 4 7 8 9。

?

3. 一個url文件，每行是一個url地址，可能有重復。

（1）統計每個url的頻次，設計函數實現實現。

（2）設有10億url，平均長度是20，現在機器有8G內存，怎么處理，寫出思路。

系統設計題

自然語言處理中的中文分詞問題，前向最大匹配算法（FMM）。

注：題目舉例說明了FMM的基本思想。

??

（1）設計字典的數據結構 struct dictnote。

?

（2）用C/C++實現FMM，可選接口為

int FMM(vector iLetters, dictnode *iRoot, vector *oResults);

其中 iLetters 為待分詞的句子，比如 {“小”，“明”，“今”，“天”，“買”，“了”，“i”，“p”，“o”，“n”，“e”，“6”}，

iRoot 是字典， oResults 保存輸出結果，即分詞的位置。也可以自己設計接口。

（3）收集了一些手機品牌的字典，如{iphone, 諾基亞}。

現在要求查找包含這些手機品牌的網頁，比如包含 iphone6, 諾基亞 9973 等。

怎么修改FMM實現這個功能，可以寫偽代碼。