2021年7月底，"陌陌"推薦算法5道面試題分享！

問題1：Graph SAGE的原理

GraphSAGE是Graph SAmple and aggreGatE的縮寫，其運(yùn)行流程如上圖所示，可以分為三個(gè)步驟：
對圖中每個(gè)頂點(diǎn)鄰居頂點(diǎn)進(jìn)行采樣
根據(jù)聚合函數(shù)聚合鄰居頂點(diǎn)蘊(yùn)含的信息
得到圖中各頂點(diǎn)的向量表示供下游任務(wù)使用

問題2：deepwalk的原理

DeepWalk的思想類似word2vec，使用圖中節(jié)點(diǎn)與節(jié)點(diǎn)的共現(xiàn)關(guān)系來學(xué)習(xí)節(jié)點(diǎn)的向量表示。那么關(guān)鍵的問題就是如何來描述節(jié)點(diǎn)與節(jié)點(diǎn)的共現(xiàn)關(guān)系，DeepWalk給出的方法是使用隨機(jī)游走(RandomWalk)的方式在圖中進(jìn)行節(jié)點(diǎn)采樣。

RandomWalk是一種可重復(fù)訪問已訪問節(jié)點(diǎn)的深度優(yōu)先遍歷算法。給定當(dāng)前訪問起始節(jié)點(diǎn)，從其鄰居中隨機(jī)采樣節(jié)點(diǎn)作為下一個(gè)訪問節(jié)點(diǎn)，重復(fù)此過程，直到訪問序列長度滿足預(yù)設(shè)條件。

獲取足夠數(shù)量的節(jié)點(diǎn)訪問序列后，使用skip-gram model進(jìn)行向量學(xué)習(xí)。

問題3：xdeepfm, deepfm區(qū)別
上圖為xDeepFM的總體結(jié)構(gòu)，有三個(gè)分支:Linear(稀疏的01向量作為輸入)、DNN(經(jīng)過embedding的稠密向量作為輸入)、CIN（壓縮感知層)。

xDeepFM如果去掉CIN分支，就等同于wide & Deep。

xDeepFM將基于Field的vector-wise思想引入Cross，并且保留了Cross的優(yōu)勢，模型結(jié)構(gòu)也很elegant，實(shí)驗(yàn)效果也提升明顯。如果說DeepFM只是“Deep & FM”，那么xDeepFm就真正做到了”Deep”Factorization Machine。xDeepFM的時(shí)間復(fù)雜度會(huì)是其工業(yè)落地的一個(gè)主要性能瓶頸，需要重點(diǎn)優(yōu)化。

問題4：wide&deep，deepfm區(qū)別，分別哪個(gè)公司的

Goggle在2016年提出的Wide & Deep模型。deepfm是華為和哈工大聯(lián)合發(fā)表的模型。
deepfm采取Wide & Deep的框架，差異在于將Wide部分的LR替換為了FM，從而自動(dòng)構(gòu)造二階特征叉乘，而非手工設(shè)計(jì)叉乘。


 問題5：股票最大利潤，并且輸出買賣價(jià)格
該題為leetcode121題，兩種方法:

方法一:暴力解法
對數(shù)組進(jìn)行遍歷，找到后一個(gè)數(shù)與前一個(gè)數(shù)的最大差值，返回。注意遍歷j時(shí)要從i+1進(jìn)行遍歷。
代碼如下：

在 leetcode 上運(yùn)行上面代碼會(huì)出現(xiàn)超出時(shí)間限制的問題。
時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)

方法二：
只進(jìn)行一次遍歷，在遍歷過程中更新兩個(gè)值，股票最小值和差值最大值，更新到最后即可。
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)