最全演算法工程師面試題目整理(一)

歡迎關注我們的微信公眾號「人工智慧LeadAI」（ID：atleadai）

最近抽風，出去面試了不少公司，和不少演算法工程師招聘的朋友有所交流，整理了相關比較有意思的題目，供大家參考：

1

基於每日用戶搜索內容，假設只有少量已知商品的情況下，如何根據用戶搜索內容獲取平台內沒有的新商品？

答案：這是一條類似於分詞「新詞獲取問題」，答案是基於信息熵＋聚合度。

這邊需要考慮排除，首先做stop詞庫，先去除形容詞等。

信息熵：比如用戶搜索「曲面顯示屏 白色」，假設現在我們的商品庫中沒有顯示屏這個商品，我們需要判斷「顯示屏」是否是潛在的商品，我們需要考慮「顯示屏」左詞、右詞出現的可能。換句話說，如果大家都在搜索「顯示屏」商品的話，會出現大量的「便宜顯示屏」、「可旋轉顯示屏」、「顯示屏 黑色」等搜索短語，根據信息熵計算公式-p∑logp，「顯示屏」前後出現的詞語類別越多，信息熵越大，代表用戶搜索的需求越旺盛，「顯示屏」越有可能是沒有的商品。

聚合度：根據信息熵的理論也會出現「顯示」等高頻出現的干擾詞，再用聚合度，比如先計算出p(「顯示」)、p(「屏」)、或p(「顯」)、p(「示屏」)的概率，如果「顯示」是一個高頻合理的搜索詞的話，p(「顯示」)*p(「屏」)應該遠遠大於p(「顯示屏」)，p(「顯」)＊p(「示屏」)應該遠遠大於p(「顯示屏」)的概率，而實際電商搜索中，用戶連貫搜索「顯示屏」的概率才是遠超其它。

2

為什麼logistic回歸的要用sigmoid函數？優缺點？

答案：

優點：

1.數據壓縮能力，將數據規約在［0，1］之間 2.導數形式優秀，方便計算

缺點：

1.容易梯度消失，x稍大的情況下就趨近一條水平線 2.非0中心化，在神經網路演算法等情況下，造成反向傳播時權重的全正全負的情況。

為什麼要用？

答案1: logistic是基於Bernoulli分布的假設，也就是y|X~Bernoulli分布，而Bernoulli分布的指數族的形式就是1/(1+exp(-z))

其實還有一個答案二，我當時沒想起來，如就是：

對於logistic多分類而言，

x1、x2、...、xn，屬於k類的概率正比於：

我們回到2類：

x1、x2、...xn屬於1的概率是：

分子分母同除以分子極為1/(1+exp(-z))，z＝w11-w01，個人覺得這樣的證明才有說服力

3

對比牛頓法、梯度下降法的關係

講真，大學學完牛頓法就丟了，一時沒回答出來，回來整理如下：

答案：牛頓法快於梯度下降法，且是梯度下降法的極限。

首先，我們有展開式：

f′(x+Δx)=f′(x)+f″(x)?Δx

Δx=?μ?f′(x)

合併兩個式子，有：

f′(x+Δx)=f′(x)+f″(x)?(?μ?f′(x))

令f′(x+Δx)＝0，

μ＝1/f″(x)，極為牛頓法在隨機梯度下降中的μ

4

兩個盒子，50個紅球，50個白球，問如何放球，抽到紅球的概率最高？（每個盒子必須有球）

答案：一個盒子1個紅球，另外一個盒子剩餘的99個球

先假設第一個盒子放x個紅球，y個白球，另外的一個盒子裡面就有50-x紅球，50-y個白球.

求的目標函數：p＝1/2(x/(x+y))+1/2((50-x)/(100-x-y))

subject to. x+y>0 & 100-x-y>0

常規解法如上，被坑了一手的是，面試的說沒有常規解，我回來思考了半天，可能是盒子裡面的排練順序有差異，上層的抽取概率>下層的抽取概率，所以需要通過EM演算法，先得到若干次抽取的結果下，每層的最大概率密度函數，再結合上述的結果去回答。

5

常見的正則化有是么，有什麼作用，為什麼l1是會把feature壓縮到0而l2做不到？

答案：

(1)l1,l2正則化

l1對應python裡面numpy.linalg.norm(ord=1)

形如|w1|+|w2|+|w3|+...

l2對應python裡面numpy.linalg.norm(ord=2)

形如w12+w22+w3^2+...

(2)防止過擬合

其它防止過擬合的方法還有：

1.增加數據量

2.採取bagging演算法，抽樣訓練數據

**

(3)畫圖解決

左邊的l1，右邊的l2，

l1在作圖只要不是特殊情況下與正方形的邊相切，一定是與某個頂點優先相交，那必然存在橫縱坐標軸中的一個係數為0，起到對變數的篩選的作用。

l2的時候，其實就可以看作是上面這個藍色的圓，在這個圓的限制下，點可以是圓上的任意一點，所以q＝2的時候也叫做嶺回歸，嶺回歸是起不到壓縮變數的作用的，在這個圖裡也是可以看出來的。

6

分類模型如何選擇？如何判斷效果？如何計算AUC？你最熟悉的ensemble Classification model是什麼？

我這邊參考了《Do we Need Hundreds of Classifiers to Solve Real World Classification Problems》裡面的結論，有興趣的自行去搜。

答案

整體上講：數據量越大，神經網路越好；維度越多，bagging演算法越優秀；數據量上不多不少的情況下，SVM效果最好；

常用判斷：roc、auc、ks、f1值、recall等；

AUC計算方法：roc曲線下方的面積積分即可，或者大數定律的投點實驗

最熟悉的集成分類模型，我說的是randomforest，詳述了原理及實際應用的注意點，後來我問了面試管，主要在這塊想了解的是實際解決的相關項目的真實性：

1、randomforest是由若干顆cart樹構成的，每棵樹盡情生長不枝剪，最後採取加權投票或者均值的方式確定輸出值；

2、每棵樹的數據是採取bagging式的隨機抽取特徵及數據樣本，兩顆樹之間的數據有可能會重複；

3、一般流程會先以sqrt(feature_number)作為每次輸入的特徵數，採取grid_search的方法觀察tree的數量由0-500，oob的變化

這邊被打斷了，解釋什麼叫做oob，也就是out of bag，每次抽取的數據樣本進行訓練，沒有被抽取到的數據作為檢驗樣本，檢驗樣本上的誤差就叫做oob；

4、根據實際要求的精度上後期可以跟進調整：每次輸入的特徵個數、每棵樹的最大深度、每個節點的分支方式（GINI還是信息增益率）、子節點最少數據量、父節點最少數據量等等。

這邊又被打斷了，問，什麼叫做信息增益率？

首先熵的計算如下：

信息增益如下：

比如14個人，好人5個壞人9個。這14個人被通過性別劃分開，10個男性中3個壞人，7個好人；4個女性中2個壞人，2個好人。

信息增益就是:

IGain＝(-5/14)log(5/14)+(-9/14)log(9/14)-(10/14(-3/10log(3/10)-7/10log(7/10))+4/14(-1/2log(1/2)-1/2log(1/2)))

看到這樣的計算方式，必然會存在問題，假設我們身份證為區分類別的化，每個身份證號碼都是獨一無二的，勢必存在存在1/n*log(1)=0這樣的最佳劃分，但是這樣的結果就是將所有的情況分別作為子節點，很明顯沒有意義，所以引出下面的信息增益率。

信息增益率就是:

比如上面分人的例子，Info＝-10/14log(10/14)-4/14log(4/14)

很明顯也可以看出，當你劃分的子類別越多，你的info會越大，Gain_ratio就越小，信息增益率就越低，懲罰了剛才身份證分類這種行為。

這也是id3和c4.5之間最大的差異，c4.5以信息增益率代替率id3裡面的信息增益，除此之外，id3隻能對分類變數處理而c4.5既可以分類變數也可以連續變數，還是很強的，同時他們都可以做多分類，而後續的cart等做多分類的成本會增加（疊加的方式）。

其實，這些都很基礎但是時間長了，真的很繞人，我也是先自己默默的在紙上畫了挺久才和面試管聊，有點出乎我的意料。

7

循環神經網路中介紹一個你熟悉的？

我說的是LSTM。

首先，先跑出了循環的機制，同時點明了RNN潛在隱藏節點對output的影響，做了下圖：

當前的預測結果，與input及上次的layer1節點下的結果相關。

正向循環：

節點1的值 = sigmoid(np.dot(輸入參數,神經元1) + np.dot(上次節點1的值,潛在神經元))

輸出值＝sigmoid(np.dot(節點1的值,神經元2))

誤差計算：

真實y－輸出值

delta：

節點2處的deltas=誤差計算*sigmoid(np.dot(節點1的值,神經元2))／(1-sigmoid(np.dot(節點1的值,神經元2)))

反向修正神經元：

神經元2 += (節點1的值).T.dot(節點2處的delta)

潛藏神經元 += (上次的節點1的值).T.dot(節點1處的delta)

神經元1 += 輸入值.T.dot(節點1處的delta)

核心強調了：sigmoid(np.dot(輸入參數,神經元1) + np.dot(上次節點1的值,潛在神經元))，輸出值與輸出值及上次節點1處的輸入值有關。

然後講了簡單的在語義識別的實際作用。

8

kmeans的原理及如何選擇k？如何選擇初始點？

原理是送分題。

原理：在給定K值和K個初始類簇中心點的情況下,把每個點(亦即數據記錄)分到離其最近的類簇中心點所代表的類簇中，優點在於易於理解和計算，缺點也是很明顯，數據一多的情況計算量極大，且標籤feature定義距離的難度大。

K的選擇，我答的一般，歡迎大家補充，

1、根據具體的業務需求，實際需求確定最後聚成的類的個數

2、grid_search去試，看那種距離下，損失函數最小（其實這樣回答不好，數據量大的情況下，機會不可能）

這邊的損失函數類別較多，可能包括組內間距和／組外間距和等

3、隨機抽樣下的層次聚類作為預參考

理論上，隨機採樣的數據分布滿足原來的數據集的分布，尤其是大量採樣次數下的情況，針對每一個較小的數據集合採取層次聚類確定最後的聚類個數，再針對原始的數據集合進行kmeans聚類

如何選取初始點？

這個問題我被問過好多次，其實，不管是r或者python裡面，或者大家日常使用中都是默認的隨機選取，然後通過多次k-折等方法不斷的去迭代，其實這樣存在的問題就是如果初始點隨機選取的有誤，導致無論這麼迭代都得不到最優的點，如：

在隨機初始點的情況下，紅色區域的部分點被藍色和綠色侵佔為己點，修正初始點，也就是將隨機初始點的聚類中心全部上移的情況下，藍色點區收回了原屬於自己的點區。

之前我惡補過一片論文：《K-means 初始聚類中心的選擇演算法》，裡面提出了兩個指標來衡量：

1.k-dist

某個點 p 到它的第k 個最近點的距離為點 p 的 k-dist 值。點的 k-dist 半徑範圍內至少包含k + 1 個點，理論上同一個聚類中改變k值不會引起k-dist值明顯變化。將 k-dist 值由小到大排序，a、b、c表示平緩點，d，e，f為躍遷點。

2.DK圖

k-dist 圖中相鄰兩點的 k-dist 值之差記為 DK。k-dist 圖中相鄰兩點pm和pm－1的 k-dist的差為DKm=k-distm －k-distm－1 ( m ＞ 1) 。由於 k-distm 非遞減，顯然 DKm ＞ 0。DK 值接近的連續鄰近點處於 k-dist 圖的同一條平緩曲線上，即處於

同一個密度層次; DK 值大幅跳動的點處於密度轉折曲線或雜訊曲線上。

3.選擇

對 DK 值從小到大排序，得到 DK 標準範圍δ。依據 DK 標準範圍內對應的數據點的分布情況，在 k-dist 圖中找出 k 個平緩曲線，代表 k 個主要密度水平。選擇每個密度水平的第一個點作為初始聚類中心。

重複若干次，得到若干組的優化聚類中心，在根據優化聚類中心組下的組內間距和／組外間距和判斷那個點組為最優點組。

其實這樣的開銷也挺大的，目前也沒有看到其它比較易理解的kmeans的初始點計算的方式。

9

大致講解一下最優化中拉格朗日乘子法的思路？KKT是什麼？

當我們求解一個函數的最小值，且這個函數也被某些確定的限制條件限制的時候：

我們可以將限制條件加入f(x)中一同進行後續的偏導計算：

至於KKT我了解的其實不多，也是回來之後惡補了一下，通過例子入手：

求解上面這個問題的化，我們需要考慮構造兩個約束變數a1，b1，使得

h1(x，a1)＝g1(x)＋a1^2＝a－x＋a1^2=0

h2(x，b1)＝g2(x)＋b1^2＝b－x＋b1^2=0

在根據普通拉格朗日乘子的方法對下面公式的每一項求偏導：

這個條件就是KKT條件

其實我覺得，http://www.cnblogs.com/zhangchaoyang/articles/2726873.html，這篇文章寫的挺好的，想要詳細了解的可以仔細參考一下。

10

聽說你做過風控，異常點檢測你用過什麼辦法？

之前正好整理過，內心大喜：

1、6個西格瑪的原理

2、箱式圖大於3/2QI＋Q3，小於Q1－3/2Qi

3、基於距離離群檢測（聚類），包括歐式、馬氏距離、街道距離

這邊被打斷了，問了馬氏距離的細節，好處：

追問了協方差Sigma怎麼算：

Cov(X,Y)=E(XY)-E(X)E(Y)

追問了什麼時候用馬氏距離比較好：

舉例很有名的曲線分布圖，如下：

4.pca的基於特徵值壓縮的方法

5.基於isolation forest識別的方法。

這邊被追問了一次原理：

method:

1.從原始數據中隨機選擇一個屬性feature；

2.從原始數據中隨機選擇該屬性的下的一個樣本值value；

3.根據feature下的value對每條記錄進行分類，把小於value的記錄放在左子集，把大於等於value的記錄放在右子集；

4.repeat 1-3 until： 　　　　

4.1.傳入的數據集只有一條記錄或者多條一樣的記錄； 　　　　

4.2.樹的高度達到了限定高度；

以s(x,n)為判斷數據是否異常的衡量指標。

其中，h(x)為x對應的節點深度，c(n)為樣本可信度，s(x,n)~[0,1]，正常數據來講s(x,n)小於0.8，s(x,n)越靠近1，數據異常的可能性越大。

詳細的可以參見我的另一篇博客：http://www.jianshu.com/p/ac6418ee8e3f

本來準備一次寫完的，後來寫著寫著發現真的挺多，準備寫個系列，最後謝謝大家的閱讀。

推薦閱讀：