NO IMAGE

華電北風吹
天津大學認知計算與應用重點實驗室
日期:2016-10-27

1、都知道小浣熊裡面有n個不同的人物,但是一包小浣熊裡面只會完全隨機的放一張人物卡。如果想集齊所有人物卡片大概要吃多少袋小浣熊?
答案: nlognn\log n
解析:關鍵是隨機事件的劃分。比如說我得到第一個人物(不管是誰),肯定只要買一包小浣熊即可。在得到一個人物卡片後,我想得到另一個人物我需要1n−1n=nn−1\frac{1}{\frac{n-1}{n}}=\frac{n}{n-1}(由幾何分佈期望公式可得)。這樣可以看出,相對於已有的kk張卡片,每次新增加一個任務卡片所需要購買小浣熊的個數服從引數n−kn\frac{n-k}{n}的幾何分佈。這樣的話問題就簡單了,可以容易地寫出總共需要購買的小浣熊包數是
1 nn−1 nn−2 nn−3… n2 n1=nlogn(1)1 \frac{n}{n-1} \frac{n}{n-2} \frac{n}{n-3}… \frac{n}{2} \frac{n}{1}=n\log n \tag{1}

2、一個村子裡有五十戶人家,每家都養了一條狗,假如其中出現了病狗。條件是每個人只能觀察別人的狗,相互之間不能交流。並且每個人只能殺自己的狗,並且是在判斷出自己的狗有病後當天立馬殺掉自己的狗。每個人每天觀察一下別人的狗,作出決定是否殺自己的狗。第一天,風平浪靜。第二天風平浪靜。第三天有狗被殺。問:其中有多少條病狗?
答案:第三天出現狗被殺了,所以是三條。
解析:這裡有個遞推的過程。比如說如果總共有一條病狗,那麼第一天病狗的主人就應該會把自己的狗殺了(只要觀察到別人的狗都是正常的,就知道自己的狗一定是病狗,因為村子裡一定有病狗)。根據第一天沒人殺狗,知道病狗數目一定大於1。來到了第二天,由於人們都能夠判斷出病狗數目大於等於2。這時,如果病狗數目等於2,這一天病狗的主人一定會在今天看到一條病狗,就能推測出來自己的狗一定是病狗,當天就會把自己的病狗殺掉,所以由第二天風平浪靜可知,病狗數目一定大於等於3。依次遞推即可知道。第幾天出現了殺狗,就總共有多少條病狗。

3、寫一個時間複雜度為nlognn\log n的連結串列排序演算法。
答:歸併排序每次二分的時候,掃描一下連結串列長度,合併的時候寫成有序連結串列合併排序即可。
解析:只要稍微修改一下快排也可以修改為適用於連結串列排序。

4、在一個源源不斷的樣本輸出流中,怎樣保證等概率取樣得到一個大小為k的子集?
答:用一個陣列先儲存輸出的前k個元素,記錄產生的樣本總數n,然後對於每產生一個元素以概率kn\frac{k}{n}接受這個樣本,如果接受就隨機替換陣列中的一個樣本。

通用知識點:
基本上來自於資料結構知識點、機器學習經典演算法,自然語言處理,搜尋引擎原理等知識點。
1、搜尋引擎的自動補全功能是怎麼實現的?資料儲存上有什麼優化技巧嗎?怎麼對使用者查詢預處理?
2、網頁怎麼去重?
3、手寫程式碼二分,快排,拓撲排序,二維矩陣的遍歷。
4、講講邏輯迴歸,SVM,決策樹,GBDT,RF,比較優缺,也會遇到手推的。
5、考察資料溢位類的簡單程式碼。最大連續子陣列和,寫計算log(1 ex)\log (1 e^x)的函式。
6、搜尋引擎的推薦問題,怎麼根據使用者點選判斷推薦的連結是否有效。
7、怎麼從一段文字中找出所有的人名?
8、怎麼找出一個文字中所有的同根詞(所構成的字母和個數完全一樣)?