机器学习算法工程师笔试考察全景：网易2018真题复盘

1. 笔试考察全景一份卷子想筛出什么人1.1 网易2018校招机器学习算法工程师的岗位画像2018年前后正是国内互联网公司大规模布局AI业务的关键时期。网易的岗位JD里写的是机器学习算法工程师但实际招进去的人要干的活非常杂可能是做网易云音乐的推荐可能是做严选商城的用户画像也可能是做考拉的海关报关单信息抽取甚至可能是做游戏里的对战AI。所以这份笔试卷的考察范围基本可以理解为什么都得会一点但必须有扎实的主干知识。我当时刷这份卷子的最大感受是它不像有些公司那样只考深度学习框架API怎么调也不像某些外企那样全是纯数学推导。网易的题更偏向你作为算法工程师能不能独立解决一个从数据到模型到上线的完整问题。这其实和2018年整个行业的状态有关——那时候大家都在从发论文转向做落地所以笔试里的传统机器学习题占比非常高深度学习反而没有想象中那么多各类数据结构和算法题则保持了大厂笔试一贯的硬核风格。从整体结构来看这份笔试卷大致可以分成三块机器学习基础与理论、算法编程与数据结构、逻辑推理与场景设计。第一块考察的是你知不知道第二块考察的是你能不能写出来第三块考察的是你碰到实际问题会不会拆解。下面我按这个顺序把每一块的核心考点和我的做题思路拆开讲顺带把一些容易踩的坑也一起说了。1.2 笔试卷结构拆解三个维度的能力筛选先说整体观感。网易这份卷子的题量不算特别大但覆盖范围广时间其实很紧张。很多同学拿到卷子习惯从第一题做到最后一题这在下午的机试里是最大的错误。我的建议是先花两分钟把整张卷子扫一遍识别出送分题中等题硬骨头三类然后按性价比排优先级——因为校招笔试看的不是你每道题都对而是你在有限时间内拿到的总分。机器学习基础部分的题目风格非常教材化比如贝叶斯公式的具体计算、SVM的核函数选择、决策树的信息增益计算这属于送分题但前提是你真的手算过而不是只在sklearn里调过包。算法编程部分则比较残酷基本都是LeetCode中等难度以上的题而且会出一些经典的字符串和排序问题比如KMP算法求next数组这要求你对基础算法的原理有真正的理解光背模板是过不去的。场景设计题则没有标准答案考察的是你面对一个模糊问题时能不能给出清晰的解决思路这在后面的章节里我会详细展开。2. 机器学习基础题手推公式才是硬功夫2.1 贝叶斯公式与概率题不只是套公式贝叶斯公式这类题几乎是所有算法岗笔试的标配网易也不例外。但我想说的一个重点是这类题目的难点往往不在于公式本身而在于你能否从题目描述中准确识别出先验概率、似然概率和全概率分别对应什么。我记得卷子里有一道题是给定一个分类器在两类样本上的准确率和召回率让你反推某个样本被分到某一类的后验概率。这种题如果对条件概率的含义理解不透很容易把分子分母搞反。当时我自己的做法是碰到这类题先在草稿纸上画一个简单的表格把真实类别和预测类别的四种组合列出来然后把题目给的数字填进去最后再套贝叶斯公式。这个方法看起来笨但永远不会错。另外一个经常考的变形是朴素贝叶斯的计算它假设特征之间条件独立所以只需要把各个特征的条件概率乘起来再乘上先验。这种题一定要看清楚题目给的是拉普拉斯平滑还是普通频率估计2018年前后很多笔试题喜欢在平滑系数上做文章坑了不少人。2.2 SVM、决策树、GBDT等经典模型对比机器学习基础部分特别爱考不同模型之间的对比比如SVM和逻辑回归的区别、决策树和随机森林的区别、GBDT和XGBoost的区别。这类题考察的是你能否从损失函数、训练方式、正则化手段、适用场景等维度系统地分析一个模型。网易的卷子里出现过一道让我印象深刻的题在样本量特别大、特征维度也特别高的情况下SVM和GBDT哪个更适用为什么。这道题的正确答案要从SVM的核函数矩阵计算复杂度出发。传统的SVM在求解时需要计算样本两两之间的核函数矩阵这个矩阵的大小是n乘以nn是样本数。当n达到百万级别时这个矩阵根本存不下训练时间也是灾难。而GBDT是通过不断拟合残差来迭代的虽然训练过程是串行的但每棵树的复杂度只跟当前特征维度有关对样本量的扩展性要好得多。当然libsvm和liblinear这类工具包其实做了一些近似优化在大规模场景下也不是完全不能用但笔试里考察的还是这个最核心的思想。决策树相关的题目核心考察点是特征选择指标信息增益、信息增益比、基尼指数。这里我建议你把三种指标的计算公式都手推一遍尤其是熵的计算里那个负号和对数底数做题的时候特别容易出错。网易出过一道题给了一个包含16个样本的数据集其中某个特征有4个取值让你计算用这个特征分裂后的信息增益是多少。这种题就看你能不能清晰统计出每个分支下的类别分布并把加权熵算对。2.3 K-Means聚类手算过程迭代收敛的直观理解聚类这块K-Means是绝对的考点。网易的卷子里出现过需要手算K-Means迭代过程的题给定几个二维坐标点初始质心给定让你写出第一轮迭代后的簇划分和新质心位置。这类题本身不难就是欧氏距离的计算加均值求解但很多人会忽略一个关键点K-Means的均值是簇内所有点的算术平均而不是中间点所以每次迭代后质心可能落在一个不是数据点的位置。这个点如果没理解后面第二轮迭代就全错了。还有一个常被拿出来考的概念是K-Means的收敛性。你要知道K-Means的迭代过程等价于在优化一个目标函数这个目标函数就是每个点到其所属簇质心的距离平方和。每一次分配样本到最近质心和重新计算质心两步都会让这个目标函数值不增所以算法一定收敛但收敛到的可能是局部最优。这就是为什么实际应用中一般会跑多次选目标函数值最小的那次结果。笔试里如果问K-Means一定能收敛到全局最优吗答案是不能。3. 算法编程题从模板到真正理解3.1 KMP算法与next数组推导字符串匹配的经典考验KMP算法是校招笔试里出现频率极高的考点网易2018年的卷子也不例外。KMP的核心思想是利用已匹配的部分信息让模式串尽可能多地向右滑动避免主串指针回溯。而实现这个滑动的关键就是next数组。热词里有一个很具体的例子模式串abacaba让我们求它的next数组。这个例子选得非常典型因为它包含了几种不同的前后缀情况。next数组的定义在不同的教材里略有差异有的定义next[i]为前i个字符组成的子串的最长相同前后缀长度有的定义为失配时跳转的位置。网易的卷子里明确写了next[i]代表的是前i个字符中最长相同前后缀的长度这个定义和大多数中文教材一致。手算abacaba的next数组过程是这样的对于i1字符是a前后缀都只能是空串所以next[1]0。对于i2子串是ab前缀有a后缀有b没有相同的前后缀next[2]0。对于i3子串是aba前缀有a、ab后缀有ba、a最长的相同前后缀是a长度为1所以next[3]1。对于i4子串是abac前缀a、ab、aba后缀bac、ac、c没有相同的next[4]0。对于i5子串是abaca前缀有a、ab、aba、abac后缀有baca、aca、ca、a最长的相同前后缀是anext[5]1。对于i6子串是abacab前缀有a、ab、aba、abac、abaca后缀有bacab、acab、cab、ab、b可以看到ab是相同的前后缀长度为2所以next[6]2。对于i7子串是abacaba前缀有a、ab、aba、abac、abaca、abacab后缀有bacaba、acaba、caba、aba、ba、aaba是相同的前后缀长度为3next[7]3。这道题如果你只是背过KMP代码但没有真正理解过next数组是怎么推出的大概率会卡住。所以我的建议是考前一定要把next数组的推导过程亲手练几遍而且要练到不用看代码只靠定义就能推出任意模式串的next数组的程度。3.2 排序算法选型时间复杂度只是起点排序算法这块几乎每份笔试都会考。网易的卷子喜欢考的是比较排序、快排、堆排、归并排序之间的对比以及特定场景下选哪种排序更合适。单纯背快排平均O(nlogn)最坏O(n^2)这种话是不够的题目会给你具体的数据特征让你做工程上的取舍。我记得有这样一个典型的考察点如果数据量很大但每个数据都不大比如要给数百万个年龄值排序这时候用哪种排序算法最合适。这类题的答案是计数排序或者桶排序因为年龄的取值范围只有0到100多我们可以用线性时间完成排序这就是非比较排序算法的优势。如果你只背了快排、堆排这些比较排序的复杂度碰到这类题目就会无从下手。另外一个考点是会问你排序算法的稳定性。稳定性的含义是如果两个元素的键值相同排序后它们的相对顺序能否保持。归并排序是稳定的快排和堆排是不稳定的。为什么笔试爱考这个因为在实际工程里我们经常需要先按一个字段排序再按另一个字段排序如果第二轮排序是稳定的那第一轮的排序结果就会保留。这个问题在场景设计题里也经常隐晦地出现需要你具备稳定性的意识。3.3 其他常考的算法题贪心、二分、DP除了字符串和排序网易的笔试编程题里还大量涉及贪心算法、二分查找和动态规划。贪心算法的题目往往看起来像DP因为都是求最优解但贪心的特点是每一步都选择局部最优而且不存在回退。我在考场上养成的习惯是先尝试用贪心思路想问题举几个test case验证贪心选择是否正确如果发现反例就果断切换成DP。二分查找这个考点网易喜欢考它的变体比如找旋转数组的最小值、找第一个大于target的位置、在有序矩阵中搜索目标值。这类题的共同点是边界条件极其容易出错。我的经验是写二分查找的时候一定要在脑子里明确你的循环不变量到底是左闭右开还是左闭右闭。两种写法都行但面试官看你代码的时候会特别注意你能不能正确处理mid的计算、左指针和右指针的更新方式。推荐统一用左闭右开的写法因为它的边界处理在大多数情况下更不容易出错。DP题是区分度最大的一类题。网易的卷子里出现过背包问题的变种以及需要状态压缩的DP。这类题的难点不在写出递推公式而在于把原问题抽象成状态转移方程。我个人的训练方法是把DP题分类整理比如背包类字符串编辑类区间DP类状压DP类每类做透10道题总结出这类状态的共同套路。笔试里的DP题基本都能归到这些大类里很少会出真正的偏题怪题。4. 进阶模型与优化算法知其所以然4.1 粒子群算法与模拟退火启发式搜索的入门口味热词里出现了粒子群算法原理和模拟退火算法这说明在机器学习算法工程师的候选知识体系里不只包含梯度下降这一类确定性优化方法还包含启发式随机搜索算法。虽然网易2018年的卷子里没有直接考粒子群算法的大题但这类算法在讨论超参数搜索、特征选择、聚类初始化等问题时经常被提及作为知识储备是很有必要的。粒子群算法PSO的核心思想是模拟鸟群觅食。每个候选解被看作一个粒子它有两个属性位置和速度。每次迭代时粒子根据自己历史最优位置pbest和群体历史最优位置gbest来更新速度再由速度更新位置。速度更新的公式是一个加权组合当前速度乘以惯性权重加上认知项向自己历史最优靠近加上社会项向群体最优靠近。三个部分的系数分别称为惯性权重w、加速常数c1和c2。一个需要注意的细节是PSO的收敛性对参数非常敏感。w过大粒子会一直在更大的范围内搜索收敛慢w过小粒子会快速汇聚到当前最优附近容易陷入局部最优。在实际使用中通常会让w从0.9线性递减到0.4这样前期全局搜索能力强后期局部精细搜索能力强。这个细节如果能在笔试或面试中提到会显得你真正理解这个算法。模拟退火算法则是受金属退火过程启发的优化算法。它从高温开始允许以一定概率接受比当前解更差的解这个概率由Metropolis准则决定如果新解比当前解好直接接受如果新解更差以概率exp(-delta/T)接受其中delta是目标函数值的差T是当前温度。随着温度逐渐降低接受差解的概率越来越小最终收敛到一个稳定解。这个算法最核心的思想是以一定概率容忍暂时的变差来换取跳出局部最优的可能性这和贪心算法的绝不回退形成了鲜明对比。4.2 规则引擎与Rete算法工程落地中的算法思维热词里还有一个非常工程化的词规则引擎drools的rete算法实现原理和事实匹配过程。这个知识点出现在机器学习算法工程师的搜索词里我是有点意外的但仔细一想也合理算法工程师在实际工作中经常要处理规则和模型的配合问题。哪些逻辑用规则引擎做哪些用模型做边界怎么划这本身就是工程决策能力的一部分。Rete算法的核心是构建一个网络把规则的匹配过程拆解成多个阶段。它不是每条规则单独去匹配所有事实而是把规则之间的相同条件部分共享并且在网络中缓存中间匹配结果。当一个新事实加入时只需要在网络中传播这个事实更新受影响的部分即可。这就避免了每次都要对所有规则做全量匹配的性能开销。Rete算法有一个关键概念叫节点根节点之下有类型节点用于按事实类型分流再往下是alpha节点对应单个条件然后是beta节点用于两个条件之间的连接。事实在网络中流转匹配结果在beta节点中累积。这个结构和数据库查询优化里的共享子表达式思想非常像。虽然校招笔试考Rete算法的概率不大但如果你在简历里写了熟悉规则引擎或者面试聊到风控、反作弊这类大量依赖规则的系统时能说清楚Rete的原理绝对是个加分项。4.3 深度学习基础不只是调API回到机器学习算法工程师的老本行——深度学习。网易2018年的卷子里深度学习相关的题占比没有想象中高但凡是出了的题目都非常看重对基础公式的理解。比如卷积层输出尺寸的计算公式output_size (input_size - kernel_size 2 * padding) / stride 1这个公式必考而且会混合padding方式和stride一起考必须熟练到不出错。还有一个高频考点是反向传播的推导。网易不会让你手推一个完整的ResNet反向传播但会让你推导一个简单的两层全连接网络的梯度传播过程或者让你写出Softmax损失函数对输入的梯度。Softmax的梯度推导是一个经典坑点单独看Softmax函数它对输入向量的梯度是一个雅可比矩阵但在交叉熵损失下最终梯度会化简成非常优雅的形式——预测概率减去one-hot真实标签。这个化简过程建议自己推一遍不仅笔试有用面试手撕代码时也经常要用到。Batch Normalization在2018年是热门考点。它做的事情是在每个batch内对每一维特征做归一化然后通过两个可学习参数进行尺度变换和偏移。但它的训练和推理行为是不同的训练时用的是当前batch的均值和方差推理时用的是训练过程中累积的全局均值和方差。这个区别几乎每年都有公司的笔试题在考网易也不例外一定要记清楚。5. 实战复盘与备考策略那些没人告诉你的细节5.1 时间分配与做题顺序先抢分再攻坚我把网易这份卷子拿给几届学弟学妹做过测试发现一个共同的规律如果按题目顺序从前往后做大多数人会在两道中等难度的编程题上卡太久导致后面的场景设计题来不及写。这是一个非常可惜的失分点。我的推荐策略是这样的拿到卷子后先花5分钟快速浏览所有题目标记出看一眼就确定会做的题优先做这些。机器学习基础题和概率题一般属于这一类因为它们的计算量不大只要会就很快。然后是编程题里的简单题确保AC拿到最稳的分数。最后再集中精力攻克难题和场景设计题。整套卷子至少要预留30分钟给场景设计题因为这类题需要组织思路和文字表达写起来比想象中花时间。还有一个小技巧编程题如果卡住了不要死磕一道题超过20分钟。先写一个暴力解法保证通过一部分测试用例拿部分分数然后再考虑优化。很多笔试系统是按测试用例的比例给分的暴力解往往能拿到30%到50%的分数这比空着不写强太多。5.2 高频失分点汇总学长的避坑指南我把这些年看到的学生高频失分点整理成了下面这个表考前看一眼至少能帮你避开一半的坑失分点具体场景正确做法贝叶斯公式分子分母混淆给定召回率、精确率反推后验概率先画2x2混淆矩阵把数字填进去再算熵计算公式忘加负号或对数底数不一致计算信息增益时对每个子集加权求熵统一用log2先算整体熵再算条件熵K-Means质心更新错误把质心写成了簇内某个数据点质心是所有点的算术平均值不一定是数据集内的点KMP next数组推导错误模式串abacaba这类有重复前缀的串手工逐i推导特别注意最长相同前后缀的最长要求排序稳定性判断错误快排被误判为稳定排序记住结论稳定排序包括冒泡、插入、归并、计数、基数不稳定包括选择、快排、堆排卷积输出尺寸计算忘加padding或stride处理错已知输入尺寸、卷积核、padding、stride求输出套公式output (input - kernel 2*padding)/stride 1注意结果向下取整DP状态转移写对了但边界条件错背包问题初始化数组时越界先画小规模示例用手推验证一遍边界5.3 备考时间线从零基础到笔试合格的三步走如果你现在还在大二大三离校招还有一段时间我建议按下面的节奏来准备而不是考前一个月突击。突击能解决见过题型的问题但解决不了真正理解的问题而后者才是笔试拿高分的分水岭。第一阶段是打基础建议花六到八周。主线教材是周志华的《机器学习》也就是大家常说的西瓜书重点啃前三章绪论、模型评估与选择、线性模型和第七章贝叶斯分类器。同时配合李航的《统计学习方法》把感知机、KNN、朴素贝叶斯、决策树、SVM这几章的精讲内容吃透。这个阶段的目标不是做题而是建立公式推导的直觉。第二阶段是刷题突破建议花四到六周。侧重于数据结构与算法编程题库用LeetCode的Hot 100外加剑指Offer每天保持两道题的节奏。需要注意的是刷题不要只刷AC了就过一定要看题解里更优的解法并且把每道题用自己的话整理到笔记里标注出核心思路和边界条件。算法题的手感是靠每天持续练习维持的中断三天就会明显生疏。第三阶段是模拟冲刺建议考前两到三周开始。找近三年大厂算法岗的真题限时做整套卷子模拟真实考场氛围。做题时要注意控制时间做完后要复盘出错的知识点。我有几个朋友用这个方法把每套真题做两遍第一遍按真实考试来第二遍针对错题专门做变式训练效果非常明显。我在实际陪跑过程中发现能把三套真题复盘两遍的人笔试成绩基本都能超过80%的竞争者。5.4 场景设计题的答题套路把自己当成在职算法工程师网易的笔试卷最后一般会有一两道开放性的场景设计题比如如何设计一个音乐推荐系统的冷启动方案或者如何用机器学习方法识别虚假评论。这类题没有标准答案但评分标准其实是看你能不能展现出完整的解决问题的框架。我在实际工作中学到的答题框架是这样四步第一步明确目标——你要优化的核心指标是什么第二步盘点数据——当前有哪些数据可以用哪些数据需要新增采集第三步选择方案——用有监督还是无监督用什么模型为什么第四步评估与迭代——怎么做离线评估上线后看什么指标怎么应对bad case。这个框架在面试回答里同样适用它展示的是你的工程思维而不是背了多少个模型的名字。还需要注意的一点是场景设计题非常看重你对这个业务场景的理解。比如设计虚假评论识别方案时如果只写用LSTM分类那基本拿不到高分。更合理的回答是先说虚假评论的特征短文本、高频重复、无真实购买记录等再说如何构造特征然后说模型选型xgb或深度学习都可以最后说冷启动问题怎么解决。这种思路体现的是你真的思考过这个业务而不仅仅是套了一个模型上去。