2021年7月底，"陌陌"推荐算法5道面试题分享！

问题1：Graph SAGE的原理

GraphSAGE是Graph SAmple and aggreGatE的缩写，其运行流程如上图所示，可以分为三个步骤：
对图中每个顶点邻居顶点进行采样
根据聚合函数聚合邻居顶点蕴含的信息
得到图中各顶点的向量表示供下游任务使用

问题2：deepwalk的原理

DeepWalk的思想类似word2vec，使用图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系，DeepWalk给出的方法是使用随机游走(RandomWalk)的方式在图中进行节点采样。

RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。

获取足够数量的节点访问序列后，使用skip-gram model进行向量学习。

问题3：xdeepfm, deepfm区别
上图为xDeepFM的总体结构，有三个分支:Linear(稀疏的01向量作为输入)、DNN(经过embedding的稠密向量作为输入)、CIN（压缩感知层)。

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

xDeepFM将基于Field的vector-wise思想引入Cross，并且保留了Cross的优势，模型结构也很elegant，实验效果也提升明显。如果说DeepFM只是“Deep & FM”，那么xDeepFm就真正做到了”Deep”Factorization Machine。xDeepFM的时间复杂度会是其工业落地的一个主要性能瓶颈，需要重点优化。

问题4：wide&deep，deepfm区别，分别哪个公司的

Goggle在2016年提出的Wide & Deep模型。deepfm是华为和哈工大联合发表的模型。
deepfm采取Wide & Deep的框架，差异在于将Wide部分的LR替换为了FM，从而自动构造二阶特征叉乘，而非手工设计叉乘。


 问题5：股票最大利润，并且输出买卖价格
该题为leetcode121题，两种方法:

方法一:暴力解法
对数组进行遍历，找到后一个数与前一个数的最大差值，返回。注意遍历j时要从i+1进行遍历。
代码如下：

在 leetcode 上运行上面代码会出现超出时间限制的问题。
时间复杂度：O(n^2)
空间复杂度：O(1)

方法二：
只进行一次遍历，在遍历过程中更新两个值，股票最小值和差值最大值，更新到最后即可。
时间复杂度：O(n)
空间复杂度：O(1)