笔试季又到了每年六七月份各个大厂的实习生招聘笔试都会准时拉开序幕。当年网易2018实习生招聘的机器学习算法岗位笔试题在牛客网上被翻来覆去讨论了很久很多准备校招的同学都把它当成一份重要的复习素材。这篇文章就当一份备战复盘把我对这套笔试题的考察目标、知识点拆解、做题思路以及后来面试环节中延伸出来的问题整体梳理一遍。机器学习基础、数据结构和算法、编程基本功这三个大块几乎是雷打不动的出题范围把每个部分怎么复习、怎么答题讲清楚对正准备算法或机器学习方向实习面试的同学会很有帮助。1. 笔试前先摸清机器学习算法实习生到底在考什么1.1 从岗位JD反推出考察范围很多人一上来就刷题、背概念但我觉得第一件事应该是站在出题人的角度想一个问题一个机器学习算法实习生入职之后最需要快速胜任的工作是什么无非是这几类处理数据、清洗特征、搭模型、调参、跑实验、分析结果偶尔还要写一些数据处理的脚本。所以笔试不会考特别偏门的深度模型细节而是把重心放在基础能力上。具体拆开考察范围基本是三大块。第一块是机器学习基础包括典型的监督学习算法逻辑回归、决策树、SVM、KNN、无监督学习K-Means、DBSCAN、集成学习随机森林、GBDT、特征工程、模型评估和调参。第二块是数据结构和算法字符串匹配、排序、图论、贪心、动态规划这些都是每届必考的内容。第三块是编程能力和工程基础要求你在限定时间内用Python、C或者Java把算法实现出来这里面对输入输出处理、边界条件、复杂度控制的要求往往比单纯“写对”更高。还有一个很多人会忽略的点概率统计和线性代数虽然没有单独成模块但会穿插在选择题和问答题里。比如给你一个贝叶斯公式的简单应用或者问一个矩阵的秩是多少这些都属于“默认你已经会了”的内容。所以复习的时候不能只盯机器学习算法数学基础也要顺手补一补。1.2 题型结构与时间分配策略网易这套笔试的题型我印象中大致是选择题单选和多选混合、编程题、以及一到两道主观问答题。选择题覆盖机器学习概念、数据结构基础、概率统计小计算编程题一般两到三道难度梯度拉开第一道可能是简单模拟第二道是常见算法模板题最后一道可能带上剪枝、状态压缩或者某种优化属于区分度较高的题。时间分配上我的建议是选择题控制在25到30分钟以内不要在一道概念题上纠结太久。编程题留出一个小时以上因为调试代码非常吃时间。主观题如果有建议放到最后写先保证编程题有分可拿。很多同学挂在笔试上不是不会做而是时间分配出了问题最后的编程题明明会写却因为前面选择题卡太久没时间敲完这非常亏。另外要注意选择题的多选部分通常没有“少选给一半分”的说法错一个就全错。所以拿不准的选项宁可不选也不要乱选蒙错不如少选。2. 机器学习基础高频考点与答题思路2.1 特征工程与数据预处理容易被忽视的送分题实习生面试中特征工程几乎是必问的笔试里也经常以选择题和简答题的形式出现。我当时复习的时候最深的体会是它考察的不是你会不会用sklearn的某个API而是对每个操作背后的原因是否清楚。比如“为什么要做特征归一化”这个问题标准回答是对于基于梯度下降的模型逻辑回归、线性回归、神经网络特征尺度不一致会使得损失函数的等高线呈椭圆形导致梯度下降路径震荡、收敛变慢对于基于距离度量的模型KNN、K-Means、SVM尺度大的特征会主导距离计算稀释其他特征的影响。再比如连续特征离散化很多人只知道“分箱”这个操作却不清楚它为什么有效离散化之后模型对异常数据更鲁棒减少了过拟合风险同时特征之间可以做交叉引入非线性对线性模型来说离散化的每个bin都相当于学到一个独立的权重表达能力反而更强。缺失值处理也是个高频点。笔试如果问你“某一列缺失率达到50%怎么处理”不能只说“填充均值”或者“删除”要分情况如果该特征是从某个外部来源拼接进来的缺失本身可能代表一种状态可以单独建一个“是否缺失”的指示特征如果缺失是随机的可以用均值、中位数、众数填充模型对分布影响不大如果是时间序列数据要优先用前后填充。我当时在笔记里记了一句话没有绝对最优的填充方法只有结合业务和数据分布才能判断。这个思路面试官很吃这一套。2.2 模型评估与调参偏差方差、交叉验证、评估指标这一块几乎是所有机器学习岗位笔试的稳定输出点考核的其实是你有没有真正做过模型实验。选择题喜欢问“过拟合怎么办”“欠拟合怎么办”参考答案很容易背但要说出为什么就比较考验理解。过拟合的对策包括增加训练数据、降低模型复杂度、正则化、早停、Dropout。欠拟合的对策则是增加模型复杂度、引入更多特征、减少正则化强度。这个里面有一个比较容易混淆的地方正则化权重过大会把模型推向欠拟合权重过小又会回到过拟合。所以调参就是一个在偏差和方差之间找平衡的过程。我当时复习的时候把偏差方差分解公式写下来再对照那句“高偏差意味着欠拟合高方差意味着过拟合”整个思路就清晰了。评估指标也是考察重点尤其是分类问题。什么时候看准确率、什么时候看精确率和召回率、什么时候看AUC这里面的门道比想象中多。准确率在正负样本均衡时好使样本不平衡的情况下会失真。比如一个二分类问题负样本占95%模型全预测为负类准确率也有95%看起来很美但没有实际价值。这时候就要看精确率、召回率、F1或者直接看AUC。AUC衡量的是模型把正样本排在负样本前面的能力对样本不平衡相对不敏感所以实际业务中用的非常多。还有一个常考的概念是交叉验证。为什么要用交叉验证而不是简单的划分训练集和测试集因为小数据集上单次划分的方差很大可能这次划分模型表现好下次划分表现差不能真实反映模型泛化能力。K折交叉验证把数据分成K份轮流做验证集最后取平均值结果更稳定。笔试如果问K怎么选常用5或10数据量小的时候可以增大K数据量很大的时候直接用留出法就行没必要做交叉验证太费时间。2.3 核心算法对比会实现还要能说清本质机器学习算法的考察不会只停留在会调用模型而是要求你理解原理并且在不同的算法之间做比较。我复习的时候做了一张表把高频算法从头到尾捋了一遍笔试选择题和面试问答基本都够用了。算法核心思想常见损失/准则关键超参数适用场景线性/逻辑回归线性决策边界概率输出交叉熵正则化系数、学习率高维稀疏特征、在线学习决策树递归划分特征空间信息增益/基尼指数最大深度、最小样本数可解释性要求高的场景SVM最大化分类间隔合页损失核函数、C、gamma小样本、高维、非线性分类K-Means基于距离的原型聚类簇内平方和K值、初始化方式大规模样本、球形簇DBSCAN基于密度的聚类密度可达eps、min_samples任意形状簇、噪声数据随机森林Bagging 随机特征选择平均/投票树数量、特征采样数高维表格数据、抗过拟合GBDT/XGBoostBoosting逐步拟合残差平方误差/对数损失学习率、树数量、深度结构化数据、排序、回归对比它们的时候有几个常见问法SVM和逻辑回归有什么本质区别答案的核心是SVM只关注支持向量离决策边界最近的点逻辑回归关注全部样本SVM自带间隔最大化的特点泛化能力有理论保证逻辑回归输出概率、易于扩展和在线更新。决策树和线性模型比优点是不需要特征归一化、能捕获非线性关系、可解释性强缺点是容易过拟合、对噪声敏感。K-Means和DBSCAN比K-Means没法处理非凸簇必须指定K对异常值敏感DBSCAN不需要指定簇个数能识别噪声点但eps和min_samples两个参数对结果影响很大。关于集成学习笔试选择题比较爱问随机森林和GBDT的区别。随机森林的基学习器是并行的每个树独立训练靠投票降低方差GBDT是串行的每棵树拟合前面的残差降低偏差。所以随机森林更不容易过拟合GBDT在训练集上拟合能力更强但调参不当更容易过拟合。当时我复习到这儿又把XGBoost对GBDT的改进总结了一遍加入了二阶导数信息、正则项控制复杂度、列抽样和近似直方图算法加速这些点后来在面试中也确实被问到了。3. 数据结构与算法笔试真正的硬骨头3.1 字符串算法KMP为什么年年出现热词里专门有“在KMP算法中对于模式串pabacaba其next数组”这种问题说明这类题在笔试里非常常见。KMP考的不是算法本身多难而是你有没有真正理解next数组的计算过程。很多同学会背模板但让你手工模拟一遍next数组就慌了这恰恰是笔试选择题最爱出的形式。简单说一下KMP的核心思路暴力匹配在失配时模式串只右移一位之前匹配过的信息全部丢弃复杂度是O(n*m)。KMP利用模式串自身的前后缀匹配情况构造一个next数组失配时根据next跳转避免重新匹配已经确定一致的字符时间复杂度降到O(nm)。next数组的语义在考研教材和竞赛圈里有两个版本网易当年的题用的是“next[i]定义为前缀串中最长相等前后缀的长度”注意这里和部分教材里next[0]-1的语法不同。对于模式串pabacaba我手动算一遍前缀逐个位置求最长相等前后缀长度。第一个字符a没有真前后缀next值为0前两个字符ab最长相等前后缀长度为0前三个字符aba前缀a和后缀a相等长度为1前四个abac没有相等前后缀为0前五个abaca前缀a和后缀a相等长度为1前六个abacab前后缀ab相等长度为2整个串abacaba前缀aba和后缀aba相等长度为3。所以next数组就是[0,0,1,0,1,2,3]。这个计算过程看起来简单但笔试中给你一个字符串让你选next数组的时候只要在“真前后缀”和“是否包含串本身”上有犹豫就容易算错。当时我复习KMP的时候还顺带把字符串哈希、Trie树、AC自动机看了一眼并不是说笔试一定会考而是因为它们都属于字符串算法的大类把套路放在一起记忆遇到类似题不至于完全陌生。3.2 排序与图论从冒泡到堆排序再到二分图排序算法在任何一家公司的笔试里都是“基础中的基础”。选择题常考的是各排序算法的稳定性和复杂度对比冒泡、插入、归并是稳定的选择、快排、堆排、希尔是不稳定的。时间复杂度上快排平均O(nlogn)、最坏O(n^2)归并和堆排稳定在O(nlogn)。空间复杂度上归并需要O(n)额外空间快排需要O(logn)的栈空间递归堆排是O(1)原地排序。这道题只要背熟就是白送分。堆排序值得单独拿出来说因为它虽然写起来麻烦但考察点很丰富。笔试编程题里如果要求“找到数组里最大的K个数”很多人第一反应是排序但标准答案是用一个大小为K的小顶堆遍历一遍数组比堆顶大就替换并调整堆复杂度O(nlogK)。这比全排序的O(nlogn)要快尤其是K远小于n的时候。我当时笔试就靠这个思路解决了一道类似的题目所以对堆的原理记得特别牢。图论方面热词里出现的Dijkstra、二分图HK算法都是笔试/面试中常涉及的知识点。Dijkstra求单源最短路核心是贪心思想每次从未确定最短路的节点中选距离最小的松弛它的邻居。笔试如果出题通常不会让你从零实现Dijkstra更多的可能是问“为什么Dijkstra不能处理负权边”——因为它一旦确定某个节点的最短路就默认后续不会再被更新而负权边可能让这个“已确定”的路径不再最优。这个理论问题比实现本身更常被问。二分图匹配算法基础版是匈牙利算法HK算法是它的优化版通过BFS分层找最短增广路然后用DFS同时找多条增广路把复杂度从O(VE)优化到O(E*sqrt(V))。这类题在纯业务的算法实习里可能不常见但在正规大厂笔试里属于拓展知识看到不用怕理解思想就够了。3.3 贪心、动态规划与剪枝识别套路是关键贪心和动态规划是笔试编程题里最能拉开差距的部分。很多人觉得难是因为没有总结出识别的套路。我当时总结的经验是如果题目要你“选择若干元素使某目标函数最大/最小”先看看有没有“贪心选择性质”和“无后效性”。比如活动安排问题按结束时间早的优先选择就是典型的贪心但同样是选择问题如果状态之间有依赖关系贪心就不成立了得回头想DP。动态规划的通用解法是四个步骤定义状态、写出状态转移方程、确定初始化和边界条件、确认遍历顺序。面试问DP题最怕的是你上来就写代码结果状态定义错了。比如最长上升子序列状态dp[i]定义为“以第i个元素结尾的最长上升子序列长度”转移方程就是dp[i] max(dp[j] 1) (j i且a[j] a[i])。笔试编程题的时间有限很难当场想出新题型的转移方程所以备考阶段要把经典问题模型吃透背包问题、最长公共子序列、最长上升子序列、编辑距离、区间DP、状态压缩DP。剪枝这个词在热词里也出现了。笔试中有一个高频搜索场景给定一个集合找满足条件的子集或者求排列组合数常见的做法是回溯加剪枝。剪枝的本质是在递归搜索的过程中提前判断当前路径不可能产生解直接返回。比如组合总和问题如果当前和已经大于目标值就不需要再往后加了又比如求排列时如果当前前缀已经违反了某个约束直接剪掉。剪枝的好坏直接影响搜索效率好的剪枝能把指数级复杂度降到可接受范围。当年笔试有一道题就是搜索加剪枝我没想清楚剪枝条件提交后超时白白丢了大题的分这个教训后来一直提醒我写搜索题之前先画递归树分析哪些分支必死再动手写代码。4. 编程题实战从读题到AC的完整流程4.1 输入输出与边界条件的坑笔试编程题和平时写业务代码最大的不同是它要求你处理裸的输入输出而且平台通常用多个测试用例跑你的代码只要有一个边界没过这道题就判0分。很多同学代码逻辑没问题却挂在了输入输出上特别可惜。先记住一条当题目没有明确说明测试用例数量时要用循环读取输入。C里就是while (cin n)Python里用sys.stdin.read()一次性读取再按行split。还有字符串处理时的常见坑题目给的字符串可能带空格用cin s会截断得用getline行末可能有回车符Python里要strip()。我笔试时遇到过一道题数据范围写了n在int范围内但输出要求用long long结果我只用了int溢出导致WA排查了半天才发现。边界条件是最容易丢分的地方。输入为空、n0、n1、负数、极大值这些都要在写代码时检查一遍。笔试现场的调试手段有限没有IDE的断点调试建议养成“写完代码后在关键分支打log”的习惯或者在本地构造几个典型的边界用例跑一遍再提交。时间充裕的话还可以写一个暴力解法用随机小数据对拍虽然笨但在ACM模式下非常有效。4.2 复杂度估算与剪枝实战编写代码之前先做一个时间复杂度估算。笔试OJ一秒大约能跑1e8次简单运算Python要再打个对折可能1e7到1e8左右就顶天了。如果数据范围是n10^5你写了一个O(n^2)的算法基本必超时必须想O(nlogn)或O(n)的方案。如果n20那就放心用2^n的搜索或者状态压缩但注意加上剪枝。我记得有一道模拟题的n是10^5要求求数组中的逆序对数量。最直接的双重循环O(n^2)显然不行正确的方向是归并排序或者树状数组O(nlogn)。这种复杂度分析能力笔试时就是用来快速排错的手段如果你写完代码发现算法复杂度是O(n^2)再回到题目看数据范围心里基本就知道该换解法了。剪枝在笔试编程题里也非常重要尤其是搜索问题。经典例子是八皇后、迷宫最短路径、组合总和。剪枝条件可以从几个角度想约束条件剪枝不满足题设直接返回、最优性剪枝当前结果已经比已知最优差直接返回、对称性剪枝相同状态只搜一次。我个人的经验是写搜索题时先把不带剪枝的暴力版本写出来跑通小数据再用剪枝优化这样调试压力小很多也更容易保证逻辑正确。5. 从笔试到面试常见追问与算法原理扩展5.1 面试追问笔试题目背后的延伸问题笔试结束后的面试环节面试官往往会从笔试中的某些题目出发追问一系列延伸问题。比如笔试里考了K-Means面试官可能就会接着问K-Means的K怎么选初始中心点怎么选K-Means的收敛性怎么理解这类追问的用意是看你有没有把知识点串成体系。我当时被问到“K-Means一定会收敛吗”时回答是在固定簇分配的基础上每次更新中心点都会使簇内平方和SSE下降而SSE大于等于0所以算法在有限次迭代内必然收敛到一个局部最优解但不能保证是全局最优。这么说之后面试官又追问“那怎么降低陷入局部最优的风险”答案就是多跑几次不同的随机初始化或者用K-Means改进初始中心选择。一个基础算法面试官能连续问三四层复习的时候最好自己也往这个方向准备。关于模型选择面试官很喜欢问“这个场景你会选什么模型为什么”。回答的时候别只给一个名字要讲清楚理由和备选方案。比如回归问题先看数据量数据量小、特征维度高选线性回归或岭回归数据量中等、特征有非线性关系可以用GBDT或随机森林如果对可解释性要求高决策树或线性模型优先。这种“场景-模型-理由”的答题结构面试官听着会觉得你真有实践经验。5.2 非典型算法考点粒子群、模拟退火、Rete、音频重采样热词里出现的“粒子群算法原理”“模拟退火算法”“规则引擎drools的rete算法实现原理”“音频重采样算法”都不是机器学习算法实习生笔试的核心考点但它们反映出一个趋势大厂对候选人的视野要求比较宽时不时会夹带一些非典型问题考察你有没有主动接触过这些常见的工程/优化算法。粒子群优化PSO是模拟鸟群觅食的启发式优化算法每个粒子有位置和速度通过个体最优和全局最优更新速度然后更新位置。它适合做连续空间的非线性优化缺点是容易早熟收敛。模拟退火算法的核心是从较高温度开始以一定概率接受更差的解随着温度下降接受差解的概率越来越小以此跳出局部最优。这两个算法如果笔试里出现大概率是以选择题的形式问“哪个算法是基于概率接受差解来跳出局部最优”答案就是模拟退火知道这个特点就不容易错。Rete算法是规则引擎比如Drools里用于高效匹配规则的模式匹配算法它的核心思路是构建一个网络Alpha网络和Beta网络共享规则之间的公共条件避免每次事实变更都从头匹配所有规则。笔试如果问它多半是考察你有没有工程中间件的知识面而不是让你手写Rete。音频重采样算法常见的有线性插值、三次样条插值、基于FFT的重采样涉及信号处理属于跨领域问题。遇到这种题我的做法是先摆出基本原理再说明具体实现时需要注意的边界即使不完全会也要让面试官看到你有分析问题的能力。6. 备考资料与时间规划一条实操过的复习路径最后聊聊备考的资料和时间规划。机器学习方向我当时刷的是周志华的《机器学习》西瓜书和李航的《统计学习方法》西瓜书重理解统计学习方法重推导。如果时间紧张优先吃透逻辑回归、决策树、SVM、贝叶斯、K-Means、GBDT这几章配套做课后题。视频方面吴恩达的机器学习课程在Coursera上很经典适合零基础入门进阶可以看林轩田的《机器学习基石》对理解SVM和特征转换很有帮助。数据结构与算法我用的复习节奏是先花两周把《剑指Offer》过一遍掌握常见的面试题套路然后按专题刷LeetCode字符串、排序、链表、树、图、贪心、动态规划各刷一批考前一周用牛客网的往年真题模拟笔试环境卡时间2小时做完整套题。这里特别想说模拟笔试非常重要因为真实笔试的紧张感、时间压力、IDE环境和平时刷题完全不一样提前适应能显著降低失误率。还有一条个人体会想分享笔试之后一定要写复盘笔记把每道错题涉及的知识点记录下来。我当时建了一个Markdown笔记按“机器学习基础”“排序/字符串/图论”“DP/贪心/搜索”“数学/概率统计”四个专题归档每次笔试前过一遍效率比重新翻书高得多。面试官看到你带着笔记过去的印象也好至少说明你是一个善于总结的人。整个网易2018实习生招聘机器学习算法实习生的笔试题量不算少难度梯度拉得也挺开。现在回头想它考察的核心从来不是“你背了多少模型”而是“你有没有形成一套扎实的机器学习基本功和算法思维”。如果你是正在准备实习的同学我建议把重心放在理解和推导上模型API调用谁都会但能说清楚特征为什么这样处理、算法为什么这样设计的人并不多。多做几次全真模拟多复盘错题这个过程本身就是在帮你建立真正的竞争力。