秋招基本结束，回馈牛油，算法精华面经

2019-1018 秋招面经总结

投递岗位：机器学习（搜索推荐）算法工程师

大致情况：paper较多（一作二作共5篇），有个top5的阿里天池竞赛，2个实验室相关项目，无实习经历。

投递简历后无反馈的公司（投递的太早，且简历有问题）：ViVO、OPPO 、京东、商汤

面试的公司：字节、快手、阿里、华为、欢聚时代、海康威视、网易雷火、滴滴、大华、依图（面试中）

Get offer的公司：阿里、华为（优招）、海康威视、滴滴（sp）、大华（提前批）、欢聚时代（ssp）、网易雷火伏羲实验室（大概率）

从7月份开始面试（准备），总体而言的心路历程是，7月份激情满满（备受打击），8月份饱受煎熬，9月开始收获offer。

由于LZ本人对于找工作毫无经验，且实验室科研任务较大（paper，项目），因此7月份才开始准备找工作，包括复习机器学习相关算法，刷题。且当时完全意识不到刷题的重要性，人为手撕代码仅仅起到锦上添花的作用，撕不出来也无伤大雅。直到遇见了字节和快手的面试。

大概是在7月10号左右，LZ参加人生中的第一次求职面试，当时自己的复习情况是，仅仅过了一遍统计机器学习，LeetCode上刷了20道数组和字符串题，（对于DP、DFS、BFS、二叉树、链表等仅仅知道概念），然后信心满满参加了宇宙条的面试，前面半个小时，聊比赛，问ML、CV的基础知识，气氛极好。后面开始撕代码，气氛突然严肃起来。。。只记得当时第一道手撕题是一个数组题，表面上是个数组，其实需要用DP来做，结果可想而知（硬着头皮思考的过程真的煎熬），又撕了一道二叉树的题（已经汗流浃背）一面被刷。。。从某种意义上，此生宇宙条已经与我无缘（按照我开始的刷题时间，不可能通过8月份正式批的头条笔试），我也为自己的年轻付出了代价。

在经历了头条的面试后，LZ痛定思痛，又认真复习了一遍机器学习算法，且开始疯狂刷题，大概到7.23左右参加了快手的“快-star校招计划”。其实当时也仅仅刷了100道题不到，且大部分是简单题，用的方法也大部分是暴力方法，每道题没有去参考讨论区的最优解。在快手的面试中，前前后后共面试了5轮。前面两轮的面经已经发过，通过前2轮的面试，面试官可能发现了我的基础知识比较扎实，简历也不错，软肋在手撕代码，于是直接加了3轮，每轮都是手撕代码（欲哭无泪），分别是求链表的循环入口节点，Topk问题，在一个数组中，求所有的字数组，这些子数组的元素和为固定值。这几个题在现在看来太easy了，无奈当时自己都没刷过，结果就是第一题自己只会判断链表是否有环，但是入口节点在哪里不会判断（需要手推一下），第二题只会用kn复杂度的算法（完全是凭借本科一点排序的知识写的），不会快排和堆排序的方法，第三题只会在所有元素都是正数的情况下，用双指针做。经过了后3轮的面试，我的软肋暴露无遗，也与快手擦肩而过。

经过头条和快手的摧残，LZ备受打击，这时候才真真认识到手撕代码的重要性，再加上7月份结束后大部分公司的提前批已经结束，LZ真的进入了疯狂刷题的阶段，而且也开始有针对性的刷高频题和热点题（大概这时才步入求职的正轨吧）。由于篇幅有限，LZ不再讲述自己的心路历程（前面两个典型的案例是为了强调手撕代码的重要性），后面的面经，由于面试公司太多，轮数太多，且大部分知识点大同小异，因此LZ也不会根据不同的公司总结，而是把所有的知识点分类总结。只要把这些知识掌握，面试算法基础基本十拿九稳。

• 首先是手撕代码，这一块LZ把高频题总结后单独发帖。
• 其次是机器学习算法，统计机器学习中一共归纳了10种，但其实需要掌握的，且按照重要性来排序是LR、SVM、集成学习（boosting && bagging）、线性回归、k-means（手撕代码也需要掌握，面试时可能会和GMM一起问）、贝叶斯决策、决策树、EM、马尔科夫模型、KNN。各种算法掌握的要点是：

1. LR（5星）：损失函数、交叉熵、权重更新的推导（建议每次面试之前推一遍）；从权重更新的公式中，明白交叉熵相对于MSE损失函数的优点（大部分CNN网络结构用的损失函数都是交叉熵）；多个角度解释逻辑回归与SVM之间的关系；标签是-1/1时损失函数形式推导。
2. SVM（5星）：理解SVM目标函数的由来；理解SVM中核技巧的使用；将目标函数转化成对偶问题的推导（软间隔、硬间隔）；为什么要转换成对偶问题求解，求解的权重个数（一系列相关的细节问题）；多个角度解释逻辑回归与SVM之间的关系。
3. 集成学习boosting（5星）：boosting算法的思想；为什么boosting能降低模型的偏差；深刻理解Adaboost、GBDT算法的思想，尤其是GBDT（包括分类树、回归树在不同情况下的使用，构建树模型的细节，损失函数的使用）；理解Adaboost和GBDT算法的联系；理解GBDT使用的梯度上升法与优化算法梯度下降法的区别；GBDT相比于SVM以及LR的优势。XGBboost相比于GBDT的改进（参加过机器学习算法比赛的同学可能会问）
4. 集成学习bagging（4星）：bagging算法的思想；为什么bagging能降低模型的方差；bagging算法与DNN中dropout技术思想的一致性；random forest算法中怎么增加随机性。
5. K-means（4星）：会手撕代码；k-means算法中包含的贝叶斯先验假设；选择聚类中心的改进方式；聚类簇数k选择的改进方式；和GMM的区别与联系；证明k-means算法的收敛性（有点超纲，面经上看到过，LZ没被问过）
6. 线性回归（4星）：权重更新方式的推导，包括矩阵形式的和非矩阵形式的（西瓜书上有）；包含L1或者L2正则化的权重更新的推导；L1/L2正则化包含的贝叶斯先验假设（或者从多个角度解释L1/L2对特征选择的作用）；在包含重复特征情况下，线性回归存在的问题，L1正则化是否能解决等细节问题。
7. 贝叶斯决策（3星）：个人觉得很少有面试官会直接问贝叶斯决策，最多就问一个先验概率和后验概率的联系，但是朴素贝叶斯的思想会在很多算法中体现，比如L1、L2正则化的贝叶斯先验假设，期望最大化算法与最小二乘法的联系，k-means包含的贝叶斯先验假设等。所以理解贝叶斯的思想是核心。
8. 决策树（2星，提问概率低）：包含特征选择，决策树的生成，决策树的剪枝三方面。特征选择包含利用信息增益、信息增益比、以及基尼系数进行特征选择（三个指标的公式最好记住）；决策树的剪枝，包括预剪枝和后剪枝方法（细节最好掌握）；三种决策树的区别，各自优点。
9. EM算法（2星，提问概率低）：理解EM算法的思想；使用EM算法求解GMM模型的思想、步骤；
10. 马尔科夫模型（1星，提问概率极低）：3个基本问题以及对应求解算法，要理解（前向后向算法、B-W算法、维特比算法）
11. KNN（1星，提问概率极低）：KNN的思想，KNN算法的影响因素，K值选择对模型的影响。

优化算法总结：mini-batch梯度下降法、动量法、AdaGrad、RMSProp、Adam等。能理解各优化算法的优缺点，以及在算法演化的过程中分别克服了什么问题，非常流畅地向面试官阐述，仿佛算法是我们自己提出一般；各种算法梯度更新的公式能手写。

• 降维的方式（PCA、LDA）：算法思想，PCA特征降维公式推导。
• 模型评价指标：准确率（accuracy）、精确率（precision）、召回率（recall），各自的定义，以及在不同的极端情况下各个指标的变化情况；PR曲线的绘制；使用PR曲线判断模型好坏；ROC曲线的横坐标、纵坐标意义；ROC曲线和PR曲线的区别；AUC的意义；AUC的计算公式。
• l特征工程：图像数据不足情况下的处理办法；数据不平衡情况下的处理办法。
• l杂乱的知识点：生成模型和判别模型的定义，区别，分别包含哪些算法；谱聚类了解一下；各种距离公式总结一下；各种损失函数总结一下。
• l深度学习的基础知识也要掌握，包括从AleNet开始典型模型的结构、模型梯度消失梯度爆炸的原因/解决办法、模型参数初始化的方式、BP的推导、BN/LN的区别、参数数量的计算、feature-map尺寸的计算、感受野的计算公式、各种激励函数的优缺点等。
• 由于LZ研究生的研究方向为强化学习（RL），因此如果面试相关岗位的同学也可以参考一波：

1）  RL中Q值的定义

2） RL中基于值函数的和基于PG算法的优缺点以及适用场景

3）  有模型RL算法和无模型RL算法的区别

4） RL中on-policy以及off-policy策略的区别，以及有哪些off-policy的方式

5）  原始PG算法，权重更新公式的推导

6） DP、蒙特卡洛采样、TD法各自的思想。

7）  理解贝尔曼方程。

8）  典型的RL算法，要理解思想，理解改进点。（1）Q-learning、DQN、Double DQN、Priority Replay DQN、Dueling DQN各自的改进点，要理解，不要背CSDN，尤其是后3者的改进。（2）REINFORCE 算法、 AC算法、A2C算法、A3C算法、DDPG算法。要理解。

RL的知识点我虽然写的少，但是要真正掌握并不容易，目前而言应用场景主要有两个（游戏AI-网易雷火、搜索推荐-阿里/快手），在面试的过程中，最好有相关项目的经历，或者相关paper，不然面试官很难切入提问。