第四范式做的是机器学习平台和自动机器学习AutoML方向所以他们的算法笔试题向来不是纯刷题那种风格而是更看重候选人能不能从底层原理上把问题讲清楚。最近不少人在准备秋招翻出2020年这批真题来问其实哪怕放到现在这些题依然很有参考价值。我结合自己做算法岗笔试和面试的经验把这些题拆开揉碎讲一遍不只是给答案更重要的是讲清楚每道题背后的考察意图和解题思路。1. 笔试整体布局四道题覆盖了算法岗的哪些核心能力第四范式2020秋招算法笔试题一共四道覆盖了字符串处理、动态规划、贪心策略和机器学习基础这几个方向。这个出题结构很有意思它不是在考某一个单一领域而是在模拟算法工程师日常工作中的思维方式——拿到一个实际问题先拆解成合适的模型再选择对应的算法工具去求解。第一题是 KMP 字符串匹配中 next 数组的计算第二题是有限数组连续子区间求和的最大值第三题是贪心算法做任务分配第四题是一道开放性的机器学习理论题考察对损失函数和模型泛化能力之间关系的理解。这套题的光谱拉得很开从最经典的字符串算法到前沿的深度学习理论都有涉及。作为过来人我建议准备这类笔试的时候不要只看面经里的题解更重要的是理解每道题在考什么。笔试不仅仅是一个筛选门槛更是公司提前让你体验他们的工程文化。第四范式做的是企业级 AI 平台算法要落地到金融、零售、制造这些场景里所以他们会特别关注候选人是否具备从问题到模型再到工程实现的完整链路思维。接下来我按题目顺序逐个拆解每道题我都会给出完整的推导过程、代码实现和在实际业务场景中的对应关系这样你不仅能应付笔试还能真正理解这些经典算法为什么到现在依然被高频考察。2. KMP 的 next 数组字符串匹配算法笔试标准考点2.1 题目原题与要求还原题目给定了模式串 p abacaba要求计算其 next 数组。这里 next 数组的定义有两种常见口径一种是以 0 为起始索引的经典版本next[i] 表示 p[0:i] 这个子串的最长相等前后缀长度另一种是考研和部分教材使用的从 -1 开始的版本。第四范式这道题在题干中特别注明了next[i] 定义为所以首先要确保对齐定义口径。从笔试现场的还原来看题目要求的是计算这个模式串的 next 数组并写出推导过程。这类题目考察的核心有两个第一是否理解 next 数组的物理意义——它记录的是模式串中每个位置之前的子串的最长相同前后缀长度第二是否掌握 KMP 算法中 next 数组的递推构造方法这个递推过程本身也是一个可以扩展到更复杂场景的动态规划思想。2.2 手工推导全过程对 p abacaba我们逐个位置推导。首先明确一个约定next[i] 表示模式串前 i 个字符组成的子串中最长相同前后缀的长度。注意这里的前后缀不包含子串自身。i 0 时子串为 a没有真前后缀所以 next[0] 0。i 1 时子串为 ab前缀集合为 {a}后缀集合为 {b}无交集所以 next[1] 0。i 2 时子串为 aba长度为 1 的前后缀都是 a相等长度为 2 的前缀是 ab后缀是 ba不相等所以最长相同前后缀长度为 1next[2] 1。i 3 时子串为 abac前缀集合 {a, ab, aba}后缀集合 {c, ac, bac}没有相等的情况所以 next[3] 0。i 4 时子串为 abaca前缀集合 {a, ab, aba, abac}后缀集合 {a, ca, aca, baca}长度为 1 的前后缀均为 a再检查长度为 2 的情况前缀 ab后缀 ca不相等长度为 3 时前缀 aba后缀 aca不相等长度 4 时前缀 abac后缀 baca 也不相等。因此 next[4] 1。i 5 时子串为 abacab前缀集合 {a, ab, aba, abac, abaca}后缀集合 {b, ab, cab, acab, bacab}。长度为 1 时前缀 a后缀 b 不相等长度为 2 时前缀 ab后缀 ab 相等。继续检查长度 3前缀 aba后缀 cab 不相等长度 4 时前缀 abac后缀 acab 不相等长度 5 时前缀 abaca后缀 bacab 不相等。所以最长相同前后缀长度为 2next[5] 2。i 6 时子串为 abacaba前缀集合 {a, ab, aba, abac, abaca, abacab}后缀集合 {a, ba, aba, caba, acaba, bacaba}。长度为 1 时都是 a相等长度为 2 时前缀 ab后缀 ba 不相等长度为 3 时前缀 aba后缀 aba 相等长度为 4 时前缀 abac后缀 caba 不相等长度 5 时前缀 abaca后缀 acaba 不相等长度 6 时前缀 abacab后缀 bacaba 不相等。所以 longest 3next[6] 3。最终得到 next 数组[0, 0, 1, 0, 1, 2, 3]。2.3 递推构造的代码实现与优化手工推导可以理解原理但笔试中如果要求写出计算 next 数组的代码我们需要用递推的方式来避免重复计算。核心逻辑是如果 p[i] p[j]那么 next[i] j 1否则 j 需要回退到 next[j-1]。vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); int j 0; for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; }这个实现的时间复杂度是 O(m)空间复杂度 O(m)。笔试现场可能不会要求写出完整代码但会在后续编程题中用到这个构造过程所以还是练熟比较好。2.4 为什么这个考点在业务中依然重要可能有人觉得 KMP 是纯理论算法实际工程中不会手写。但在文本检索、日志解析、基因序列比对、敏感词过滤等场景中字符串模式匹配仍然是高频需求。比如在第四范式的业务场景里需要从大量非结构化文本日志中提取特定模式的特征高效的字符串匹配能显著降低推理延迟。做模型服务的时候一个正则表达式引擎内部的核心算法就包含 KMP 的思想理解它有助于在性能瓶颈出现时快速定位问题。另一个容易被忽视的点是next 数组的递推逻辑本质上是一种带状态记忆的动态规划。面试官想确认你不仅会背模板还能把这个失败时回退的思路迁移到其他场景。比如很多自动机类的算法、AC 自动机等多模式匹配算法其实都是 KMP 思想的延伸。3. 最大连续子区间和从暴力到动态规划的思维升级3.1 题目原题与要求还原这道题是另一个经典问题给定一个整数数组 nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。这是 LeetCode 53 题的原型也是各个公司笔试的常客。第四范式在这一题上并不会只满足于你写出 Kadane 算法的代码他们会在后续面试中追问其正确性证明和边界条件处理笔试现场则是要求给出能处理负数数组的完整实现。这道题之所以经久不衰是因为它隐藏着一个重要的思维跃迁从枚举所有可能子区间到利用以某个位置结尾的局部最优解来递推全局最优解。这个思路是整个动态规划体系的入门钥匙。3.2 暴力解法分析为什么要先想清楚暴力解笔试中直接写 Kadane 算法是够的但真正优秀的人会先在草稿纸上推导一遍暴力解法再过渡到优化解法。暴力解是枚举每个左端点和右端点计算区间和并更新最大值时间复杂度 O(n^2)。这个过程中有一个关键观察如果我们固定右端点 i那么以 i 结尾的所有子区间中最大和其实可以由以 i-1 结尾的最大子区间和加上 nums[i] 得出。换句话说设 dp[i] 表示以第 i 个元素结尾的连续子数组的最大和那么状态转移方程是 dp[i] max(nums[i], dp[i-1] nums[i])。这背后的直觉是如果 dp[i-1] 为正数那么把它加到 nums[i] 上一定会让结果更大如果 dp[i-1] 为负数那不如从 nums[i] 重新开始。整个逻辑可以浓缩为一个变量滚动维护。3.3 标准实现与空间优化经典实现如下def maxSubArray(nums): cur max_sum nums[0] for num in nums[1:]: cur max(num, cur num) max_sum max(max_sum, cur) return max_sum这里的 cur 就是 dp[i-1] 的滚动状态max_sum 维护全局最大。空间复杂度从 O(n) 降到了 O(1)。笔试中如果能额外说明为什么可以只保留一个变量而不是整个 dp 数组会是一个重要的加分项——它体现了你对状态依赖关系的理解dp[i] 只依赖 dp[i-1]所以前面的状态可以丢弃。3.4 扩展思考最大子矩阵和与最大子数组的实战映射笔试中如果这道题以变体形式出现比如要求返回最大子数组的起始和结束下标或者输入是二维矩阵时求最大子矩阵和降维为多轮一维问题处理思路要提前准备好。第四范式的算法岗日常工作中经常会遇到时间序列数据比如某个特征在连续时间段内的累积效果本质上就是在找最大连续子区间这和金融领域计算最大回撤也有异曲同工之处。我在实际面试中遇到过一个追问如果数组允许循环该如何处理最大循环子数组和解法是把问题拆成两种情况——不跨越边界直接用 Kadane跨越边界则等价于总数组和减去最小子数组和。这种举一反三的能力在笔试之后的面试环节非常加分。4. 贪心算法解任务分配看似简单实则暗藏玄机4.1 题目原题场景还原这类题在各大公司笔试中很常见具体描述通常是有 n 个任务每个任务有开始时间和结束时间同一时刻只能做一个任务求最多能完成多少个任务。或者是给定一些会议的开始时间和结束时间求能参加的最大会议数。第四范式的题目形式可能略有变化但核心模型是区间调度问题考察贪心策略的选择和证明能力。4.2 贪心策略的选择为什么按结束时间排序才是正确的面对区间调度问题常见的三种策略是按开始时间早的优先、按区间持续时间短的优先、按结束时间早的优先。第一个和第二个策略都很容易构造出反例。举个反例来说明按开始时间排序的错误任务 A [1, 5]任务 B [2, 3]任务 C [4, 6]。按开始时间排序会先选 A然后 B 和 C 都无法选了最多完成 1 个但正确做法是先选 B再选 C能完成 2 个任务。按结束时间排序的策略才是正确的。证明思路是贪心交换法假设某个最优解中第一个选择的任务结束时间不是所有任务中最早的我们可以把这个任务替换成结束时间最早的且与它兼容的任务不会减少能完成的任务总数。因为结束时间更早剩余的时间只会更多所以不会让后续选择变差。这个替换论证是面试中证明贪心正确性的标准套路。4.3 完整代码与边界条件def maxTasks(tasks): # tasks: list of (start, end) tasks.sort(keylambda x: x[1]) count 0 last_end -float(inf) for start, end in tasks: if start last_end: count 1 last_end end return count边界条件要注意如果任务的开始时间等于前一个任务的结束时间是可以连续做的所以判断条件是 start last_end 而不是 start last_end。另外输入任务可能未排序需要先按结束时间排序。4.4 变体带权重的区间调度如何用动态规划解决如果笔试难度升级给每个任务加上一个权重要求选择互不冲突的任务使总权重最大贪心就失效了需要改成动态规划先将任务按结束时间排序定义 dp[i] 为前 i 个任务能获得的最大权重转移方程是 dp[i] max(dp[i-1], weight[i] dp[p[i]])其中 p[i] 表示与任务 i 不冲突的前一个任务的下标。这个变体在面试环节出现的概率很高因为它把贪心失效的场景作为切入点展开讨论考察的是对两类算法的边界把握能力。4.5 贪心策略在算法平台中的应用第四范式做企业级 AI 平台时任务调度、资源分配、模型推理时的 GPU 利用率优化都会涉及区间调度思想。比如在 AutoML 场景中多个模型训练任务共享计算资源如何合理安排任务执行顺序来最小化总耗时或最大化吞吐量就是一个带约束的调度优化问题。笔试中出现这道题某种意义上也是公司业务场景的映射。5. 机器学习理论题损失函数与模型泛化能力的关系5.1 题目原题推测与考察意图第四范式的算法笔试中通常会有一道机器学习领域的理论题考察对核心概念的理解深度。2020年这道题的考察点是损失函数的选择如何影响模型的泛化能力具体场景可能是对比 L1 损失和 L2 损失的差异或者是对比交叉熵损失和均方误差在分类任务中的表现。这类开放性问题没有标准答案它考察的是你是否真正理解损失函数背后的数学原理和在实际业务中如何做选择。5.2 L1 损失与 L2 损失的对比分析从梯度角度分析L2 损失对误差的梯度是线性的误差越大梯度越大L1 损失的梯度是常数误差较大时梯度不会继续增大。这意味着当训练数据中存在离群点时L2 损失会给予离群点过大的梯度导致模型为了拟合离群点而牺牲整体表现L1 损失对离群点的容忍度更高更稳健。从解的性质来看L1 正则化倾向于产生稀疏解L2 正则化倾向于让权重尽可能小且均匀分布。在第四范式的业务中特征维度可能非常高训练样本相对有限L1 正则化可以把不重要特征的权重压缩到 0实现特征选择效果提升模型的泛化能力。L2 正则化则更适合处理特征间相关性较强的情况它能保持解的唯一性。在笔试中回答这个问题时我应该从以下三个层面展开第一是损失函数的公式表达及对应的梯度行为第二是它们对离群点的敏感度和对解空间结构的影响第三是结合业务场景给出选择建议并说明超参数的调整经验。这种数学-性质-业务的三层结构是面试官最认可的回答框架。5.3 交叉熵损失与 MSE 在分类任务中的选择逻辑对于分类问题交叉熵损失是默认选择。从信息论角度看交叉熵衡量的是预测分布与真实分布之间的 KL 散度它的梯度形式是预测概率与真实标签的差值当预测错误时梯度较大利于参数更新。MSE 用于分类问题时会遇到梯度消失问题——因为 sigmoid 或 softmax 函数在饱和区的导数趋近于 0MSE 的梯度中包含了这个导数项导致训练极其缓慢。我把这个问题的回答浓缩成一张对比表笔试现场可以快速提取要点维度交叉熵损失均方误差梯度形式预测值与真实值的差误差乘以激活函数导数分类任务训练速度快错误样本梯度大慢易饱和对异常预测的惩罚对数增长惩罚合理平方增长惩罚过重适用场景分类、多标签回归、自监督重建任务数值稳定性需配合 softmax 的 log 技巧相对稳定5.4 过拟合与正则化的笔试标准回答损失函数选择直接影响模型的偏差-方差权衡。L2 正则化等价于给参数引入高斯先验L1 正则化等价于拉普拉斯先验。从贝叶斯视角理解正则化是第四范式这类机器学习公司特别看重的思维深度。它们笔试题目虽然不一定直接问贝叶斯公式但实际做模型平台时对不同先验假设如何影响最终模型容量与泛化性能有深刻理解的候选人更容易在实际业务中做出合理的模型选择。我在笔试题中通常会补充训练集损失与验证集损失的对比分析方法当训练损失下降但验证损失上升时说明进入过拟合区间应增强正则化系数或增加数据增强当两者都在高位不降时说明模型容量不足此时调整损失函数的意义不大。损失函数跟过拟合是一对紧密咬合的齿轮真正理解它们的互动关系才是这一题的核心。5.5 如何准备这类开放理论题这类题目没有标准刷题路径更依赖平日的积累。我的建议是吃透三件事第一每个损失函数的数学表达式、梯度表达式和 Hessian 矩阵特征第二想象一个具体业务场景比如在金融风控场景中违约样本极少此时用加权交叉熵或用 Focal Loss 的效果差异是什么第三多了解 AutoML 场景下损失函数选择的部分——这正是第四范式产品中非常重要的环节。6. 数据结构与排序算法基础中的基础6.1 排序算法在笔试中的考察方式第四范式这套题的笔试中围绕排序算法的考察通常不会让你直接手写快排而是给出一个具体场景让你选择合适的排序算法或者基于堆排序来解决 Top-K 问题。2020 年的笔试中排序是一个穿插在其他题目里的背景知识但面试环节可能会追问排序算法的稳定性和空间复杂度。我把常见排序算法进行了整理方便笔试前快速回顾排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定插入排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定6.2 快排的退化问题与优化手段快速排序之所以平均快是因为它利用了缓存局部性和原地分区操作。但当输入数据本身接近有序或逆序时如果每次选取的基准都是最大或最小值快排会退化到 O(n^2)。优化手段包括随机选取基准、三数取中法、在子序列长度小于一定阈值时改用插入排序。我在实际面试中被追问过为什么工程上的 sort 函数不用纯快排而是混排答案是在数据量较小时递归开销和分区操作带来的常数因子可能超过插入排序的 O(n^2) 最坏代价。所以成熟的排序库通常是小数据量插排、大数据量快排或归并排的组合策略。笔试中如果能提到这些优化细节会显得你代码功底扎实。6.3 堆排序与 Top-K 问题大数据场景的经典解法第四范式的业务中经常需要从海量特征中筛出 Top-K 重要特征从海量样本中找出异常分数最高的 K 个样本这类问题在线性扫描一遍的前提下用堆来解决是最优的。具体做法是维护一个大小为 K 的最小堆遍历数据时如果当前元素大于堆顶就替换堆顶并调整堆结构。最终堆里保留的就是最大的 K 个元素。时间复杂度 O(n log K)空间复杂度 O(K)。笔试中可能会让你实现这个逻辑代码核心是熟悉 heapq 或手写堆的下沉操作。import heapq def top_k(nums, k): heap nums[:k] heapq.heapify(heap) for num in nums[k:]: if num heap[0]: heapq.heapreplace(heap, num) return heap6.4 外部排序与归并思路的延伸当数据量大到无法全部加载到内存时外部排序是必经之路核心思路就是归并排序的分而治之大文件切分成多个有序的小文件再通过多路归并得到整体有序结果。虽然笔试不一定会直接考外部排序但归并排序的理解是基础尤其当面试官追问如果数据量超过内存怎么办时这个思路几乎是唯一答案。从第四范式业务角度看分布式计算框架中的 shuffle 阶段就包含了大量归并排序的变体。理解归并排序合并两个有序区间这个核心操作的复杂度与实现细节能帮助理解和优化分布式任务中的数据传输和排序开销。7. 图论与搜索从 KMP 联想到的更广泛算法版图7.1 二分图与 HK 算法复杂模型匹配问题热词中出现二分图 hk算法不是偶然这类图论算法在现实业务中有很强的映射场景比如在推荐系统中用户和物品天然构成二分图衡量用户与物品的匹配程度可以转化为最大匹配问题。Hopcroft-Karp 算法是求解二分图最大匹配的高效算法通过每次寻找多条增广路径并使用 BFS 分层和 DFS 增广把复杂度降低到 O(E sqrt(V))。笔试中如果考二分图直接考 HK 算法的概率不大但考匈牙利算法的概率较高。两者解决的问题相同只是优化手段不同。建议先掌握匈牙利算法的增广路径思想和代码模板再理解 HK 算法为什么通过 BFS 分层能加速多路匹配。7.2 Dijkstra 算法与最短路径的变体热词中出现dijkstra算法这也是各类公司算法笔试的高频考点。经典 Dijkstra 适用于单源正权图核心在于贪心选择当前距离最小的未访问节点通过优先队列实现 O((VE) log V)。笔试中容易出现的变体包括要求输出路径本身处理有负权边时如何通过 Bellman-Ford 或 SPFA 解决以及如何计算从起点到每个节点的最短路径条数。在第四范式的业务场景中物流路径优化、供应链网络分析、知识图谱中的关系路径查询等都与最短路径问题相关。虽然算法岗日常工作中更常用现成的图计算框架但理解底层算法原理有助于在框架性能调优时做出正确的索引和存储选择。7.3 拓扑排序与 Kahn 算法任务依赖关系建模Kahn 算法解决的是拓扑排序问题对有向无环图输出一种节点顺序使得对每条有向边 u - vu 都出现在 v 之前。算法核心是不断选取入度为 0 的节点删除其出边并更新相关节点入度。这个算法在工程调度和依赖关系分析中非常常见。比如在 AutoML 平台中一个完整的机器学习流水线可能包含数据清洗、特征工程、模型训练、模型评估、模型部署等多个阶段每个阶段之间存在依赖关系利用 Kahn 算法可以检测是否存在循环依赖并给出一个可执行的调度顺序。笔试中如果考到拓扑排序重点是把入度表、邻接表和队列的配合逻辑写对。7.4 KMP 与自动机思想的统一视角很多人把字符串算法和图论算法当成两个独立模块但从更高的抽象视角看KMP 的核心就是构造一个有限状态自动机模式串的每个匹配状态对应自动机的一个节点匹配失败时的回退就是自动机的状态转移。所以 KMP 本质上是一种特殊的 DFA 构建问题这就是为什么 KMP 问题的变体能自然延伸到 AC 自动机和后缀自动机。从笔试准备的角度我建议将所有图算法统一到状态-转移的思维框架下KMP 是线性序上的确定性自动机拓扑排序是偏序关系的线性展开Dijkstra 是加权有向图上的动态规划加贪心优化。这套统一的框架能让你在面对新题时不慌因为它把问题的本质归结为状态空间加转移规则的建模而不是死记硬背某个算法模板。8. 笔试之外从刷题到算法工程师思维的转变8.1 2020真题在今天依然有价值的三个原因很多人在刷真题时会问2020年的题目到今天还有参考价值吗我觉得有而且价值不低。第一字符串、动态规划、贪心、排序、图论这五大板块是所有算法岗笔试恒定的基本面变化的只是包装方式核心模型几十年都没变。第二第四范式的真题能反映出这家公司对候选人的期望——不仅要会解题还要能解释为什么这么解以及这个解法在业务中的对应物是什么。第三这套题目的难度和区分度设计得很合理前两题保证基础分第三题检验策略思维第四题拉开深度差距这种结构本身就是模板级的。8.2 刷题之外的隐性准备笔试除了做题还有一些隐性准备容易被忽略。比如编程环境的选择——多数在线笔试平台支持 Python 和 C但不同语言的输入输出模板和运行效率有差异。我个人建议提前熟悉目标公司的笔试平台了解是否需要自己处理多组测试用例的输入循环是否需要考虑大数溢出。另一个容易被忽略的点是代码风格。笔试虽然只看测试用例是否通过但少数情况下面试官会调阅你的笔试代码来了解你的编码习惯。变量命名清晰、函数边界明确、关键逻辑有简短注释这些细节会成为后续面试中印象分的组成部分。我见过有候选人笔试分数一样但面试时因为代码风格更专业而获得额外认可。8.3 时间分配策略笔试现场的取舍以第四范式这套题为例总时长大约 90 分钟到 120 分钟四道题的价值并不均等。前两题属于保分题建议控制在 20 分钟内完成并确保测试用例全部通过第三题如果思路清晰10 分钟内能搞定第四题作为开放题值得预留至少 30 分钟来组织一个结构完整的回答因为它的区分度最高。如果遇到卡壳的题切记不要死磕。先跳过做后面的题再回来补前面的题是笔试最基本的时间管理策略。卡壳常常是因为思维走进了死胡同跳出来换个角度再看往往能很快找到解法。8.4 从真题到真实业务能力算法岗的长期成长路径笔试只是算法岗的第一关真正决定职业发展的还是解决真实业务问题的能力。第四范式的业务场景对算法工程师有很高的复合要求既要有机器学习的建模能力又要有扎实的工程实现功底还要具备将业务问题转化为数学模型的抽象能力。这套笔试中的 KMP、贪心、损失函数选择这些题目表面上看是零散知识点背后其实都是这些核心能力的最小单元。作为过来人我强烈建议在准备笔试的同时有意识地做一件从题目到论文的延伸阅读。比如看到最大连续子数组和的问题就去了解一下在线凸优化的 regret bound 分析看到贪心区间调度就去了解一下任务调度问题在分布式系统中的变体。这种由点及面的学习方式才是把一次笔试准备转化为长期竞争力的关键。我自己在准备面试和带新人时发现一个规律那些笔试排名靠前的人并不是刷题量最多的人而是能把每道题背后的原理吃透并讲清楚的人。所以你在准备这套真题的时候不要只盯着答案是什么更要问自己为什么是这个答案以及如果场景变了这个答案还成立吗。带着这三个问题去刷完这四道题收获会远超一套题的预期。 
长河君 · 2026/9/1 21:58:38 · 阅读 1.2k 2020第四范式算法笔试题全解析：KMP到损失函数一网打尽
第四范式做的是机器学习平台和自动机器学习AutoML方向所以他们的算法笔试题向来不是纯刷题那种风格而是更看重候选人能不能从底层原理上把问题讲清楚。最近不少人在准备秋招翻出2020年这批真题来问其实哪怕放到现在这些题依然很有参考价值。我结合自己做算法岗笔试和面试的经验把这些题拆开揉碎讲一遍不只是给答案更重要的是讲清楚每道题背后的考察意图和解题思路。1. 笔试整体布局四道题覆盖了算法岗的哪些核心能力第四范式2020秋招算法笔试题一共四道覆盖了字符串处理、动态规划、贪心策略和机器学习基础这几个方向。这个出题结构很有意思它不是在考某一个单一领域而是在模拟算法工程师日常工作中的思维方式——拿到一个实际问题先拆解成合适的模型再选择对应的算法工具去求解。第一题是 KMP 字符串匹配中 next 数组的计算第二题是有限数组连续子区间求和的最大值第三题是贪心算法做任务分配第四题是一道开放性的机器学习理论题考察对损失函数和模型泛化能力之间关系的理解。这套题的光谱拉得很开从最经典的字符串算法到前沿的深度学习理论都有涉及。作为过来人我建议准备这类笔试的时候不要只看面经里的题解更重要的是理解每道题在考什么。笔试不仅仅是一个筛选门槛更是公司提前让你体验他们的工程文化。第四范式做的是企业级 AI 平台算法要落地到金融、零售、制造这些场景里所以他们会特别关注候选人是否具备从问题到模型再到工程实现的完整链路思维。接下来我按题目顺序逐个拆解每道题我都会给出完整的推导过程、代码实现和在实际业务场景中的对应关系这样你不仅能应付笔试还能真正理解这些经典算法为什么到现在依然被高频考察。2. KMP 的 next 数组字符串匹配算法笔试标准考点2.1 题目原题与要求还原题目给定了模式串 p abacaba要求计算其 next 数组。这里 next 数组的定义有两种常见口径一种是以 0 为起始索引的经典版本next[i] 表示 p[0:i] 这个子串的最长相等前后缀长度另一种是考研和部分教材使用的从 -1 开始的版本。第四范式这道题在题干中特别注明了next[i] 定义为所以首先要确保对齐定义口径。从笔试现场的还原来看题目要求的是计算这个模式串的 next 数组并写出推导过程。这类题目考察的核心有两个第一是否理解 next 数组的物理意义——它记录的是模式串中每个位置之前的子串的最长相同前后缀长度第二是否掌握 KMP 算法中 next 数组的递推构造方法这个递推过程本身也是一个可以扩展到更复杂场景的动态规划思想。2.2 手工推导全过程对 p abacaba我们逐个位置推导。首先明确一个约定next[i] 表示模式串前 i 个字符组成的子串中最长相同前后缀的长度。注意这里的前后缀不包含子串自身。i 0 时子串为 a没有真前后缀所以 next[0] 0。i 1 时子串为 ab前缀集合为 {a}后缀集合为 {b}无交集所以 next[1] 0。i 2 时子串为 aba长度为 1 的前后缀都是 a相等长度为 2 的前缀是 ab后缀是 ba不相等所以最长相同前后缀长度为 1next[2] 1。i 3 时子串为 abac前缀集合 {a, ab, aba}后缀集合 {c, ac, bac}没有相等的情况所以 next[3] 0。i 4 时子串为 abaca前缀集合 {a, ab, aba, abac}后缀集合 {a, ca, aca, baca}长度为 1 的前后缀均为 a再检查长度为 2 的情况前缀 ab后缀 ca不相等长度为 3 时前缀 aba后缀 aca不相等长度 4 时前缀 abac后缀 baca 也不相等。因此 next[4] 1。i 5 时子串为 abacab前缀集合 {a, ab, aba, abac, abaca}后缀集合 {b, ab, cab, acab, bacab}。长度为 1 时前缀 a后缀 b 不相等长度为 2 时前缀 ab后缀 ab 相等。继续检查长度 3前缀 aba后缀 cab 不相等长度 4 时前缀 abac后缀 acab 不相等长度 5 时前缀 abaca后缀 bacab 不相等。所以最长相同前后缀长度为 2next[5] 2。i 6 时子串为 abacaba前缀集合 {a, ab, aba, abac, abaca, abacab}后缀集合 {a, ba, aba, caba, acaba, bacaba}。长度为 1 时都是 a相等长度为 2 时前缀 ab后缀 ba 不相等长度为 3 时前缀 aba后缀 aba 相等长度为 4 时前缀 abac后缀 caba 不相等长度 5 时前缀 abaca后缀 acaba 不相等长度 6 时前缀 abacab后缀 bacaba 不相等。所以 longest 3next[6] 3。最终得到 next 数组[0, 0, 1, 0, 1, 2, 3]。2.3 递推构造的代码实现与优化手工推导可以理解原理但笔试中如果要求写出计算 next 数组的代码我们需要用递推的方式来避免重复计算。核心逻辑是如果 p[i] p[j]那么 next[i] j 1否则 j 需要回退到 next[j-1]。vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); int j 0; for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; }这个实现的时间复杂度是 O(m)空间复杂度 O(m)。笔试现场可能不会要求写出完整代码但会在后续编程题中用到这个构造过程所以还是练熟比较好。2.4 为什么这个考点在业务中依然重要可能有人觉得 KMP 是纯理论算法实际工程中不会手写。但在文本检索、日志解析、基因序列比对、敏感词过滤等场景中字符串模式匹配仍然是高频需求。比如在第四范式的业务场景里需要从大量非结构化文本日志中提取特定模式的特征高效的字符串匹配能显著降低推理延迟。做模型服务的时候一个正则表达式引擎内部的核心算法就包含 KMP 的思想理解它有助于在性能瓶颈出现时快速定位问题。另一个容易被忽视的点是next 数组的递推逻辑本质上是一种带状态记忆的动态规划。面试官想确认你不仅会背模板还能把这个失败时回退的思路迁移到其他场景。比如很多自动机类的算法、AC 自动机等多模式匹配算法其实都是 KMP 思想的延伸。3. 最大连续子区间和从暴力到动态规划的思维升级3.1 题目原题与要求还原这道题是另一个经典问题给定一个整数数组 nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。这是 LeetCode 53 题的原型也是各个公司笔试的常客。第四范式在这一题上并不会只满足于你写出 Kadane 算法的代码他们会在后续面试中追问其正确性证明和边界条件处理笔试现场则是要求给出能处理负数数组的完整实现。这道题之所以经久不衰是因为它隐藏着一个重要的思维跃迁从枚举所有可能子区间到利用以某个位置结尾的局部最优解来递推全局最优解。这个思路是整个动态规划体系的入门钥匙。3.2 暴力解法分析为什么要先想清楚暴力解笔试中直接写 Kadane 算法是够的但真正优秀的人会先在草稿纸上推导一遍暴力解法再过渡到优化解法。暴力解是枚举每个左端点和右端点计算区间和并更新最大值时间复杂度 O(n^2)。这个过程中有一个关键观察如果我们固定右端点 i那么以 i 结尾的所有子区间中最大和其实可以由以 i-1 结尾的最大子区间和加上 nums[i] 得出。换句话说设 dp[i] 表示以第 i 个元素结尾的连续子数组的最大和那么状态转移方程是 dp[i] max(nums[i], dp[i-1] nums[i])。这背后的直觉是如果 dp[i-1] 为正数那么把它加到 nums[i] 上一定会让结果更大如果 dp[i-1] 为负数那不如从 nums[i] 重新开始。整个逻辑可以浓缩为一个变量滚动维护。3.3 标准实现与空间优化经典实现如下def maxSubArray(nums): cur max_sum nums[0] for num in nums[1:]: cur max(num, cur num) max_sum max(max_sum, cur) return max_sum这里的 cur 就是 dp[i-1] 的滚动状态max_sum 维护全局最大。空间复杂度从 O(n) 降到了 O(1)。笔试中如果能额外说明为什么可以只保留一个变量而不是整个 dp 数组会是一个重要的加分项——它体现了你对状态依赖关系的理解dp[i] 只依赖 dp[i-1]所以前面的状态可以丢弃。3.4 扩展思考最大子矩阵和与最大子数组的实战映射笔试中如果这道题以变体形式出现比如要求返回最大子数组的起始和结束下标或者输入是二维矩阵时求最大子矩阵和降维为多轮一维问题处理思路要提前准备好。第四范式的算法岗日常工作中经常会遇到时间序列数据比如某个特征在连续时间段内的累积效果本质上就是在找最大连续子区间这和金融领域计算最大回撤也有异曲同工之处。我在实际面试中遇到过一个追问如果数组允许循环该如何处理最大循环子数组和解法是把问题拆成两种情况——不跨越边界直接用 Kadane跨越边界则等价于总数组和减去最小子数组和。这种举一反三的能力在笔试之后的面试环节非常加分。4. 贪心算法解任务分配看似简单实则暗藏玄机4.1 题目原题场景还原这类题在各大公司笔试中很常见具体描述通常是有 n 个任务每个任务有开始时间和结束时间同一时刻只能做一个任务求最多能完成多少个任务。或者是给定一些会议的开始时间和结束时间求能参加的最大会议数。第四范式的题目形式可能略有变化但核心模型是区间调度问题考察贪心策略的选择和证明能力。4.2 贪心策略的选择为什么按结束时间排序才是正确的面对区间调度问题常见的三种策略是按开始时间早的优先、按区间持续时间短的优先、按结束时间早的优先。第一个和第二个策略都很容易构造出反例。举个反例来说明按开始时间排序的错误任务 A [1, 5]任务 B [2, 3]任务 C [4, 6]。按开始时间排序会先选 A然后 B 和 C 都无法选了最多完成 1 个但正确做法是先选 B再选 C能完成 2 个任务。按结束时间排序的策略才是正确的。证明思路是贪心交换法假设某个最优解中第一个选择的任务结束时间不是所有任务中最早的我们可以把这个任务替换成结束时间最早的且与它兼容的任务不会减少能完成的任务总数。因为结束时间更早剩余的时间只会更多所以不会让后续选择变差。这个替换论证是面试中证明贪心正确性的标准套路。4.3 完整代码与边界条件def maxTasks(tasks): # tasks: list of (start, end) tasks.sort(keylambda x: x[1]) count 0 last_end -float(inf) for start, end in tasks: if start last_end: count 1 last_end end return count边界条件要注意如果任务的开始时间等于前一个任务的结束时间是可以连续做的所以判断条件是 start last_end 而不是 start last_end。另外输入任务可能未排序需要先按结束时间排序。4.4 变体带权重的区间调度如何用动态规划解决如果笔试难度升级给每个任务加上一个权重要求选择互不冲突的任务使总权重最大贪心就失效了需要改成动态规划先将任务按结束时间排序定义 dp[i] 为前 i 个任务能获得的最大权重转移方程是 dp[i] max(dp[i-1], weight[i] dp[p[i]])其中 p[i] 表示与任务 i 不冲突的前一个任务的下标。这个变体在面试环节出现的概率很高因为它把贪心失效的场景作为切入点展开讨论考察的是对两类算法的边界把握能力。4.5 贪心策略在算法平台中的应用第四范式做企业级 AI 平台时任务调度、资源分配、模型推理时的 GPU 利用率优化都会涉及区间调度思想。比如在 AutoML 场景中多个模型训练任务共享计算资源如何合理安排任务执行顺序来最小化总耗时或最大化吞吐量就是一个带约束的调度优化问题。笔试中出现这道题某种意义上也是公司业务场景的映射。5. 机器学习理论题损失函数与模型泛化能力的关系5.1 题目原题推测与考察意图第四范式的算法笔试中通常会有一道机器学习领域的理论题考察对核心概念的理解深度。2020年这道题的考察点是损失函数的选择如何影响模型的泛化能力具体场景可能是对比 L1 损失和 L2 损失的差异或者是对比交叉熵损失和均方误差在分类任务中的表现。这类开放性问题没有标准答案它考察的是你是否真正理解损失函数背后的数学原理和在实际业务中如何做选择。5.2 L1 损失与 L2 损失的对比分析从梯度角度分析L2 损失对误差的梯度是线性的误差越大梯度越大L1 损失的梯度是常数误差较大时梯度不会继续增大。这意味着当训练数据中存在离群点时L2 损失会给予离群点过大的梯度导致模型为了拟合离群点而牺牲整体表现L1 损失对离群点的容忍度更高更稳健。从解的性质来看L1 正则化倾向于产生稀疏解L2 正则化倾向于让权重尽可能小且均匀分布。在第四范式的业务中特征维度可能非常高训练样本相对有限L1 正则化可以把不重要特征的权重压缩到 0实现特征选择效果提升模型的泛化能力。L2 正则化则更适合处理特征间相关性较强的情况它能保持解的唯一性。在笔试中回答这个问题时我应该从以下三个层面展开第一是损失函数的公式表达及对应的梯度行为第二是它们对离群点的敏感度和对解空间结构的影响第三是结合业务场景给出选择建议并说明超参数的调整经验。这种数学-性质-业务的三层结构是面试官最认可的回答框架。5.3 交叉熵损失与 MSE 在分类任务中的选择逻辑对于分类问题交叉熵损失是默认选择。从信息论角度看交叉熵衡量的是预测分布与真实分布之间的 KL 散度它的梯度形式是预测概率与真实标签的差值当预测错误时梯度较大利于参数更新。MSE 用于分类问题时会遇到梯度消失问题——因为 sigmoid 或 softmax 函数在饱和区的导数趋近于 0MSE 的梯度中包含了这个导数项导致训练极其缓慢。我把这个问题的回答浓缩成一张对比表笔试现场可以快速提取要点维度交叉熵损失均方误差梯度形式预测值与真实值的差误差乘以激活函数导数分类任务训练速度快错误样本梯度大慢易饱和对异常预测的惩罚对数增长惩罚合理平方增长惩罚过重适用场景分类、多标签回归、自监督重建任务数值稳定性需配合 softmax 的 log 技巧相对稳定5.4 过拟合与正则化的笔试标准回答损失函数选择直接影响模型的偏差-方差权衡。L2 正则化等价于给参数引入高斯先验L1 正则化等价于拉普拉斯先验。从贝叶斯视角理解正则化是第四范式这类机器学习公司特别看重的思维深度。它们笔试题目虽然不一定直接问贝叶斯公式但实际做模型平台时对不同先验假设如何影响最终模型容量与泛化性能有深刻理解的候选人更容易在实际业务中做出合理的模型选择。我在笔试题中通常会补充训练集损失与验证集损失的对比分析方法当训练损失下降但验证损失上升时说明进入过拟合区间应增强正则化系数或增加数据增强当两者都在高位不降时说明模型容量不足此时调整损失函数的意义不大。损失函数跟过拟合是一对紧密咬合的齿轮真正理解它们的互动关系才是这一题的核心。5.5 如何准备这类开放理论题这类题目没有标准刷题路径更依赖平日的积累。我的建议是吃透三件事第一每个损失函数的数学表达式、梯度表达式和 Hessian 矩阵特征第二想象一个具体业务场景比如在金融风控场景中违约样本极少此时用加权交叉熵或用 Focal Loss 的效果差异是什么第三多了解 AutoML 场景下损失函数选择的部分——这正是第四范式产品中非常重要的环节。6. 数据结构与排序算法基础中的基础6.1 排序算法在笔试中的考察方式第四范式这套题的笔试中围绕排序算法的考察通常不会让你直接手写快排而是给出一个具体场景让你选择合适的排序算法或者基于堆排序来解决 Top-K 问题。2020 年的笔试中排序是一个穿插在其他题目里的背景知识但面试环节可能会追问排序算法的稳定性和空间复杂度。我把常见排序算法进行了整理方便笔试前快速回顾排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定插入排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定6.2 快排的退化问题与优化手段快速排序之所以平均快是因为它利用了缓存局部性和原地分区操作。但当输入数据本身接近有序或逆序时如果每次选取的基准都是最大或最小值快排会退化到 O(n^2)。优化手段包括随机选取基准、三数取中法、在子序列长度小于一定阈值时改用插入排序。我在实际面试中被追问过为什么工程上的 sort 函数不用纯快排而是混排答案是在数据量较小时递归开销和分区操作带来的常数因子可能超过插入排序的 O(n^2) 最坏代价。所以成熟的排序库通常是小数据量插排、大数据量快排或归并排的组合策略。笔试中如果能提到这些优化细节会显得你代码功底扎实。6.3 堆排序与 Top-K 问题大数据场景的经典解法第四范式的业务中经常需要从海量特征中筛出 Top-K 重要特征从海量样本中找出异常分数最高的 K 个样本这类问题在线性扫描一遍的前提下用堆来解决是最优的。具体做法是维护一个大小为 K 的最小堆遍历数据时如果当前元素大于堆顶就替换堆顶并调整堆结构。最终堆里保留的就是最大的 K 个元素。时间复杂度 O(n log K)空间复杂度 O(K)。笔试中可能会让你实现这个逻辑代码核心是熟悉 heapq 或手写堆的下沉操作。import heapq def top_k(nums, k): heap nums[:k] heapq.heapify(heap) for num in nums[k:]: if num heap[0]: heapq.heapreplace(heap, num) return heap6.4 外部排序与归并思路的延伸当数据量大到无法全部加载到内存时外部排序是必经之路核心思路就是归并排序的分而治之大文件切分成多个有序的小文件再通过多路归并得到整体有序结果。虽然笔试不一定会直接考外部排序但归并排序的理解是基础尤其当面试官追问如果数据量超过内存怎么办时这个思路几乎是唯一答案。从第四范式业务角度看分布式计算框架中的 shuffle 阶段就包含了大量归并排序的变体。理解归并排序合并两个有序区间这个核心操作的复杂度与实现细节能帮助理解和优化分布式任务中的数据传输和排序开销。7. 图论与搜索从 KMP 联想到的更广泛算法版图7.1 二分图与 HK 算法复杂模型匹配问题热词中出现二分图 hk算法不是偶然这类图论算法在现实业务中有很强的映射场景比如在推荐系统中用户和物品天然构成二分图衡量用户与物品的匹配程度可以转化为最大匹配问题。Hopcroft-Karp 算法是求解二分图最大匹配的高效算法通过每次寻找多条增广路径并使用 BFS 分层和 DFS 增广把复杂度降低到 O(E sqrt(V))。笔试中如果考二分图直接考 HK 算法的概率不大但考匈牙利算法的概率较高。两者解决的问题相同只是优化手段不同。建议先掌握匈牙利算法的增广路径思想和代码模板再理解 HK 算法为什么通过 BFS 分层能加速多路匹配。7.2 Dijkstra 算法与最短路径的变体热词中出现dijkstra算法这也是各类公司算法笔试的高频考点。经典 Dijkstra 适用于单源正权图核心在于贪心选择当前距离最小的未访问节点通过优先队列实现 O((VE) log V)。笔试中容易出现的变体包括要求输出路径本身处理有负权边时如何通过 Bellman-Ford 或 SPFA 解决以及如何计算从起点到每个节点的最短路径条数。在第四范式的业务场景中物流路径优化、供应链网络分析、知识图谱中的关系路径查询等都与最短路径问题相关。虽然算法岗日常工作中更常用现成的图计算框架但理解底层算法原理有助于在框架性能调优时做出正确的索引和存储选择。7.3 拓扑排序与 Kahn 算法任务依赖关系建模Kahn 算法解决的是拓扑排序问题对有向无环图输出一种节点顺序使得对每条有向边 u - vu 都出现在 v 之前。算法核心是不断选取入度为 0 的节点删除其出边并更新相关节点入度。这个算法在工程调度和依赖关系分析中非常常见。比如在 AutoML 平台中一个完整的机器学习流水线可能包含数据清洗、特征工程、模型训练、模型评估、模型部署等多个阶段每个阶段之间存在依赖关系利用 Kahn 算法可以检测是否存在循环依赖并给出一个可执行的调度顺序。笔试中如果考到拓扑排序重点是把入度表、邻接表和队列的配合逻辑写对。7.4 KMP 与自动机思想的统一视角很多人把字符串算法和图论算法当成两个独立模块但从更高的抽象视角看KMP 的核心就是构造一个有限状态自动机模式串的每个匹配状态对应自动机的一个节点匹配失败时的回退就是自动机的状态转移。所以 KMP 本质上是一种特殊的 DFA 构建问题这就是为什么 KMP 问题的变体能自然延伸到 AC 自动机和后缀自动机。从笔试准备的角度我建议将所有图算法统一到状态-转移的思维框架下KMP 是线性序上的确定性自动机拓扑排序是偏序关系的线性展开Dijkstra 是加权有向图上的动态规划加贪心优化。这套统一的框架能让你在面对新题时不慌因为它把问题的本质归结为状态空间加转移规则的建模而不是死记硬背某个算法模板。8. 笔试之外从刷题到算法工程师思维的转变8.1 2020真题在今天依然有价值的三个原因很多人在刷真题时会问2020年的题目到今天还有参考价值吗我觉得有而且价值不低。第一字符串、动态规划、贪心、排序、图论这五大板块是所有算法岗笔试恒定的基本面变化的只是包装方式核心模型几十年都没变。第二第四范式的真题能反映出这家公司对候选人的期望——不仅要会解题还要能解释为什么这么解以及这个解法在业务中的对应物是什么。第三这套题目的难度和区分度设计得很合理前两题保证基础分第三题检验策略思维第四题拉开深度差距这种结构本身就是模板级的。8.2 刷题之外的隐性准备笔试除了做题还有一些隐性准备容易被忽略。比如编程环境的选择——多数在线笔试平台支持 Python 和 C但不同语言的输入输出模板和运行效率有差异。我个人建议提前熟悉目标公司的笔试平台了解是否需要自己处理多组测试用例的输入循环是否需要考虑大数溢出。另一个容易被忽略的点是代码风格。笔试虽然只看测试用例是否通过但少数情况下面试官会调阅你的笔试代码来了解你的编码习惯。变量命名清晰、函数边界明确、关键逻辑有简短注释这些细节会成为后续面试中印象分的组成部分。我见过有候选人笔试分数一样但面试时因为代码风格更专业而获得额外认可。8.3 时间分配策略笔试现场的取舍以第四范式这套题为例总时长大约 90 分钟到 120 分钟四道题的价值并不均等。前两题属于保分题建议控制在 20 分钟内完成并确保测试用例全部通过第三题如果思路清晰10 分钟内能搞定第四题作为开放题值得预留至少 30 分钟来组织一个结构完整的回答因为它的区分度最高。如果遇到卡壳的题切记不要死磕。先跳过做后面的题再回来补前面的题是笔试最基本的时间管理策略。卡壳常常是因为思维走进了死胡同跳出来换个角度再看往往能很快找到解法。8.4 从真题到真实业务能力算法岗的长期成长路径笔试只是算法岗的第一关真正决定职业发展的还是解决真实业务问题的能力。第四范式的业务场景对算法工程师有很高的复合要求既要有机器学习的建模能力又要有扎实的工程实现功底还要具备将业务问题转化为数学模型的抽象能力。这套笔试中的 KMP、贪心、损失函数选择这些题目表面上看是零散知识点背后其实都是这些核心能力的最小单元。作为过来人我强烈建议在准备笔试的同时有意识地做一件从题目到论文的延伸阅读。比如看到最大连续子数组和的问题就去了解一下在线凸优化的 regret bound 分析看到贪心区间调度就去了解一下任务调度问题在分布式系统中的变体。这种由点及面的学习方式才是把一次笔试准备转化为长期竞争力的关键。我自己在准备面试和带新人时发现一个规律那些笔试排名靠前的人并不是刷题量最多的人而是能把每道题背后的原理吃透并讲清楚的人。所以你在准备这套真题的时候不要只盯着答案是什么更要问自己为什么是这个答案以及如果场景变了这个答案还成立吗。带着这三个问题去刷完这四道题收获会远超一套题的预期。