筆試時間：2015-9-20

　　筆試職位：機(jī)器學(xué)習(xí)/數(shù)據(jù)挖掘工程師

　　筆試城市：天津、深圳、南京等

　　一. 簡答題

　　1. new 和 malloc 的區(qū)別。

　　2. hash沖突是指什么?怎么解決?給兩種方法，寫出過程和優(yōu)缺點(diǎn)。

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

　　二. 算法設(shè)計題

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

　　數(shù)據(jù)結(jié)構(gòu)為struct Node{int v; Node next};

　　接口為 Node merge_sort(Node );

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

　　舉例：應(yīng)依次輸出 1 2 3 6 5 4 7 8 9。

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

　　(1)統(tǒng)計每個url的頻次，設(shè)計函數(shù)實(shí)現(xiàn)實(shí)現(xiàn)。

　　(2)設(shè)有10億url，平均長度是20，現(xiàn)在機(jī)器有8G內(nèi)存，怎么處理，寫出思路。

　　三. 系統(tǒng)設(shè)計題

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

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

　　(1)設(shè)計字典的數(shù)據(jù)結(jié)構(gòu) struct dictnote。

　　(2)用C/C++實(shí)現(xiàn)FMM，可選接口為

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

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

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

　　(3)收集了一些手機(jī)品牌的字典，如{iphone, 諾基亞}。

　　現(xiàn)在要求查找包含這些手機(jī)品牌的網(wǎng)頁，比如包含 iphone6, 諾基亞 9973 等。

　　怎么修改FMM實(shí)現(xiàn)這個功能，可以寫偽代碼。