网易校招机器学习算法笔试题全解析：从KMP到模型评估与特征工程

网易2018校招机器学习算法工程师笔试卷，现在回过头看依然是一份很有代表性的考察样本。那阵子算法岗远没有现在这么卷，但这张卷子已经相当扎实地覆盖了机器学习与算法的核心骨架：数据结构、经典算法、统计学习理论、模型评估、特征工程，外加几道编程实战。我身边不少当年一起刷题的朋友，后来面试其他大厂时也都遇到同款知识点，所以这份卷子的参考价值并不随时间过期，反而很适合拿来检验基本功。如果你正在准备算法岗校招，或者刚入门机器学习想确认自己到底缺哪块，这份题目拆解能帮你把知识清单捋清楚。

1. 笔试全貌与考察逻辑拆解

1.1 一张卷子考了什么：题型与知识点分布

网易这套笔试卷的题型结构，基本沿用了国内互联网大厂算法岗笔试的成熟框架。从公开资料和参加过考试同学的复盘来看，大致可以分为四类：单选题、多选题、编程题、简答/推导题。每一类都有明确的考察侧重点，不是随便凑出来的。为了让没参加过的人有个直观感受，我把它整理成一张分布表。

这个时间分配是我根据当年实际答题节奏调整过的一版。考试总时长一般是一个半小时到两小时，最忌讳的就是在单选题上反复纠结。一张卷子的难度曲线通常不是均匀上升的，前面几道基础题反而是送分题，真正拉开差距的往往是编程题和最后一道综合推导题。

从知识点覆盖来看，排序算法、KMP、动态规划这些是代码题的常客；逻辑回归、SVM、决策树、朴素贝叶斯这些经典模型则是理论题的主力；再加一些概率统计和特征工程的内容。这套组合几乎成了后来几年互联网算法岗笔试的标准配方，原因很简单：它能在有限时间内同时考察候选人的代码功底和理论深度。

1.2 网易选这些题的真实意图

很多同学刷题时只关注“这题怎么做”，但很少去想“公司为什么出这题”。我当年吃过这个亏，直到面了多个团队才慢慢理解。网易这套卷子的出题逻辑，其实反映了算法岗招聘的三个底层诉求。

第一，区分“刷题型选手”和“原理型选手”。单选和多选里的机器学习概念题，表面上是考记忆，实际上是考理解。比如问“下列哪个指标不受类别不平衡影响”，如果只背过公式而没真正理解AUC和准确率的区别，很容易在这类题上翻车。第二，考察工程落地能力。编程题不会出纯竞赛难度的题目，而是在经典算法上加了业务化包装，比如给定用户行为序列求某个统计量，这本质上是在模拟真实场景中的数据清洗和特征计算。第三，检验学习深度。简答题里让推导逻辑回归的损失函数或解释SVM的对偶问题，就是在淘汰那些只会调库、不懂原理的候选人。

想明白这三点，你就能理解为什么网易笔试不考深度学习而重点考传统机器学习。不是因为深度学习不重要，而是校招笔试要覆盖更广的基础面，深度学习完全可以放到面试环节再深入考察。作为候选人，你不用面面俱到地去押题，但一定要把经典算法的原理吃透，做到能推导、能手写、能解释。

2. 核心算法题解析：从KMP到排序与搜索

2.1 KMP算法：next数组推导与手写注意事项

KMP几乎是校招笔试编程题里的“钉子户”，网易这张卷子也不例外。很多同学一看到KMP就头疼，觉得next数组很难背。其实问题出在学习方法上，如果你理解了next数组的本质，根本不需要背。

next数组的定义是：对于模式串P，next[i]表示P[0...i-1]这个子串中，最长的相等前缀和后缀的长度。注意，这里的前缀和后缀不能是子串本身。比如模式串 p="abacaba"，我带你手推一遍next数组。

当i=0时，next[0]约定为-1。i=1时，子串是"a"，没有相等的前后缀，所以next[1]=0。i=2时，子串是"ab"，前缀a不等于后缀b，next[2]=0。i=3时，子串是"aba"，前缀"a"等于后缀"a"，长度1，next[3]=1。i=4时，子串是"abac"，最长的相等前后缀长度是0，next[4]=0。i=5时，子串是"abaca"，前缀"a"等于后缀"a"，next[5]=1。i=6时，子串是"abacab"，前缀"ab"等于后缀"ab"，长度2，next[6]=2。i=7时，子串是整个模式串"abacaba"，最长的相等前后缀是"aba"，长度3，所以next[7]=3。

这个推导过程写出来很直观，但真正手写代码时很多人会卡在“如何用递推求next”。核心思路是：假设我们已经知道next[i]的值，现在要求next[i+1]，就让当前的最长相等前后缀长度k去尝试扩展，如果P[k]==P[i]，那么next[i+1]=k+1；如果不相等，就回退到next[k]，继续比较。这个回退过程是KMP最精妙也最容易被忽视的地方。

void getNext(const string& p, vector<int>& next) { int n = p.size(); next.resize(n); next[0] = -1; int k = -1, i = 0; while (i < n - 1) { if (k == -1 || p[i] == p[k]) { ++k; ++i; next[i] = k; } else { k = next[k]; } } }

建议你把这段代码亲手敲一遍，然后带着刚推出来的数组走一遍匹配流程。KMP的核心价值在于主串指针不回溯，这在处理大文本匹配时能保证O(m+n)的复杂度。笔试中KMP题一般不会只让你写匹配，更常见的是让你计算next数组或者求匹配位置，所以两个都要熟练。

2.2 排序算法：手写快排、堆排与复杂度分析

排序算法是数据结构部分考查频率最高的一类题，网易笔试几乎每年都会涉及。原因是排序算法能同时考察代码实现能力、复杂度分析和边界处理能力。我见过太多同学能说出快速排序和堆排序的原理，但一到笔试现场手写就各种bug，这是典型的“眼高手低”。

快速排序最重要的是partition函数的写法。我习惯用“挖坑法”来写，不容易出错。思路是：先取一个基准值（一般取第一个元素），形成一个“坑”；然后从右向左找比基准小的元素填坑，再从右向左找比基准大的元素填坑，最后把基准放回坑里。这个过程结束后，基准元素就位，接着递归处理左右两半。

int partition(vector<int>& arr, int left, int right) { int pivot = arr[left]; while (left < right) { while (left < right && arr[right] >= pivot) right--; arr[left] = arr[right]; while (left < right && arr[left] <= pivot) left++; arr[right] = arr[left]; } arr[left] = pivot; return left; } void quickSort(vector<int>& arr, int left, int right) { if (left >= right) return; int idx = partition(arr, left, right); quickSort(arr, left, idx - 1); quickSort(arr, idx + 1, right); }

快速排序的时间复杂度平均是O(n log n)，最坏情况是O(n^2)，当输入序列已经有序且每次都取第一个元素作为基准时就会触发。笔试时如果题目要求写出“最坏情况下的时间复杂度”，很多人的答案是错的，就是没想清楚退化条件。

堆排序的考点集中在建堆和堆调整两个操作上。建堆的过程是从最后一个非叶子节点开始，自底向上做“下沉”操作，时间复杂度是O(n)。堆排序的总复杂度是O(n log n)，并且是原地排序，不会额外占用太多内存。笔试中常见的手写题是“用堆排序求数组第k大的数”，这种题用最小堆最方便：维护一个大小为k的最小堆，遍历数组，如果当前元素比堆顶大，就替换并做堆调整。这样堆顶就是第k大的数，整体复杂度O(n log k)。

2.3 高级数据结构的应用：哈希、二叉搜索树与并查集

除了排序和字符串，网易笔试的编程题还喜欢考察哈希、二叉搜索树、并查集这些常见结构。它们很少以“请你实现一个哈希表”这种直白的形式出现，更多是藏在某个业务场景里。比如“设计一个数据结构支持插入、删除和随机返回一个元素，时间复杂度均为O(1)”，这道经典题就需要你结合哈希表和动态数组来做。

哈希表的本质是空间换时间。笔试中涉及哈希的题目，一般不需要你从头实现哈希函数，而是要求你分析哈希冲突对性能的影响，或者设计合理的哈希函数。我建议你记住一个结论：当装载因子超过0.75时，哈希表的性能会急剧下降，所以Java的HashMap扩容阈值就是0.75，这个数字背后是有数据支撑的。

二叉搜索树的核心考点是中序遍历有序性。很多题表面上跟BST无关，比如“给定一个数组，求每个元素右边第一个比它大的数”，实际上可以用单调栈解决，但BST相关思路也常出现。至于平衡二叉树（AVL或红黑树），笔试一般不会让你手写旋转，但会考察你对平衡条件的理解。红黑树的五大性质最好背下来，面试问到的概率很高。

并查集是我个人非常推荐重点掌握的结构，因为它代码量少、套路固定，但能解决的题非常多。支持路径压缩和按秩合并的并查集，单次操作的时间复杂度近似O(1)。国内大厂笔试里经常出现的“朋友圈数量”“岛屿数量”“连通分量”问题，都可以用并查集秒解。我建议你专门练习一下手写并查集，35行以内的代码量，性价比极高。

3. 机器学习理论考点详解

3.1 模型评估指标：准确率、召回率、F1与AUC的坑

模型评估是机器学习笔试中最高频的知识点之一，网易也不例外。这里有一个很多初学者都会踩的坑：在类别不平衡的场景下，准确率完全没有参考价值。比如99%的样本是负类，模型把所有样本都判为负类，准确率是99%，但这显然不是一个好模型。所以笔试里只要出现“类别不平衡”几个字，答案基本就往召回率、精确率、F1、AUC或者PR曲线方向靠。

精确率和召回率是一对此消彼长的指标。精确率Precision = TP/(TP+FP)，衡量的是“预测为正类的样本中有多少真的为正类”；召回率Recall = TP/(TP+FN)，衡量的是“真实正类样本中有多少被找出来了”。在垃圾邮件过滤场景中，我们更关注精确率，因为误杀正常邮件比漏放垃圾邮件更让人恼火；在癌症筛查场景中，我们更关注召回率，因为漏诊的代价远高于误诊。

F1是精确率和召回率的调和平均数，公式是F1 = 2 * P * R / (P + R)。注意是调和平均而不是算术平均，调和平均对低值更敏感。如果一道题给了你混淆矩阵的四个格子，让你分别算Precision、Recall、F1，这属于送分题，但前提是你把混淆矩阵的坐标弄清楚——横轴是预测值，纵轴是真实值，TP在左上角，FP在右上角，FN在左下角，TN在右下角，这个排列在很多资料里并不统一，审题时一定要看清。

AUC是一个更鲁棒的指标。AUC = P(正样本的预测值 > 负样本的预测值)，它衡量的是模型的排序能力，对类别不平衡不敏感。绘制ROC曲线时，横轴是FPR，纵轴是TPR。AUC永远在0到1之间，0.5相当于随机猜，0.7以上算可用，0.9以上说明模型有很强的区分能力。笔试中如果问“为什么AUC对不平衡数据不敏感”，不要只答“因为AUC不考虑阈值”，还要提到它是从排序角度计算概率，本质上是穷举了所有正负样本对。

3.2 经典模型推导：逻辑回归、朴素贝叶斯与SVM

网易笔试的简答题部分，特别爱出“请推导逻辑回归”或“比较SVM和逻辑回归的异同”。这类题考察的是你能否把公式推导的链条完整写出来，而不是背结论。逻辑回归的完整推导链条是：先通过线性回归得到 z = w^T x + b，再用sigmoid函数将z映射到(0,1)区间，得到 h(x) = 1 / (1 + e^{-z})，然后将h(x)解释为P(y=1|x)。极大似然估计的负对数损失，最终会得到一个损失函数，就是交叉熵损失。

关键点在于梯度计算。逻辑回归的损失函数对参数w求导，结果恰好是 (h(x) - y) * x，这个形式极其优雅，也正是为什么逻辑回归可以用简单的梯度下降来优化的原因。很多同学笔试时会写错符号或漏掉负号，建议你自己动手推一遍链式法则，推完之后就很难忘了。

朴素贝叶斯的考点是“朴素”二字的含义：它假设特征之间相互独立。正是因为这个强假设，联合概率分布才能分解成各个特征条件概率的乘积。在垃圾邮件分类这种特征维度高的场景中，这个假设虽然不完全成立，但往往能取得不错的效果。笔试容易考的点是：用贝叶斯公式计算后验概率时，分母P(X)对所有类别是常数，所以比较时可以直接省略。

SVM的推导是这个板块的难点。如果你完整推导过线性可分SVM的对偶问题，你就会理解为什么会有支持向量的概念，为什么核函数能解决非线性问题。笔试中通常不会让你一步步推拉格朗日乘子，但可能会问“为什么SVM对高维数据表现较好”“什么是KKT条件”“核函数的本质是什么”。核函数的本质是：定义一个高维空间中的内积，避免显式进行高维映射的计算。这个解释在笔试问答中最好用，既简洁又准确。

3.3 特征工程与过拟合控制

特征工程在笔试中经常以“给你一个业务场景，你会怎么设计特征”这种开放题出现。这类题没有唯一答案，但考察的是你的工程直觉。一个好用的回答框架是：先分统计特征、时间特征、文本特征、交叉特征这几个维度来构建答案。

统计特征是最基础的一类，包括均值、方差、最大值、最小值、分位数等。比如预测用户是否会付费，可以统计用户历史消费金额的平均值和最近30天的消费次数。时间特征强调的是“近期行为比历史行为更有价值”，所以可以设计“最近7天活跃天数”“距离上次登录的天数”这类特征。文本特征如果出现在业务题里，大多是让用TF-IDF或Word2Vec做向量化。交叉特征则考验你能否从业务逻辑中找到有意义的组合，比如“新用户+高活跃”组合可能表示刚进入平台的优质用户。

特征工程的回答要体现“先单个特征，再组合特征，最后做特征筛选”的完整思路。特征筛选的常用方法包括方差选择、卡方检验和基于模型的重要性排序，笔试答出两到三种就够了。

过拟合控制是另一个高频题。常见方法可以归纳为四条线：数据层面做数据增强和交叉验证；模型层面降低复杂度；参数层面加正则化项；训练层面加早停法和dropout（深度学习用）。问答题的核心是讲清楚“每个方法背后在解决什么问题”。比如L2正则化的本质是在假设参数服从高斯先验的前提下做最大后验估计，所以会让权重趋向于0；L1正则化对应拉普拉斯先验，会让权重倾向于变成0，从而实现稀疏性。能把这一点讲明白，分数就会明显高于只会列举方法名的同学。

4. 实操过程：一张模拟卷的完整作答实录

4.1 选择题阶段的取舍策略

笔试刚开始的15分钟，我建议你把全部选择题快速扫一遍。拿到卷子第一件事不是从第一题开始按顺序做，而是先花一分钟浏览整份试卷，判断难易分布，标记出自己有把握的题和需要犹豫的题。我当年就是先做完了所有有把握的题，再回头啃难题，这样即使时间不够，也能保证正确率。因为算法岗笔试不是要求你考满分，而是要求你的相对排名靠前，在有限时间内拿更多分才是最优策略。

多选题是最容易拉开分数差距的地方。多选题的规则一般是“少选得部分分，错选不得分”，所以不确定的选项宁愿不选。举个例子，如果一道题问“下列哪些算法可以用来处理非线性分类问题”，选项里有逻辑回归、SVM、决策树、朴素贝叶斯。逻辑回归本身是线性分类器，但加了核技巧之后也可以处理非线性。这种选项就属于“会做的人会纠结，不会做的人直接蒙错”的典型。如果你不确定，宁可少选。

选择题里偶尔会出现一两道纯记忆型的题，比如“在KMP算法中，对于模式串p=‘abacaba’，其next数组的值是多少”。这种题没有技巧，就是平时要刷足够的题量。建议在校招季开始前，把所有经典算法的next数组、复杂度、稳定排序结论都整理成一张速查表，考前30分钟过一遍。

4.2 编程题现场手撕思路

编程题的两道题，通常一道是数据结构和算法题，一道是偏业务场景的编码题。做题顺序我建议先做数据结构题，因为这类题的解法比较标准，容易快速AC；业务场景题虽然看起来贴近应用，但往往需要花时间理解题意和边界条件，容易陷入细节。

第一道编程题如果考排序变体，常见思路是先分析复杂度要求再选算法。比如题目说“n较大且要求O(n log n)”，那就应该直接写快速排序或堆排序，不要纠结其他方法。如果题目说“数据范围小但要求稳定”，那就用归并排序。手写代码时一定要先写主函数的框架，再补辅助函数，最后再检查边界条件。我见过不少同学先写辅助函数，写到一半思路断了，反而浪费了时间。

第二道业务场景题，最关键的技巧是从题目描述里提取“输入输出样例”。如果题目给出了输入输出样例，你先把样例走一遍，搞清楚数据是怎么流转的，比阅读大段文字描述快得多。然后想想这个题能不能转化成经典问题：如果把“用户行为序列”看成“数组”，“连续活跃天数”看成“最长连续子序列”，那解法就呼之欲出了。很多业务包装题的核心都是经典模型，只是换了层皮。

写代码时我习惯先处理几个必考的边界条件：空数组、单元素数组、数组元素全相等、目标值在首尾位置。这些情况往往是样例里不会给但后台测试数据一定会覆盖的。如果写完代码后有时间，再用自己构造的几个极端case跑一遍，基本就能避免因为边界问题导致的崩溃或超时。

4.3 简答题的答题结构与踩分点

简答题是很多人的弱项，因为它既考知识又考表达。我自己的经验是：答简答题一定要分层，哪怕你只记得两个要点，也要写成(1)(2)(3)的结构。因为笔试通常是人工阅卷，重点看你的“踩分点”是否覆盖了参考答案里的关键条目。条目清晰、有逻辑顺序的答案，比一大段堆砌文字的答案得分高很多。

举个例子，如果题目是“请简述Bagging和Boosting的异同”，你的答案结构应该分成两层：相同点和不同点。相同点写“都是集成学习方法，通过组合多个弱学习器提升模型性能”；不同点分三条写：样本采样方式不同（Bagging有放回采样，Boosting每一轮调整样本权重）、弱学习器训练方式不同（Bagging并行，Boosting串行）、目标不同（Bagging降低方差，Boosting降低偏差）。每一条后面再加一句简短解释，这样结构就完整了。

还有一道很常见的题是“如何处理特征缺失值”，踩分点包括：删除缺失率过高的特征或样本、用均值/中位数/众数填充、用模型预测填充、用哑变量标记缺失情况。把四个方法列出来并说明适用场景，基本就能拿满分。注意答题时不要只列方法名称，每个方法补一句“在什么情况下使用”，这道题就从“及格”变成了“优秀”。

5. 常见失分点与备战建议

5.1 笔试失利典型问题清单

我总结了几届同学做网易笔试题的常见失分点，整理成表格，方便你对照自查。这张表格里的每一项，都是真实考场里反复出现的问题，避开它们，你至少能多拿10分。

这里面最容易被忽视的是第7条。业务包装题看起来题目很长、信息量很大，但本质往往很基础。我建议你平时刷题时养成一个习惯：每做完一道题，强迫自己在题目的“技术标签”位置写一句“这是一道XX算法的题”，比如“这是一道前缀和的题”“这是一道滑动窗口的题”。长期训练下来，考场上你一眼就能看穿题目包装。

5.2 三周备战路线参考

如果你现在是零基础或者半基础状态，时间还剩三周，我推荐按下面这个路线来准备。不用追求面面俱到，但要保证核心考点全部覆盖。

第一周主攻数据结构和算法编程。每天至少手写两道经典算法题，重点覆盖排序、二分、双指针、滑动窗口、KMP、动态规划。编程语言建议用C++或Python，不要换来换去。这一周的目标不是做难题，而是把基础算法练到闭着眼睛能写出来。可以按我前面给的代码模板去练，先理解再默写，最后做到能根据题目要求灵活调整。

第二周主攻机器学习理论和推导。每天一个主题：周一逻辑回归、周二SVM、周三决策树和随机森林、周四朴素贝叶斯和EM、周五集成学习、周六特征工程和模型评估、周日把前六天内容过一遍，并尝试不看笔记推导一遍关键公式。周志华的《机器学习》是这个阶段的好帮手，重点看前六章和第十六章。推导时可以在纸上写，也可以在电脑上敲Markdown公式，关键是动手写出来。

第三周做模拟考和查漏补缺。找两三套相似的笔试真题，严格按考试时间120分钟来模拟。模拟考后不要只对答案，要把每道错题的知识点提取出来，整理成一份“错题知识点清单”。比如错了一道动态规划的题，就在清单上写“动态规划状态定义方法不够熟练”，然后当天补做三道同类题。第三周的晚上可以刷选择题和简答题，训练快速反应能力，同时把前面整理好的知识速查表反复过几遍。

最后再分享一个小技巧：笔试前一定要调整好作息，保持上午头脑清醒的状态。校招笔试很多安排在上午，如果你习惯熬夜刷题，考试时大脑容易短路。我在实际备考刷题中发现，坚持早睡早起复习效率反而比熬夜高，考场上思维也更清晰。另外，代码编辑器可能会和你平时练习的环境不一样，考前至少用在线OJ熟悉一下输入输出的标准写法，这个细节能帮你节省不少时间。