网易2018校园招聘算法工程师(有道)笔试卷——这份卷子我已经不知道给多少学弟学妹讲过了。倒不是它有多难而是它的出题风格特别典型选择题里埋坑编程题考基本功问答/设计题考你“是不是真的做过算法”而不是只背了几个模型。我当时拿到卷子的第一反应是咦居然没有想象中那么偏门但越做越发现每一道题都在精准地试探你的知识边界。如果你是准备校招的算法岗同学这篇复盘值得认真看完。我不会只贴题目和答案而是把每类题背后的出题意图、常见错误、推导过程都讲明白。你把这套卷子的思路吃透再去面任何一家互联网公司的算法岗笔试至少不会再出现“明明刷了不少题还是被一套校招卷按在地上摩擦”的情况。1. 网易有道2018校招笔试到底在筛什么样的人1.1 卷面结构与考点分布复盘先把这份卷子的整体轮廓还原一下。三个部分选择题/填空题、编程题、问答/设计题整体时间一般在90到120分钟。选择题和填空题覆盖的范围很广从我记忆中的版本来看大致集中在这样几个方向考察方向高频考点占比估计数据结构与算法栈、队列、树、堆、排序、查找、KMP、拓扑排序40%左右机器学习/深度学习基础过拟合、正则化、损失函数、SVM、BN、常见模型30%左右概率统计条件概率、贝叶斯、期望、采样、数据分布20%左右开放/综合海量数据、TopK、优化算法、知识面扩展10%左右编程题通常两到三道考察比较集中一道排序/数组变种题一道字符串题再加一道图论或者搜索/动态规划题。这几乎成了互联网大厂算法笔试的固定配方。问答/设计题则比较“有道”——有道做搜索、教育产品、NLP所以题目里经常出现和文本处理、海量数据、推荐排序相关的场景题。这部分不是考你背了多少理论而是看你能不能把一个模糊的业务问题转化成清楚的算法流程。1.2 这份卷子想筛掉什么样的人先说个扎心的事实校招笔试不是用来选“最强”的人而是用来筛掉“不合格”的人。网易这种体量的公司简历投递量极大笔试系统不可能是为了选拔天才设计的它的核心目标只有一个——用最短的时间确认你有扎实的计算机基础、有基本的算法建模能力、有把思路写成代码的能力。所以你会发现这份卷子里的编程题难度基本在LeetCode中等题偏下的水平至少一半题目你只要刷过常见题型思路肯定是有的。真正拉开差距的是那些“看起来会但是一写就错”的题。比如排序的边界条件、KMP的next数组下标定义、递归改非递归、溢出处理等等。我后来和当时一起笔试的同学复盘发现一个规律被筛掉的人往往不是不会做难题而是挂在了简单题的细节上。三色旗排序写成了冒泡、KMP的next数组背错了定义、贝叶斯公式代入时把条件搞反了——这些错法在阅卷系统里无处遁形。1.3 和LeetCode刷题的区别在哪很多同学备考就是刷LeetCode这没错但校招笔试和平台刷题有个本质区别LeetCode是“核心代码模式”你只需要补完那个函数笔试通常直接套一个完整程序模板你要自己处理输入输出、考虑多组数据、处理文件结束甚至有的系统里根本没有编译器自动补全你错了就得按行扣分。LeetCode的通过率往往是一遍交上去错了几乎无所谓你可以反复提交试错。校招笔试不同提交次数通常有限而且系统会记录每一次提交甚至有的公司会看你的“解题时间曲线”——这听起来夸张但我确实在内部交流时听HR说过笔试成绩单上一眼就能看出谁是在本地调试通了再交谁是在线疯狂试错。所以平时准备的时候就应该用“笔试模式”约束自己一次性把代码写对想清楚边界再动手不要依赖在线反馈。养成这个习惯比多刷一百道题都值。2. 现场还原三道编程题从读题到AC的完整思路2.1 三色旗排序排序题的经典变种当年编程题第一道说句实话考得相当客气。题目大意是给定一个只包含0、1、2的整数数组请将其排序要求时间复杂度O(n)空间复杂度O(1)尽量少遍历。看到这题第一反应是“排序”但仔细一看数组里只有三种值。计数排序当然能做——扫一遍统计0、1、2出现的次数再回填数组。但这样需要遍历两次而且严格来说额外空间也顺便申请了虽然只有三个计数器但有些面试官就是会追着这个地方问“你能不能做到一次遍历”。一次遍历的经典解法是三指针也叫荷兰旗问题void sortColors(vectorint nums) { int n nums.size(); int zero 0, two n - 1; int i 0; while (i two) { if (nums[i] 0) { swap(nums[i], nums[zero]); zero; i; } else if (nums[i] 2) { swap(nums[i], nums[two]); two--; // 注意这里 i 不能自增因为换过来的是 2 还是 0 还不确定 } else { i; } } }这个解法里最容易写错的就是nums[i] 2的分支交换之后从后面换过来的数可能是0也可能是1如果是0下一次循环还要把它交换到前面去所以 i 不能动。我第一次手写这道题就折在这里直接把 i 递增了结果遇到 0 混在 2 的位置上时答案直接不对。另一个边界坑是空数组和全0/全2的情况。while (i two)这个条件天然处理了全2的情况——i 初始为0zero 初始为0如果数组里全是2每次都把2换到尾部two 递减直到 two 变成 -1循环退出。这个写法容错性确实高。这道题背后其实藏着出题人的潜台词算法工程师天天和数据处理打交道一个排序都写不利索的人谁敢让你去排序几十亿个样本所以这类“简单变种题”从来不是送分题而是那种“会的人一眼秒不会的人写半天还错”的考法。2.2 KMP与next数组“背过”和“真懂”的区别第二道编程题是个字符串题很多人回忆里的版本是给定模式串 p abacaba求它的 next 数组要求写出计算过程和最终数组。有的版本会给出 next[i] 的精确定义有的版本不给这本身就是个坑。我先把按“next[i] 表示 p[0..i] 这个子串的最长相等前后缀长度”这个定义算一遍i子串最长相等前后缀长度0a01ab02aba1前缀 a后缀 a3abac04abaca1前缀 a后缀 a5abacab2前缀 ab后缀 ab6abacaba3前缀 aba后缀 aba所以 next 数组 [0, 0, 1, 0, 1, 2, 3]。但这里非常容易出现争议不同教材对 next 数组的下标定义不一样。有的定义 next[i] 为“前 i 个字符组成的子串的最长相等前后缀长度”此时 next[0] 通常是 -1有的定义 next[i] 为“p[0..i] 的最长相等前后缀长度”此时 next[0] 0还有的定义 next[i] 为“失配时模式串要跳到的下标”。所以如果你在笔试卷上看到 KMP 的题第一步不是急着算而是先看题目对 next 的定义。如果题目没说建议在答案里写清楚“本文采用如下定义”然后再计算。这一句话就能避免整道题因为约定不一致被判错。真正要掌握的其实是 next 数组的递推代码vectorint getNext(const string p) { int m p.size(); vectorint next(m, 0); int k 0; // 当前最长相等前后缀长度 for (int i 1; i m; i) { while (k 0 p[i] ! p[k]) { k next[k - 1]; // 向左回溯到更短的前缀 } if (p[i] p[k]) { k; } next[i] k; } return next; }很多人背了这段代码却从没想过为什么失配时要回溯到next[k - 1]。这里其实是 KMP 的精髓当当前位置的字符和已匹配前缀的下一个字符不相等时我并不能直接从头开始匹配因为前面 k 个字符可能仍然构成一个更短的前缀-后缀匹配。用动态规划的话说next 数组本质是一个自动机的跳转表。笔试如果考到 KMP十有八九不是考你匹配过程而是考这个跳转过程的理解。能够手写getNext并且讲清楚“为什么要回退到 next[k-1] 而不是 k-1”的人在阅卷官眼里才是真正理解 KMP 的人。2.3 一道更发散的题拓扑排序与任务依赖编程题第三道通常会和图沾点边。我见过的一个版本是“课程学习顺序”问题和 LeetCode 207 课程表基本一致。给出一系列课程之间的先修关系输出一个可行的学习顺序如果有环就输出无法完成。这类题直接上 Kahn 算法vectorint topoSort(int n, vectorvectorint adj) { vectorint inDegree(n, 0); for (int u 0; u n; u) { for (int v : adj[u]) { inDegree[v]; } } queueint q; for (int i 0; i n; i) { if (inDegree[i] 0) q.push(i); } vectorint res; while (!q.empty()) { int u q.front(); q.pop(); res.push_back(u); for (int v : adj[u]) { if (--inDegree[v] 0) { q.push(v); } } } if ((int)res.size() ! n) { // 有环无法完成全部课程 return {}; } return res; }Kahn 算法并不复杂核心就三句话统计入度、入度为零的节点入队、每次弹出一个节点并更新它的邻居入度。但笔试里真正拉开差距的变种是如果题目要求输出字典序最小的合法学习顺序你就要把 queue 换成 priority_queue每次取入度为0且编号最小的节点。这种变化很常见因为算法工程师在日常工作中经常遇到“多个任务同时可做时优先做哪个”的调度问题。我在强调一次这类题不是背代码而是理解“为什么拓扑序列可能不唯一”。只要理解了这一点优先队列版本的解法就是顺水推舟的事情。3. 机器学习基础题过拟合、正则化与BN别只会背概念3.1 过拟合和偏差-方差选择题里的“送命题”每个公司算法岗笔试卷里几乎都会出现过拟合相关的题目网易这份也不例外。常见出法有两种。一种是直接问“以下哪些是缓解过拟合的方法”选项里混入“增加训练数据量”“Dropout”“L2正则”“增加模型参数”“降低模型复杂度”。另一种是问偏差和方差的关系“高偏差意味着模型过于简单还是复杂”。过拟合的本质就是模型在训练集上学到了太多训练集特有的噪声导致泛化能力下降。而缓解过拟合的全部手段本质上都是在“限制模型复杂度”或者“增加有效数据量”。我自己在给校招同学模拟面试时发现很多人能说出 Dropout、正则化却说不清“为什么 L2 正则化可以抑制过拟合”。L2 把每个参数的整体平方和放进损失函数里梯度下降时参数会被额外减去一个正比于参数本身的量也就是“权重衰减”。权重被压小了模型的决策边界就更平滑对噪声音量的敏感度就下降了。这道选择题如果问你“L2 正则化为什么有效”一定不要只回答“防止过拟合”要答到“权重衰减使得模型对输入噪声的敏感度降低”这个层次。选择题的选项设计往往会把这种表述作为区分项。3.2 L1 和 L2 正则化为什么 L1 更容易产生稀疏解这是机器学习基础题里的常青树。L1 是参数的绝对值之和L2 是参数的平方和。两者的差异不仅体现在数学公式上更体现在优化解的几何形状上。在高维空间中L1 约束对应的可行域是一个“菱形体”角点正好落在坐标轴上所以最优解很容易落在某个参数为零的角点附近从而产生稀疏解。L2 约束对应的是一个球体切点几乎不可能恰好落在某个坐标轴上所以参数会往接近零但非零的方向收缩。有的选择题会从“特征选择”角度出L1 正则化适合做特征选择因为稀疏解会让不重要的特征权重直接变成0L2 则是让权重整体变小特征依然都保留。背下这句话很容易但我建议大家自己画一张二维等高线图把损失函数等高线和 L1/L2 的约束区域画在一起看看切点落在哪里。凡是能画出这张图的人这道题永远都不会错。3.3 BatchNorm 为什么能加速训练BatchNorm 是2015年Batch Normalization那篇论文提出来的这几年已经成为深度学习笔试的必考知识点之一。它会对一个 batch 内每个特征维度做归一化然后再通过可学习的缩放和平移参数恢复表达能力。选择题和简答题的常见问法BN 解决的是什么问题内部协变量偏移或者说前面层的参数变化导致后面层输入分布不稳定为什么 BN 能增大学习率因为每层输入分布稳定了梯度不会因为输入太大或太小爆炸所以可以用更大步长训练和预测时的 BN 有什么区别训练时用当前 batch 的均值和方差归一化预测时用训练阶段滑动平均得到的全局均值和方差。我把“为什么输入分布稳定能加速训练”再展开一下神经网络反向传播时梯度大小不仅和损失函数有关还和每一层输入数据的范围有关。如果某些层的输入动不动就变成几十几百那些层的梯度会非常大训练就震荡就得把学习率调得很小。BN 把每层输入拉回均值为0、方差为1的分布梯度大小相对可控训练自然就快了。笔试里如果给你一个选择题里有“BN 必须配合 Dropout 使用”“BN 训练和预测都在用 batch 统计量”“BN 只在卷积层可用”这种错误说法你要能一眼识别出来。BN 训练和预测统计量不同是一个高频易错点至少有三位同学在我面前栽在这道题上。3.4 损失函数对比为什么交叉熵比MSE更适合分类这个知识点网易卷里出现的频率很高通常以选择题或者简答题的形式出现。分类任务里很多深度学习框架默认用交叉熵损失而不直接对 last layer 的输出用均方误差MSE这背后是两个原因。第一个原因是梯度形态。分类任务最后一层通常是 softmax输出经过 softmax 后已经变成了概率分布。如果在这个概率输出上用 MSE梯度和输出概率之间会存在一个“概率×(1-概率)”的乘积项当预测概率接近0或1时梯度会很小也就是梯度饱和。而 softmax 交叉熵的组合梯度推导到最后极其简洁等于预测概率减去 one-hot 真值不会有饱和问题训练效率高很多。第二个原因是概率语义。交叉熵衡量的是两个分布的差异训练目标就是让模型输出分布逼近真实类别的 one-hot 分布这与分类任务的语义一致。MSE 则是回归任务的度量方式硬套到分类上相当于把一个分布匹配问题当成数值拟合问题来解逻辑上就拧了。复习的时候除了会背结论建议亲手推导一次交叉熵对 softmax 输入的梯度。推导一遍之后遇到“下列关于 softmax 交叉熵梯度描述正确的是”这种选择题你根本不需要背答案直接现推都能做对。4. 概率统计与海量数据题最容易被低估的拉分区块4.1 贝叶斯公式一道被无数人答错的检测题网易这份卷子里有一道非常经典的概率题版本很多核心结构是这样的某种疾病的患病率是0.1%现有检测方法的准确率是99%也就是真阳性率99%假阳性率1%。某个人检测结果为阳性问这个人真正患病的概率是多少。很多人的第一直觉是99%这个答案错得离谱。正确算法是P(患病 | 阳性) P(阳性 | 患病) × P(患病) / P(阳性)其中P(阳性 | 患病) 0.99P(患病) 0.001P(阳性) 0.99 × 0.001 0.01 × 0.999 0.00099 0.00999 0.01098所以P(患病 | 阳性) 0.00099 / 0.01098 ≈ 0.0902也就是大约9%。这个结果反直觉的地方在于即使检测准确率高达99%在患病率极低的情况下一次阳性结果依然大概率是误报。原因很简单假阳性率1%听起来很低但乘以庞大的未患病基数之后产生的假阳性人数远超过真阳性人数。校招笔试里概率题几乎必出这种“先验概率噪声观测”的结构因为算法工程师日常工作中到处都要和这种逻辑打交道。比如推荐系统里预测点击率点击率通常只有几个百分点你怎么判断一个用户点击了是不是“真的喜欢”怎么处理冷启动不确定性贝叶斯思维就是基础中的基础。这道题答错的人不是不会套公式而是缺少这种概率直觉。我建议你用一个小脚本模拟一下“一万个人里有多少人误报、多少人真阳性”立刻就能建立起这种直觉。4.2 蓄水池抽样流式数据等概率采样的标准答案海量数据题里抽样问题非常经典。网易卷子里有一种问法有一个长度未知的流式数据序列内存不足以放下全部数据请你设计一个算法保证任意时刻你都能从已见过的数据中等概率地抽样一个出来。标准的答案是蓄水池抽样Reservoir Samplingvectorint reservoirSample(vectorint stream, int k) { vectorint reservoir(stream.begin(), stream.begin() k); for (int i k; i (int)stream.size(); i) { int j rand() % (i 1); if (j k) { reservoir[j] stream[i]; } } return reservoir; }单样本的情况就是 k1第 i 个元素以 1/i 的概率被选中覆盖当前结果。为什么这样能满足等概率可以用归纳法证明。假设处理完前 i-1 个元素时每个元素被保留的概率是 1/(i-1)。那么处理第 i 个元素后前 i-1 个元素被保留的概率分为两部分第 i 个元素没被选中概率是 (i-1)/i以及第 i 个元素被选中但它覆盖的是其他元素这部分不影响“这个元素是否被保留”因为只要第 i 个元素没被选中它就在。所以前 i-1 个元素的保留概率等于 (i-1)/i × 1/(i-1) 1/i。第 i 个元素被保留的概率本来就是 1/i。于是到第 i 个元素时所有元素等概率。笔试考到蓄水池抽样往往不是让你背代码而是让你现场推导正确性。如果你能把上面这段归纳法推导完整写出来这道题基本就是满分。4.3 海量数据 TopK100亿个整数怎么找最大的100个另一类高频海量数据题是关于 TopK 的。常见问法100亿个32位整数分布在多个文件中内存只有1GB找出其中最大的100个。首先算一笔账100亿个 int约 4×10^10 字节也就是40GB单机单进程直接读入内存是不现实的。正确的做法是把100亿个整数哈希分桶到100个文件中每个文件大约400MB对每个文件维护一个大小为100的最小堆依次读入文件里的数据一旦当前数比堆顶大就弹出堆顶、插入当前数所有文件扫完后每个文件得到100个候选数把这100个文件各自的 Top100 全部混进来再做一次 Top100得到最终结果。时间复杂度是 O(n log k)这里 n100亿k100log k 很小所以瓶颈其实在磁盘IO在40GB数据的顺序读取上。如果你的回答里提到“用外部排序也可以”也没错但一定要指出外部排序需要多次读写磁盘哈希分桶堆这种方案只读取一遍原始数据在IO上更优。这道题还有一个变种如果数据中有大量重复值可以先去重再排序或者用 bitmap 标记。百亿量级的整数去重bitmap 需要 2^32 bit 512MB恰好卡在内存边缘所以也是可行的。面试官喜欢听你权衡这些方案的取舍这就是加分项。4.4 快速幂一道算得又多又快的送分题快速幂算是选择题和编程题之间的一道“夹心层”。有时候是选择题问“计算 3^100 mod 7”有时候是编程题要求实现 pow(a, b, mod)。背过模板的肯定是秒杀long long fastPow(long long a, long long b, long long mod) { long long res 1; a % mod; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }快速幂的核心思想是把指数 b 看成二进制数。比如 b 13二进制是1101那么 a^13 a^8 × a^4 × a^1。代码里每轮把底数平方对应二进制的每一位如果当前位是1就把结果乘上当前底数的幂次。这样从 O(b) 的朴素乘法优化到了 O(log b)。很多人会写这个模板但笔试如果考到往往会在取模上做文章。int 相乘再取模可能溢出要用 long long 或者更大的类型。这个细节如果你不写出来被卡了样例都不知道自己错在哪。另外扩展一下这个模板和二分幂、矩阵快速幂是同一套血统。矩阵快速幂在递推数列和动态规划优化里用得很多。你如果能把快速幂理解透彻顺便把矩阵快速幂也过一遍笔试涉及到斐波那契数列求解的时候就能多出一种“高维做法”的谈资。5. 复盘与备考踩过的坑、时间分配和优先级清单5.1 我当年在笔试里踩过的坑说实话我刚刷笔试题那会儿最喜欢干的事情就是“差不多做出来就直接交”——样例测一下没问题就跑。这种习惯在校招笔试里极其致命。第一个坑是不处理多组输入。很多笔试系统不给样例组数而是让程序一直读直到 EOF。我用while (cin n)习惯了以后觉得这是常识但第一次参加机考时过于紧张直接写成了只读一次结果后面所有测试点全是错的而本地样例又通过。从那以后我的习惯是凡是读入循环一律写成 while 形式防止遗漏。第二个坑是数组越界和整型溢出。链表、数组题里最容易出现i1越界递归深度超过栈上限导致爆栈中间结果乘到 int 上限之外。这些坑不是你不会算法是你的代码忽略了运行环境。笔试的测试用例往往会刻意卡边界你要做的不是抱怨而是把“检查边界”变成肌肉记忆。第三个坑是选择题里那些“看似正确”的干扰项。网易卷子里出现过类似“SVM 一定是线性分类器”“KNN 训练阶段需要保存全部样本”“LSTM 可以完美解决梯度消失”这种一刀切的表述正确答案都是“错误”。机器学习里几乎没有绝对化的说法选项里出现“一定”“全部”“完美”之类的词往往就是反例被设计出来的地方。5.2 时间分配策略每一种题型应该花多久笔试时间短、题量大不会时间管理的人经常在选择题上磨了太久编程题反而没时间写。我给自己定的标准是这样的分享出来给你参考题型建议时间策略选择题/填空题每题60到90秒超过90秒就跳过后面有时间再回看编程题第一道20到25分钟简单题必须全对不能丢分编程题第二道25到35分钟中等题先想清楚边界再写编程题第三道剩余时间能写暴力就给暴力能过部分用例也是分问答/设计题10到15分钟思路优先不需要写完整代码这里面最重要的原则是先把能稳拿的分全部拿到再谈冲击难题。编程题即使只写对一部分测试用例往往也有部分分交白卷才是零分。我见过很多同学一看第三题不会做就直接放弃连暴力的20%分都不要这样就等于自动放弃了通过机会。另外一定留出最后的3到5分钟复查。复查的主要是读入格式、输出格式、是否有return缺失、数组是否越界。有一次我笔试完发现第一道题的输出少了一个空格那种懊恼感你绝对不想体会。5.3 针对有道/NLP方向的算法岗备考优先级清单网易有道的主要业务方向是搜索、教育硬件、AI开放平台NLP 相关的岗位比例很高。所以备考的时候除了常规的通用算法建议你按下面的优先级准备数据结构与算法数组、链表、栈、队列、哈希表、二叉树、堆、图尤其是排序全家族、二分查找、双指针、滑动窗口、KMP、Trie、拓扑排序这些是笔试硬通货。字符串处理字符串哈希、KMP、AC自动机了解即可、正则表达式相关有道太喜欢考字符串了。机器学习基础过拟合、正则化、偏差方差、损失函数、优化器SGD、Adam、交叉验证这些是选择题的主要来源。深度学习基础CNN、RNN/LSTM、Attention、Transformer 的结构和优缺点、常见的训练技巧BN、Dropout、学习率调度。概率与统计贝叶斯、期望、方差、常见分布、最大似然估计、抽样方法这是算法岗区别于后端岗的标志。海量数据与工程能力TopK、哈希分桶、外部排序、蓄水池抽样、布隆过滤器这些在问答/设计题里出现频率极高。如果只给你30天时间我建议这样分配前10天夯实数据结构和 LeetCode 前300题里的高频中等题中间10天刷机器学习基础题每看到一个概念就要求自己“讲给一个不懂的人听”最后10天集中做历年真题和模拟题重点练速度、边界处理和时间分配。值得一提的还有“知识面扩展题”。有道卷子里有时候会冒出一两个冷门方向的概念比如信号处理里的重采样、图像里的拉普拉斯算子、控制理论里的 PID 算法、优化算法里的粒子群或者模拟退火。这类题要么是选择题选定义要么是简单判断考察的是你是否具备跨方向的学习敏感度。这玩意儿没法临时抱佛脚靠的是平时读文章、逛技术社区的积累。5.4 关于这道卷子的最后一个建议我见过太多同学把校招笔试当成一场“突击战”刷了两周题就去考考完觉得自己运气不好。但我复盘下来网易这份卷子也好其他大厂卷子也好它们的命题逻辑其实非常稳定选择题考知识广度编程题考代码基本功设计题考工程思维。这三块没有哪一块是可以靠“押题”混过去的。我自己当年的处理方式是把做错的每一道题都整理到一个文档里标注三件事——错误原因、正确思路、和哪个已掌握的知识点关联。笔试前翻一遍这个文档比重新刷十道新题都管用。因为人的错误往往是重复的你第一次栽在的地方很容易第二次继续栽。准备这个文档的过程其实就是把“我听懂了”变成“我会写了”的过程。校招笔试的淘汰率确实高但它考的绝不是运气而是一个人在基础能力上的真实厚度。把每一个原理真正吃透把每一行代码边界都写干净这套卷子自然会给你一个对得起努力的结果。最后说一个我自己的体会笔试只是算法的第一道门真正决定你适不适合做算法工程师的是你能不能把一个模糊的业务问题拆解成一小步一小步可执行的算法逻辑。网易这套卷子从选择题里夹带先验概率到编程题里考察边界处理再到处处强调“为什么”的追问其实都在帮你提前预习这一点。好好准备别辜负这些题目背后的一番用心。