网易有道算法笔试题复盘：KMP、排序与动态规划全解析

1. 试卷定位一场筛选“算法基本功”的技术面试关卡2018年我正好在准备秋招当时刷到网易有道这套算法工程师笔试卷第一反应是这份卷子比很多大厂的A卷都要“厚道”。它没有堆砌偏题怪题而是把考察重心放在了算法工程师日常工作中真正用得上的基本功上——数据结构与算法、机器学习/深度学习基础、以及工程实现能力。先说结论如果你是准备校招算法岗的读者这份试卷可以作为一份很好的“能力体检单”。它考的不是你背了多少篇顶会论文而是你能不能把“数据结构 经典算法 基础模型”这三大件用扎实。从当时校招整体情况来看网易有道的算法岗位笔试向来偏向实战覆盖范围也比较稳定选择题部分重点考察排序算法的复杂度、KMP这种字符串匹配经典算法、图论里的基本遍历策略编程题则基本围绕二分、动态规划、DFS/BFS展开。这套试卷适合谁来参考两类人一类是正在备战校招/实习的计算机相关专业学生想评估自己的算法底子是否达到一线互联网公司门槛另一类是刚入门的算法工程师想看看自己有没有“学过但不会用”的知识盲区。我当年的感受是这张卷子做完你对“校招算法考什么、我哪些地方薄弱”基本就有了一个清晰的画像。作为过来人我把这套试卷的核心考点、解题思路、以及我当时踩过的坑整理成了一份复盘笔记结构是这样的先看试卷整体设计与考点分布再逐一拆解高频考点接着拿一道典型的编程题做完整推演最后是备考路线上我可复用的经验。以下都是个人复习过程中的总结和理解具体题目细节可能与原卷略有出入但考察思路和解题框架是一致的照着这个框架去准备基本不会跑偏。2. 试卷结构拆解网易有道算法笔试在考察哪几类能力2.1 题型分布与考察意图从题型来看这套笔试卷大致可以分成三个模块基础选择题、算法填空题/简答题、编程题。选择题覆盖的知识面很广从时间复杂度分析到排序算法稳定性再到哈希冲突的解决方式基本都是在考察你“对数据结构有没有系统性的理解”。我当时做的时候最大的感受是这些题单独拎出来都不难但放在一起就能拉开“背过八股文”和“真正理解原理”的差距。有道这边的算法笔试题有个特点它喜欢把多个知识点揉在一道题里考。举个例子一道关于HashMap的选择题表面上考的是“HashMap的底层结构”但选项里涉及的可能是“链表转红黑树的阈值”“hash函数的扰动计算”“负载因子对扩容的影响”的综合判断。如果你只知其然不知其所以然很容易在一两个容易混淆的选项上翻车。编程题部分偏向LeetCode中档难度不会考变态难的ACM题但也不会让你轻松AC。题目特征比较明显给你一个看似复杂的情景包装剥掉外壳后核心还是那几种经典解法——二分边界处理、DP状态设计与转移、DFS剪枝等。这套题的核心逻辑是题目本身不难难的是你在有限时间内能不能快速建模、写出干净且不超时的代码。2.2 基础选择题中的高频考点盘点结合当年网上流传的题目回忆和我的记忆有几个考点几乎每年必考我按重要程度排了个序方便你对照自检排序算法全家桶快速排序、堆排序、归并排序的时间复杂度最好、最坏、平均空间复杂度稳定性。尤其要注意快排在“近乎有序”的数组上会退化成O(n²)以及堆排序为什么是不稳定的。KMP算法的next数组求解这属于“看似简单、实则需要动手算”的题型。很多人背了模板但不会手动计算一旦考到具体字符串的next数组就容易出错。二叉树遍历与递归前序/中序/后序的转换已知两种遍历序列求第三种。这类题在纸上画一画就能做出来但考试紧张时容易忽略“递归终止条件”的边界。图论基础DFS和BFS的时间复杂度、拓扑排序的实现方式、Dijkstra算法为什么不能处理负权边。哈希表与冲突处理链地址法、开放定址法的优缺点对比负载因子对查找性能的影响。这个考点分布其实反映了算法工程师岗位的一个现实需求你不需要在笔试中展示多么前沿的模型知识但必须保证基础数据结构手到擒来。原因也很直接——面试官需要确认你具备阅读和编写高质量工程代码的基本能力而不是只会调包。2.3 机器学习与深度学习基础题不只是背概念除了传统算法这套试卷里还出现了不少机器学习相关的基础题。比如“什么是过拟合、如何防止过拟合”“SVM的核函数作用”“梯度消失的原因和常见解决方案”。这倒不是考察你会不会手推SVM而是想确认你有没有建立“从数据到模型到优化”的完整认知框架。我当时在准备这类题目时发现一个比较高效的方法不孤立地背概念而是围绕“训练流程”把知识点串成线。你只要能把“数据预处理→特征工程→模型选择→损失函数→优化器→评估指标”这条链路上的每个环节讲清楚再顺着链路去理解过拟合、正则化、交叉验证等概念答题会顺手很多。深度学习方面高频考点集中在反向传播的基本原理、激活函数的选择、Batch Normalization的作用、CNN中感受野的计算。特别提示一个易错点感受野的计算公式要按层逐级推导不能只记最后一层的结果。我有一次就是在这里算错了小数值导致整个选项选错事后复盘觉得非常可惜。3. 核心考点精讲从思路到计算逐层拆解3.1 KMP算法与next数组高频但容易翻车热词里出现了好几次KMP可见很多人在准备校招时对这块都有点“心虚”。确实KMP是算法笔试中一个非常经典的分水岭题目能手推next数组的人说明对字符串匹配有系统理解只会背模板的人一旦题目稍微变形就露馅。所谓next数组简单来说就是记录模式串中每个位置之前的子串的“最长相等前后缀长度”这样当匹配失败时不需要把模式串的指针回退到开头而是根据next数组跳到下一个可能匹配的位置从而把匹配过程的复杂度从O(n*m)降到O(nm)。以热词中提到的pabacaba为例我带着你把next数组手动算一遍方便你找到手感。先约定next[i]表示模式串前i个字符组成的子串即前缀的最长相等前后缀长度注意不同资料对下标起始和next[0]的定义有差异这里采用固定写法next[i]表示长度i的前缀的子串对应的最长相等前后缀长度。手动计算过程如下i1子串为a没有真前后缀最长相等前后缀长度为0即next[1]0。i2子串为ab前缀a、后缀b不相等next[2]0。i3子串为aba前缀a后缀a长度1前缀ab≠后缀ba所以next[3]1。i4子串为abac前缀a≠后缀c长度1不行再看长度2前缀ab≠后缀ac也不行next[4]0。i5子串为abaca前缀a后缀a长度1前缀ab≠后缀ca前缀aba≠后缀aca所以next[5]1。i6子串为abacab前缀a≠后缀b前缀ab后缀ab长度2前缀aba≠后缀cab所以next[6]2。i7子串为abacaba前缀a后缀a长度1前缀ab后缀ba吗不等于前缀aba后缀aba长度3前缀abac≠后缀caba所以next[7]3。算下来next数组就是0, 0, 1, 0, 1, 2, 3我这里从next[1]到next[7]。这个推演过程比背代码重要得多因为考场上极大概率需要你手动推一个小例子。我在复盘时还额外练习了“如何用next数组加速匹配”的完整流程建议你也照做拿起笔在纸上模拟一遍模式串与文本串的匹配过程画清楚指针i和j的移动你才能真正记住KMP的运行机制。3.2 排序算法横向对比不只看时间复杂度和稳定性排序算法这块光记住“快排平均O(n log n)、堆排O(n log n)、归并O(n log n)”是不够的。网易的笔试题很喜欢在“稳定性”和“空间复杂度”上做文章。比如堆排序为什么不稳定因为堆排序在调整堆的过程中可能把相同值的元素相对位置打乱。快排为什么不稳定因为partition的过程本身就是基于随机选主元的交换操作相同关键字的相对顺序也没有保证。归并排序为什么稳定关键在于合并两个有序子数组时当遇到相等元素我们先把左半部分的元素放入结果数组这样相同值的前后顺序不会颠倒。我当时做了一个表格把高频排序算法的核心特征放在一起对比复习效率高了不少排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)递归栈不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3~1.5)O(n²)O(1)不稳定计数排序O(nk)O(nk)O(k)稳定注意笔试中“最坏时间复杂度O(n²)”这个坑出现频率很高尤其针对快速排序。我当时因为只记得“快排很优秀”而忽略了退化场景还专门花了时间整理了触发最坏情况的条件当数组接近有序、且每次选的基准值都落在端点附近时partition极度不平衡递归深度变成n整体退化为O(n²)。解决办法也顺手记一下随机化选择基准、三数取中法这两种优化在校招面试中属于加分项。3.3 动态规划与二分查找编程题的常客这套试卷的编程题里动态规划DP绝对是大头。做DP题的核心不是“背状态转移方程”而是掌握一套通用方法论先定义清楚状态dp[i]的含义再写出状态转移方程最后确定初始化和遍历顺序。以最经典的“最长递增子序列”为例dp[i]可以定义为“以第i个元素结尾的最长递增子序列长度”。初始化时每个dp[i]至少为1因为单个元素本身就是一个长度为1的递增子序列。状态转移时遍历j从0到i-1如果nums[j] nums[i]就尝试用dp[j] 1来更新dp[i]最终答案是max(dp)。很多人在这一步会犯“遍历顺序错误”的毛病递推dp[i]必须保证所有可能依赖的dp[j]j i已经被计算出来。所以外层循环i要从左往右走内层循环j从0到i-1这就是我们常说的“自底向上”。如果题目的状态定义更复杂比如区间DPdp[i][j]表示区间i到j的最优解那遍历顺序就得按区间长度从小到大枚举这点需要额外留意。二分查找同样容易在边界条件上翻车。我在试卷复盘时总结了一个自己用着很顺手的模板核心是“区间不变量”的思想// 找左边界第一个 target 的位置 int leftBound(vectorint nums, int target) { int left 0, right nums.size(); // [left, right) while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }用这个模板的关键是始终维护“答案在[left, right)区间内”的不变量这样就不会因为循环里加一减一搞混。笔试编程题中二分还经常和“最小化最大值”这类题意结合看到这种题第一反应就应该往二分答案的方向去想确定一个候选值写一个check函数判断可行不可行然后根据可行性收窄上下界。有道这套卷子里的编程题就有类似的思路题整体方向是一致的。3.4 机器学习基础题从过拟合到模型评估除了传统算法网易这套试卷里还有机器学习基本功的考查。关于“防止过拟合”这个高频题标准回答要覆盖到增加训练数据量、降低模型复杂度简化网络结构/减少特征维度、正则化L1/L2、Dropout、早停、数据增强。光列点不够我当时被追问最多的是“L1和L2正则化在效果上有什么区别”。简单来说L1正则化倾向于让部分权重变为0相当于在做特征选择L2正则化是让权重整体变小但不会主动置零。原因也很直观L1的惩罚项在0点不可导优化过程更容易把参数推到0附近。关于“SVM核函数的作用”核心一句话核函数把低维空间线性不可分的数据隐式映射到高维空间使得在高维空间中可以用线性超平面完成分割。但要注意核函数最妙的地方在于“隐式”——你不需要真的算出高维特征向量只需要计算两两样本的内积即可这就是“核技巧”。笔试如果考到“哪些函数可以作为核函数”需要满足Mercer条件常见的就是线性核、多项式核、高斯核RBF、sigmoid核。模型评估这块常见的混淆矩阵指标准确率、精确率、召回率、F1也建议一次性搞熟。特别是“精准率和召回率的trade-off”这个经典问题比如在垃圾邮件识别场景里我们更看重精确率因为不想把正常邮件误判为垃圾邮件而在癌症筛查场景里我们更看重召回率因为漏诊的代价远大于误诊。一道选择题里如果出现“F1值”还要会算调和平均F1 2 * precision * recall / (precision recall)分子是两者的乘积分母是两者之和。实际公司里做推荐系统、内容理解相关工作时这几个指标的使用频率非常高笔试考察它们是合理且必要的。4. 编程题实战推演一道动态规划题从审题到AC的全过程4.1 题目理解与建模思路从这一节开始进入实战环节。根据我当年的回忆和网上流传的复盘信息这套试卷里有一类非常典型的DP题给定一个非负整数数组每个元素代表你在该位置可以跳跃的最大长度问能否到达最后一个下标如果要求输出最少跳跃次数怎么办。它本质上考察的是“贪心/动态规划”的对比与取舍。我们先看更基础的版本判断能否到达。建模思路是维护一个maxReach变量代表当前能到达的最远下标遍历数组时不断更新它如果某个时刻maxReach n-1说明能到达终点。为什么这个题用贪心而不是DP因为“能到达的最远位置”只取决于前面所有位置的最大覆盖范围不需要记录每个位置的“是否可达”状态。你可以用一个变量滚动更新这就是贪心选择性质的体现。而如果题目改成“最少跳跃次数”贪心依然高效但状态记录会更复杂一些。笔试时看清题目问的是“能否”还是“最少几次”很重要两个解法虽然同源但代码差别不小。4.2 代码实现与边界条件分析把“能否到达”版本用C写出来核心逻辑非常短bool canJump(vectorint nums) { int maxReach 0; int n nums.size(); for (int i 0; i n; i) { if (i maxReach) { return false; // 当前位置已经不可达 } maxReach max(maxReach, i nums[i]); if (maxReach n - 1) { return true; } } return true; }这里有一个容易漏掉的边界当nums[i] 0时如果当前位置正好是maxReach的边界那么后续位置将全部不可达循环里的i maxReach判断会触发返回false。比如nums [2, 0, 0]第一个位置跳到最远index2但中间index1的跳跃能力为0实际上无法到达最后一个下标程序能正确识别出来。这就是“贪心法”边界判断精妙的地方不是看某个点能不能继续跳而是看最远覆盖范围是否被某个不可达点阻断。至于“最少跳跃次数”版本思路是三个变量steps记录当前步数maxReach记录在步数steps内能到达的最远位置end记录当前步数的边界。遍历数组时一旦走到end就说明需要用掉一步把end更新为maxReach同时steps。这个解法的时间复杂度O(n)空间复杂度O(1)无论在笔试还是面试中都是最优解。4.3 现场做题的时间分配与调试策略编程题在笔试中通常有2到3道总时间可能只有60到90分钟。我的经验是前5到8分钟必须完成审题和暴力解构思如果10分钟还没摸清思路立刻跳到下一题。为什么这么建议因为校招笔试看的是总分和AC题数而不是单题完美度。有一次我做题时在一道DP题上死磕了20分钟虽然最后AC了但剩下的时间只够写一个暴力解反而得不偿失。调试策略上我会先用最简单的小样例跑通逻辑比如nums [0]、nums [2, 3, 1, 1, 4]确认边界行为正确后再提交。如果提交报错先在本地打印中间变量看看是在状态更新还是边界判断出错。还有一个小技巧在写DP代码时给dp数组额外申请一个哨兵位置比如n1大小往往能省去不少“下标越界”的判断这个习惯在笔试限时环境下非常实用。5. 常见错误与避坑指南这些坑我当年都踩过5.1 next数组的“符号约定”坑KMP的next数组在不同教材里有不同定义有的next[0]-1有的next[0]0有的从0开始计数有的从1开始。我当时在牛客网的讨论区看到过很多人在“next数组的值到底应该是多少”这个问题上争论不休其实本质上就是约定不同。笔试如果遇到这类题先看题目给的示例按示例的约定去算不要凭自己背的模板直接填答案。手动推演时最好把“前缀”和“后缀”的边界写清楚避免把整个字符串本身当成最大公共前后缀这是新手最容易犯的错误。5.2 快速排序“稳定性”的错误记忆快排不稳定、堆排不稳定、归并稳定这三个结论属于“高频必背三件套”但如果不理解原因很容易在类似“新排序算法是基于哪种经典算法改进的”这种变种题上栽跟头。稳定性这个概念本身强调的就是“相同关键字的元素在排序前后的相对顺序是否保持不变”。我建议你在准备时不要只背结论而是亲自动手用一组小数据走一遍排序流程比如判断[3a, 2, 3b, 1]排序后3a和3b的相对顺序是否变化一目了然。5.3 递归算法的爆栈风险笔试中经常要写DFS比如二叉树路径总和、岛屿数量这类题。很多人的实现里会忽略递归深度的问题。虽然校招笔试的测试数据通常不会刻意设计到爆栈但如果你在代码中显示地写了递归并且处理的是链状结构的树退化成链表递归深度可能达到10万级别这时候程序会直接栈溢出。稳妥起见如果题目没有明确限制优先考虑显式栈模拟或迭代写法至少要把递归改为尾递归或者提前判断树高。这个认知在面试时主动说出来也是加分项。5.4 复杂度分析“只看循环不看递归栈”有些题你在纸上分析时间复杂度时容易忽略递归栈带来的空间开销。比如归并排序的空间复杂度是O(n)不是O(1)因为合并时需要额外数组。快速排序的空间复杂度是O(log n)因为递归调用栈的平均深度是log n最坏情况是O(n)。这种细节是选择题的最爱务必记牢。6. 备战路线与资源清单从这套试卷出发怎么系统准备校招算法笔试6.1 三轮复习法从“会做题”到“会讲题”结合我自己的备考经历我把算法笔试的准备过程拆成三轮每轮目标不同对应的时间投入也不同。如果你现在离笔试还有两个月以上可以按这个路线稳步推进如果只剩两周建议把重心放在第二轮和第三轮。第一轮知识扫盲与题型熟悉2~4周。把数据结构数组、链表、栈、队列、哈希、树、堆、图过一遍每个数据结构都搞清楚三件事底层存储方式是什么、常见操作的时间复杂度是多少、典型的应用场景有哪些。算法方面排序、二分、双指针、滑动窗口、DFS/BFS、回溯、贪心、DP这八类问题是绝对主线每一类至少刷20道题。第二轮真题训练与限时模拟1~2周。这个阶段直奔历年真题和LeetCode Hot 100。给自己设定严格的时间限制比如2小时一套题模拟真实笔试环境。做完之后一定要错题复盘把每道错题的核心考点和正确思路整理成笔记而不是只对一下答案就翻篇。第三轮总结归纳与手撕高频题1周。最后一周不要贪多求新把整理好的错题本和高频考点再过一遍。特别是KMP的next数组、快排的partition过程、反转链表、LRU缓存这类“手撕题”能做到闭着眼睛写出来为止。同时练一下“讲题”把解题思路用口语表达出来。因为笔试过了之后紧跟着就是面试面试官让你现场讲思路的概率极高。6.2 学习资源推荐与实用技巧其实备考算法笔试不需要囤积大量资料关键是把手头的资源吃透。我个人觉得最有价值的是这几样LeetCode按标签刷题重点刷数组、字符串、树、动态规划、牛客网的真题题库可以找到很多公司的历年笔试题、以及一本算法入门书我用的是一套经典的算法教材但不必迷信某一本重点是建立系统知识框架。刷题时我会遵守一个“15分钟法则”如果一道题15分钟没有任何思路直接看题解学习别人的解法和思考路径然后在第二天独立重写一遍这道题。重写这一步极其重要否则很容易出现“看懂了但写不出来”的假性掌握。6.3 笔试之外的加分准备除了纯粹的算法题网易有道的笔试还有一点值得注意它可能会在选择题中混入一些和公司业务相关的问题。比如有道做词典和翻译相关产品所以一些NLP的基础概念词向量、TF-IDF、n-gram也可能被顺带考到。如果你是冲着有道算法岗去的建议提前了解一下NLP的浅层基础知识不一定要多深入但至少知道TF-IDF是干什么的、词向量的基本思想是什么。这类“小灶知识”在笔试中可能只有一两道题的分量但也能在同等水平的候选人中帮你拉开一点点差距。另外再多说一句笔试只是校招流程的敲门砖真正决定你是否拿到offer的是后续的面试。所以笔试备考过程中养成的“手撕代码能力”和“讲解思路能力”一定要延续到面试准备中去。不要觉得笔试完了就万事大吉很多人在面试现场因为紧张或者表达不清反而把笔试阶段建立的优势给削弱了。我在实际使用中发现把每道题模拟讲解一遍哪怕只是自言自语都能显著提升面试时的流畅度。这个习惯我从笔试一直坚持到了入职以后带新人时也经常推荐给他们。这套2018年的网易有道算法笔试卷从今天的视角来看依然是相当经典的校招复习素材。技术栈会迭代题型也在微调但“数据结构与算法三大件 机器学习基础 工程实现能力”这个考察框架并没有过时。如果你正在准备校招与其焦虑竞争激烈不如静下心来把这套框架里每一块都夯实。考试归根结底考的是熟练度熟练度靠的是重复训练。祝你笔试顺利。