春招笔试是最讲性价比的地方筛人快、题量大很多同学在简历上花的心思比准备笔试多得多结果笔试直接挂掉。去年我经历了2023年度小满春招算法岗第二批笔试这场考试基本把算法岗笔试的经典考点都覆盖了一遍从KMP的next数组到数据结构排序算法再到贪心、快速幂、堆排序、并查集最后还有机器学习方向的基础题。如果你正在准备算法岗春招或者暑期实习笔试这篇复盘值得好好看完我会把这场笔试背后的考点逻辑、题目拆解思路和踩过的坑一次性讲清楚。这篇内容不只适合马上要笔试的同学也适合想系统巩固算法基础的开发者因为很多经验和判断方法刷题软件里学不到。1. 小满春招算法岗第二批笔试题型分布与备考重点1.1 这场笔试到底考了什么小满这批笔试是春招第二波整体节奏比第一批明显更快。我印象里是限时180分钟选择题和填空题占40分左右编程题三道共60分另外还有一道机器学习方向的开放题计入总分。这个配置非常典型很多中大型公司算法岗笔试都爱这么干一半基础题筛基础一半编程题看代码能力最后还塞一道模型题看你有没有真做过训练。第一轮笔试看的是知识面广度第二轮看的就是深度。今年算法岗竞争比往年更卷笔试通过率大概只有20%不到所以不能抱侥幸心理。我这里凭印象整理一下题型分布选择题里字符串、排序、贪心、图论都有编程题两道偏传统算法一道偏工程模拟附加题则涉及变分推断和模型优化。整体看下来考察方向和搜索热词里高频出现的KMP算法、排序算法、贪心算法、动态规划、快速幂算法、并查集这些方向高度吻合。建议第一次参加算法岗笔试的同学先不要急着刷难题把这场笔试暴露出的考点矩阵列出来按优先级逐个击破。我后面会详细拆每类题的做题思路但首先你得知道算法岗笔试不是竞赛是筛选求稳比求快重要得多。1.2 考点分布与复习优先级排序我考完当天就把考过的知识点列了一张表对照着复盘复习重点这张表对你的备考规划应该也适用。考点出现形式优先级KMP算法next数组计算选择题、填空题高数据结构排序算法快排、堆排、归并等选择题、填空题高贪心算法编程题高动态规划编程题高快速幂、位运算编程题中并查集带权编程题中堆排序与优先队列编程题中机器学习基础KL散度、ELBO、过拟合附加题高算法岗粒子群、卡尔曼滤波等启发式算法开放题低视岗位方向而定从表格能看出来笔试不是刷题越多越好而是把高频考点覆盖掉再准备一块自己投递方向相关的知识。我当时复习的重心全放在数据结构和经典算法上机器学习只看了交叉熵和反向传播结果附加题考了ELBO推导直接给我整懵了。如果提前知道算法岗笔试必考这些考前一周抽一个晚上把公式推导过一遍至少能多拿十分。2. KMP的next数组和排序算法选择题里的高频考点2.1 next数组的两种定义笔试最容易翻车KMP算法几乎是算法岗笔试选择题的钉子户。这次考了一道题给了一个模式串 pabacaba问 next 数组是什么。我一开始看这题觉得很简单但后来和同场考的人对了答案发现大家的答案五花八门问题就出在题目对 next 数组的定义上。网上讲 KMP 的时候next 数组有两种主流定义。第一种是前缀函数也就是 pi[i] 表示 p[0..i] 这个子串的最长公共真前后缀长度。拿 abacaba 来算结果如下p[0..0] a最长公共前后缀长度为0p[0..1] ab前缀a和后缀b对不上是0p[0..2] aba前缀a等于后缀a是1p[0..3] abac前缀和后缀对不上是0p[0..4] abaca前缀a等于后缀a是1p[0..5] abacab前缀ab等于后缀ab是2p[0..6] abacaba前缀aba等于后缀aba是3所以前缀函数结果是 [0, 0, 1, 0, 1, 2, 3]。第二种是失配跳转数组很多教材里也直接叫 next 数组表示第 i 位失配时模式串指针应该跳回哪个位置通常定义为 next[0] -1next[i] pi[i-1]。这样算出来的结果是 [-1, 0, 0, 1, 0, 1, 2]。如果有的地方把 next[0] 初始化为0结果又会是 [0, 0, 0, 1, 0, 1, 2]。同样的字符串三种答案可能都有人写但只要题目有个括号说明next[i]定义为……答案就唯一了。我建议大家平时刷题时就练成习惯先圈出定义再动手算不要拿到题就默认自己熟悉的版本。2.2 排序算法速查表与稳定性记忆法排序算法这场笔试考得不算难但考得很细有两道选择题分别问哪个排序在最坏情况下时间复杂度是O(n²)和哪些排序是稳定的。这种题就是送分题只是很多人记混。我用一张速查表把主流排序捋一遍排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)左右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(nk)O(nk)O(k)稳定稳定性这块我自己总结过一个口诀稳定排序只有插归冒计基也就是插入、归并、冒泡、计数、基数其他常见排序基本都不稳定。笔试如果考选择题直接用这个口诀能省好多时间。另外注意快速排序虽然平均是 O(n log n)但最坏情况是 O(n²)当数组基本有序且选第一个元素作为基准时最容易触发。归并排序则稳定且最坏也是 O(n log n)代价是空间 O(n)。理解了这些区别选择题基本不会失分。2.3 贪心策略怎么判断“能不能贪”贪心算法这次出现在编程题里题型很经典是一道区间调度相关的题。很多同学遇到贪心就发怵主要是不知道什么时候可以用贪心什么时候要用动态规划。我的判断方法很简单如果每一步做一个局部最优的决策最终能得到全局最优并且能举出反例证伪那大概率可以贪。比如区间调度问题按结束时间排序就是典型的局部最优结束越早剩余可用时间越多能安排的区间数就越多。如果你按开始时间排序或者按区间长度排序很快就能举出反例所以那种排法不对。笔试时间紧张不太可能严格证明贪心正确性。我的建议是先用小规模数据在脑子里模拟一遍确认没有明显反例就直接写代码。如果心里没底就用暴力搜索跑几个随机小数据对比验证这也算是笔试里的一个实用技巧。贪心题写起来通常很快但前提是排序的依据想清楚这是整个题的核心。3. 笔试编程题拆解快速幂、并查集、DP和堆排序的实战思路3.1 快速幂从暴力循环到O(log n)的取模写法编程题第一道就是快速幂的变体要求算 a 的 b 次方对 m 取模的结果其中 b 的范围给到了 1e9 级别。如果没学过快速幂直接写个 for 循环对于大指数必然超时。快速幂的核心思想是把指数拆成二进制。比如 a^1313 的二进制是 1101所以 a^13 a^8 * a^4 * a^1。我们只要把底数不断平方同时判断当前二进制位是不是1决定要不要乘进结果就能把 O(b) 的复杂度降到 O(log b)。Python 写法很简洁def pow_mod(a, b, m): res 1 a % m while b 0: if b 1: res res * a % m a a * a % m b 1 return res这里有一个细节一定要提醒进入循环前要先a % m否则如果 m 很大第一步乘法就可能溢出。用 C 的同学更要小心a * a在 a 接近 1e9 时已经接近 1e18long long 还能扛住但如果题目给的 m 更大可能要用到快速乘或者 Python 的大整数这也是为什么很多算法岗笔试允许用 Python 时大家都会优先选 Python。3.2 带权并查集食物链类型题的标准解法第二道编程题的方向是并查集但考的不是普通连通性而是带权并查集也就是节点之间不仅有是不是同一集合的关系还有相对关系比如差值、倍数、方向等。这类题的经典原型是食物链问题考场上遇到的时候很多同学当场就卡住了。带权并查集和普通并查集相比多维护了一个权值数组 d[x]表示节点 x 到父节点的相对值。find 的时候除了路径压缩还要顺带更新 d[x]让 d[x] 最终表示 x 到根节点的相对值。union 的时候需要推导合并公式这是最容易写错的地方。我提供一个可以直接用的模板class WeightedUnionFind: def __init__(self, n): self.fa list(range(n)) self.d [0] * n def find(self, x): if self.fa[x] ! x: p self.fa[x] r self.find(p) self.d[x] self.d[p] self.fa[x] r return self.fa[x] def merge(self, x, y, w): # 表示 val[x] - val[y] w rx, ry self.find(x), self.find(y) if rx ry: return self.fa[rx] ry self.d[rx] self.d[y] - self.d[x] w这个公式怎么理解合并时我们希望把 rx 接到 ry 下面并且满足 val[x] - val[y] w。因为 find 之后有 val[x] d[x] val[rx]val[y] d[y] val[ry]代入等式一推d[rx] 就等于 d[y] - d[x] w。这里符号方向依赖于题目的定义有些题给的是差值有些给的是模3余数关系但模板结构是一样的。考场上遇到带权并查集不要慌先根据题意确定权值数组的物理含义再把 merge 的等式列出来最后套模板。如果时间不够也不建议放弃因为并查集本身代码量不大一旦写对整个题目的分都能拿到。3.3 动态规划状态设计的三步法第三道编程题更像是综合题考察动态规划数据范围区分度很明显。题目的细节我不方便透露太多但解题思路可以讲透。动态规划题在笔试里最怕的不是转移方程写不出来而是状态定义一开始就错了。我自己习惯用三步法第一步确认状态是什么。常见套路是dp[i]表示以 i 结尾的最优值或者dp[i][j]表示两个序列前 i 个和前 j 个之间的最优值。状态定义一定要包含所有会影响后续决策的信息。第二步从最后一步入手推转移方程。比如编辑距离问题dp[i][j]表示串A前 i 个字符变成串B前 j 个字符的最小编辑距离最后一步无非是增、删、改三种操作分别对应dp[i][j-1]1、dp[i-1][j]1、dp[i-1][j-1]cost取最小值就行。第三步确认初始化和遍历顺序。很多DP写错都是因为初始化不对或者遍历方向反了。这个在写代码之前就要想清楚不要编译报错后再去猜。如果题目数据范围达到 1e5O(n²) 的 DP 基本会被卡这个时候就要想优化。比如最长上升子序列O(n²) 可以写但 1e5 的数据必须用贪心加二分维护 tails 数组tails[k]表示长度为 k1 的上升子序列末尾元素的最小值。import bisect def length_of_lis(nums): tails [] for x in nums: idx bisect.bisect_left(tails, x) if idx len(tails): tails.append(x) else: tails[idx] x return len(tails)DP题不是看会的是真的要动手推、动手写。考前建议把最长上升子序列、最长公共子序列、编辑距离、背包问题、区间DP、树形DP这六类经典题各练五道以上笔试遇到基本都能套上。3.4 堆排序与优先队列TopK 和二分答案的配合后面还有一道编程题考到了堆结合了 TopK 和二分答案。题目大意是给一个数组要求做若干次合并操作每次取最大的两个数合并类似哈夫曼的思路问最终的最小代价。这类题最自然的解法就是用优先队列堆。为什么用堆因为我们需要动态维护一组数据中的最大值或最小值每次操作只改变少数几个元素。如果用有序数组插入是 O(n) 的用堆插入和弹出都是 O(log n)整体复杂度能压到 O(n log n)。Python 里直接用heapq模块但要注意默认是小根堆想取最大值就把元素取负号放进去。代码大概是import heapq def min_cost(nums): heap [-x for x in nums] heapq.heapify(heap) cost 0 while len(heap) 1: a -heapq.heappop(heap) b -heapq.heappop(heap) cost a b heapq.heappush(heap, -(a b)) return cost除了这类合并题堆在找第K大元素里也很常见维护一个大小为 K 的小根堆遍历数组时如果新元素比堆顶大就弹出堆顶、插入新元素最后堆顶就是第K大。这样做时间复杂度 O(n log K)空间 O(K)适合海量数据场景。还有一种高频组合是二分答案加贪心题目问最小化最大值或最大化最小值时先写一个判断函数判断某个 limit 是否可行然后二分查找答案。比如把数组分成 m 段让每段和的最大值最小判断函数就用贪心去切段def can_split(nums, m, limit): cnt 1 cur 0 for x in nums: if cur x limit: cnt 1 cur x if cnt m: return False else: cur x return True def split_array(nums, m): lo, hi max(nums), sum(nums) while lo hi: mid (lo hi) // 2 if can_split(nums, m, mid): hi mid else: lo mid 1 return lo这个技巧很值得掌握因为很多看着像DP的题目用二分答案贪心判断反而更简单而且代码不容易写错。笔试时如果你感觉 DP 转移不好推先试着往二分答案方向想一下很多时候会有惊喜。4. 机器学习附加题算法岗笔试的隐藏分4.1 KL散度与ELBO变分推断的基础推导附加题里有一道和变分推断相关关键词就是最近搜索热词里频繁出现的KL散度和ELBO。这道题放在算法岗笔试里非常合理因为现在做搜索、推荐、广告、生成模型的算法工程师多少都会接触到变分自编码器或者扩散模型的训练目标。先把核心公式摆出来。假设真实后验 p(z|x) 不好算我们用 q(z) 去逼近它。KL散度的定义是KL(q(z) || p(z|x)) ∫ q(z) log (q(z) / p(z|x)) dz两边同时加上 log p(x)经过一步简单的变换可以写成log p(x) ELBO KL(q(z) || p(z|x))其中 ELBO 的完整形式是ELBO E_{q(z)}[log p(x, z)] - E_{q(z)}[log q(z)]为什么需要 ELBO因为 log p(x) 是证据但直接算 KL(q(z) || p(z|x)) 需要知道真实后验 p(z|x)这本来就是算不出来的。而 ELBO 只依赖联合分布 p(x, z) 和 q(z)这两者都是可计算的。由于 KL 散度非负ELBO 是 log p(x) 的下界所以最大化 ELBO 就是在间接最小化 KL 散度让 q(z) 尽量贴近真实后验。变分自编码器的损失函数本质上就是负的 ELBO重构项加 KL 正则项。笔试答这道题时不用写多长的推导但一定要把ELBO是证据下界和最大化ELBO等价于最小化KL散度这两句核心说清楚再写一下公式基本就能拿分。4.2 过拟合、正则化与优化器选择附加题后半部分考的是模型训练常识都是选择题题目不难但覆盖面很广。我记得有训练损失下降但验证损失上升说明什么这是典型的过拟合还有 L1 正则和 L2 正则的区别以及 Adam 和 SGD 的对比。这类题要想拿分核心理解几个点过拟合的典型表现是训练集指标好、验证集指标差解决手段有增加数据、降低模型复杂度、加正则化、加 Dropout、早停等。L1 正则化能让一部分权重变成0产生稀疏解适合做特征选择L2 正则化把权重压向0但不至于为0对离群点更平滑。Adam 自适应学习率、收敛快、对学习率不敏感适合快速试错SGD 加 Momentum 在某些任务上泛化性更好但调参成本更高。现在大模型预训练里也常用 AdamW这是 Adam 的改进版很多笔试会作为加分项问到知道就好。还有梯度消失和梯度爆炸简单说就是网络层数深了之后梯度连乘导致太小或太大。解决方案包括BatchNorm、残差连接、梯度裁剪、合理的激活函数选择等。4.3 方向性开放题粒子群、卡尔曼滤波等扩展考点最后一道附加题给了几个方向性的话题其中包括粒子群算法、模拟退火、卡尔曼滤波、PID控制等但不需要全答选一个你熟悉的展开就行。这类题明显是为不同方向的算法岗位准备的比如你做控制或自动驾驶方向可能就选卡尔曼滤波或PID你做优化方向就选粒子群或模拟退火。我当时选了粒子群算法因为之前做过一个参数调优的小项目。回答时我讲了粒子群的核心思想每个解是一只粒子有位置和速度不断向个体历史最优和群体历史最优移动通过惯性权重、认知系数、社会系数三个参数来控制搜索行为。这种题不要求你把公式背得一字不差但一定得能说清楚这个算法解决什么问题、为什么有效、主要参数有哪些、和梯度类优化方法相比优缺点是什么。如果你投的算法岗偏传统优化考前最好把粒子群、模拟退火、遗传算法、蚁群算法这些启发式算法的思路过一遍每个算法准备一段两分钟能讲完的总结笔试和面试都能用上。5. 考后三天我在复盘什么翻车点与笔试避坑清单5.1 我在这场笔试里翻过的三个车第一KMP next 数组定义没看仔细。我把题目里的 next[i] 按前缀函数来算但题目给的其实是失配跳转版本结果答案完全对不上。复盘时发现选择题题干里明明写了next[i] 定义为失配时跳转的位置只是我一看是 KMP 就条件反射用了自己最熟的版本。这个教训太深刻了以后拿到题先找括号里的定义再动笔。第二快速幂的输入取模。我第一遍写的时候忘了a % m自己造了一个 m 很大、a 也很大的测试数据计算过程直接溢出后面修了半天。小细节决定成败这种错误在笔试中非常可惜因为思路完全正确只是少了最前面那一行。第三带权并查集的合并公式符号写反了。我当时想着d[rx] d[x] d[y] w结果样例一直过不去。后来冷静下来按合并后要满足 val[x] - val[y] w这个条件重新推了一遍才改对。所以带权并查集一定要把等量关系写清楚不要凭记忆背公式我上面那个模板是用 val[x] - val[y] w 的方向如果题目方向相反记得把 w 的符号换一下。5.2 时间分配与代码风格的自检清单这次笔试我最庆幸的是提前规划了时间不然附加题根本没时间写。我的时间分配大概是选择题和填空题控制在35分钟以内不会的先标记跳过别恋战编程题每题留30到40分钟按自己最熟练的题先做的顺序排序最后留20分钟给机器学习附加题和整体检查。代码风格方面笔试环境通常不能运行调试所以代码必须一遍写对。我给自己定的自检清单是变量名用有意义的名字不要写 a、b、c 满天飞循环边界写之前先想清楚是 n还是 n所有数组下标从0开始还是从1开始全程保持一致涉及取模的地方检查每一步是否都取模了写完在脑子里跑一个最小样例、一个空样例、一个边界样例。尤其要注意评测机的边界条件比如数组长度为0、n等于1、数据量达到上限的情况。很多时候不是思路错是边界没处理完。5.3 后续备考我调整了什么考完这次笔试我把后面的复习计划重新排了一版重点从刷题量转向知识结构化。第一高频考点做专项整理。字符串、排序、贪心、DP、图论、并查集、快速幂每个方向整理出一页A4纸的笔记包含典型题型、核心公式、易错点。比如把KMP的前缀函数和失配数组两种定义分别列出来下次再遇到直接对号入座。第二每天限时做两道编程题严格按笔试节奏来一道题最多40分钟超时就去看题解然后复盘。不要再一题磨一小时考场上根本不允许。第三机器学习基础公式全部手推一遍。KL散度、ELBO、交叉熵、SVM对偶、朴素贝叶斯、逻辑回归的损失函数这些都是算法岗笔试和面试反复出现的内容。只记住结论不够必须能自己推出来。第四每周做一次模拟笔试。用往年真题或者热门题库里的混合套题按真实笔试的时间和题量来训练自己在限时环境下的心态和策略。模拟笔试最大的价值不是押题而是让你知道每类题应该花多少时间遇到不会的题能不能果断跳过。如果你也在准备算法岗笔试我最大的体会就一句话别把时间浪费在刷偏题怪题上把KMP、排序、贪心、DP、并查集、快速幂这些常客练到条件反射机器学习的基础公式能自己推一遍笔试基本就稳了。最后再分享一个小技巧考试时把题目里的数据范围圈出来再决定用什么算法这个习惯能帮你避开很多复杂度超纲的隐患。后面如果有二面、三面的经历我再回来继续写。
春招笔试是最讲性价比的地方筛人快、题量大很多同学在简历上花的心思比准备笔试多得多结果笔试直接挂掉。去年我经历了2023年度小满春招算法岗第二批笔试这场考试基本把算法岗笔试的经典考点都覆盖了一遍从KMP的next数组到数据结构排序算法再到贪心、快速幂、堆排序、并查集最后还有机器学习方向的基础题。如果你正在准备算法岗春招或者暑期实习笔试这篇复盘值得好好看完我会把这场笔试背后的考点逻辑、题目拆解思路和踩过的坑一次性讲清楚。这篇内容不只适合马上要笔试的同学也适合想系统巩固算法基础的开发者因为很多经验和判断方法刷题软件里学不到。1. 小满春招算法岗第二批笔试题型分布与备考重点1.1 这场笔试到底考了什么小满这批笔试是春招第二波整体节奏比第一批明显更快。我印象里是限时180分钟选择题和填空题占40分左右编程题三道共60分另外还有一道机器学习方向的开放题计入总分。这个配置非常典型很多中大型公司算法岗笔试都爱这么干一半基础题筛基础一半编程题看代码能力最后还塞一道模型题看你有没有真做过训练。第一轮笔试看的是知识面广度第二轮看的就是深度。今年算法岗竞争比往年更卷笔试通过率大概只有20%不到所以不能抱侥幸心理。我这里凭印象整理一下题型分布选择题里字符串、排序、贪心、图论都有编程题两道偏传统算法一道偏工程模拟附加题则涉及变分推断和模型优化。整体看下来考察方向和搜索热词里高频出现的KMP算法、排序算法、贪心算法、动态规划、快速幂算法、并查集这些方向高度吻合。建议第一次参加算法岗笔试的同学先不要急着刷难题把这场笔试暴露出的考点矩阵列出来按优先级逐个击破。我后面会详细拆每类题的做题思路但首先你得知道算法岗笔试不是竞赛是筛选求稳比求快重要得多。1.2 考点分布与复习优先级排序我考完当天就把考过的知识点列了一张表对照着复盘复习重点这张表对你的备考规划应该也适用。考点出现形式优先级KMP算法next数组计算选择题、填空题高数据结构排序算法快排、堆排、归并等选择题、填空题高贪心算法编程题高动态规划编程题高快速幂、位运算编程题中并查集带权编程题中堆排序与优先队列编程题中机器学习基础KL散度、ELBO、过拟合附加题高算法岗粒子群、卡尔曼滤波等启发式算法开放题低视岗位方向而定从表格能看出来笔试不是刷题越多越好而是把高频考点覆盖掉再准备一块自己投递方向相关的知识。我当时复习的重心全放在数据结构和经典算法上机器学习只看了交叉熵和反向传播结果附加题考了ELBO推导直接给我整懵了。如果提前知道算法岗笔试必考这些考前一周抽一个晚上把公式推导过一遍至少能多拿十分。2. KMP的next数组和排序算法选择题里的高频考点2.1 next数组的两种定义笔试最容易翻车KMP算法几乎是算法岗笔试选择题的钉子户。这次考了一道题给了一个模式串 pabacaba问 next 数组是什么。我一开始看这题觉得很简单但后来和同场考的人对了答案发现大家的答案五花八门问题就出在题目对 next 数组的定义上。网上讲 KMP 的时候next 数组有两种主流定义。第一种是前缀函数也就是 pi[i] 表示 p[0..i] 这个子串的最长公共真前后缀长度。拿 abacaba 来算结果如下p[0..0] a最长公共前后缀长度为0p[0..1] ab前缀a和后缀b对不上是0p[0..2] aba前缀a等于后缀a是1p[0..3] abac前缀和后缀对不上是0p[0..4] abaca前缀a等于后缀a是1p[0..5] abacab前缀ab等于后缀ab是2p[0..6] abacaba前缀aba等于后缀aba是3所以前缀函数结果是 [0, 0, 1, 0, 1, 2, 3]。第二种是失配跳转数组很多教材里也直接叫 next 数组表示第 i 位失配时模式串指针应该跳回哪个位置通常定义为 next[0] -1next[i] pi[i-1]。这样算出来的结果是 [-1, 0, 0, 1, 0, 1, 2]。如果有的地方把 next[0] 初始化为0结果又会是 [0, 0, 0, 1, 0, 1, 2]。同样的字符串三种答案可能都有人写但只要题目有个括号说明next[i]定义为……答案就唯一了。我建议大家平时刷题时就练成习惯先圈出定义再动手算不要拿到题就默认自己熟悉的版本。2.2 排序算法速查表与稳定性记忆法排序算法这场笔试考得不算难但考得很细有两道选择题分别问哪个排序在最坏情况下时间复杂度是O(n²)和哪些排序是稳定的。这种题就是送分题只是很多人记混。我用一张速查表把主流排序捋一遍排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)左右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(nk)O(nk)O(k)稳定稳定性这块我自己总结过一个口诀稳定排序只有插归冒计基也就是插入、归并、冒泡、计数、基数其他常见排序基本都不稳定。笔试如果考选择题直接用这个口诀能省好多时间。另外注意快速排序虽然平均是 O(n log n)但最坏情况是 O(n²)当数组基本有序且选第一个元素作为基准时最容易触发。归并排序则稳定且最坏也是 O(n log n)代价是空间 O(n)。理解了这些区别选择题基本不会失分。2.3 贪心策略怎么判断“能不能贪”贪心算法这次出现在编程题里题型很经典是一道区间调度相关的题。很多同学遇到贪心就发怵主要是不知道什么时候可以用贪心什么时候要用动态规划。我的判断方法很简单如果每一步做一个局部最优的决策最终能得到全局最优并且能举出反例证伪那大概率可以贪。比如区间调度问题按结束时间排序就是典型的局部最优结束越早剩余可用时间越多能安排的区间数就越多。如果你按开始时间排序或者按区间长度排序很快就能举出反例所以那种排法不对。笔试时间紧张不太可能严格证明贪心正确性。我的建议是先用小规模数据在脑子里模拟一遍确认没有明显反例就直接写代码。如果心里没底就用暴力搜索跑几个随机小数据对比验证这也算是笔试里的一个实用技巧。贪心题写起来通常很快但前提是排序的依据想清楚这是整个题的核心。3. 笔试编程题拆解快速幂、并查集、DP和堆排序的实战思路3.1 快速幂从暴力循环到O(log n)的取模写法编程题第一道就是快速幂的变体要求算 a 的 b 次方对 m 取模的结果其中 b 的范围给到了 1e9 级别。如果没学过快速幂直接写个 for 循环对于大指数必然超时。快速幂的核心思想是把指数拆成二进制。比如 a^1313 的二进制是 1101所以 a^13 a^8 * a^4 * a^1。我们只要把底数不断平方同时判断当前二进制位是不是1决定要不要乘进结果就能把 O(b) 的复杂度降到 O(log b)。Python 写法很简洁def pow_mod(a, b, m): res 1 a % m while b 0: if b 1: res res * a % m a a * a % m b 1 return res这里有一个细节一定要提醒进入循环前要先a % m否则如果 m 很大第一步乘法就可能溢出。用 C 的同学更要小心a * a在 a 接近 1e9 时已经接近 1e18long long 还能扛住但如果题目给的 m 更大可能要用到快速乘或者 Python 的大整数这也是为什么很多算法岗笔试允许用 Python 时大家都会优先选 Python。3.2 带权并查集食物链类型题的标准解法第二道编程题的方向是并查集但考的不是普通连通性而是带权并查集也就是节点之间不仅有是不是同一集合的关系还有相对关系比如差值、倍数、方向等。这类题的经典原型是食物链问题考场上遇到的时候很多同学当场就卡住了。带权并查集和普通并查集相比多维护了一个权值数组 d[x]表示节点 x 到父节点的相对值。find 的时候除了路径压缩还要顺带更新 d[x]让 d[x] 最终表示 x 到根节点的相对值。union 的时候需要推导合并公式这是最容易写错的地方。我提供一个可以直接用的模板class WeightedUnionFind: def __init__(self, n): self.fa list(range(n)) self.d [0] * n def find(self, x): if self.fa[x] ! x: p self.fa[x] r self.find(p) self.d[x] self.d[p] self.fa[x] r return self.fa[x] def merge(self, x, y, w): # 表示 val[x] - val[y] w rx, ry self.find(x), self.find(y) if rx ry: return self.fa[rx] ry self.d[rx] self.d[y] - self.d[x] w这个公式怎么理解合并时我们希望把 rx 接到 ry 下面并且满足 val[x] - val[y] w。因为 find 之后有 val[x] d[x] val[rx]val[y] d[y] val[ry]代入等式一推d[rx] 就等于 d[y] - d[x] w。这里符号方向依赖于题目的定义有些题给的是差值有些给的是模3余数关系但模板结构是一样的。考场上遇到带权并查集不要慌先根据题意确定权值数组的物理含义再把 merge 的等式列出来最后套模板。如果时间不够也不建议放弃因为并查集本身代码量不大一旦写对整个题目的分都能拿到。3.3 动态规划状态设计的三步法第三道编程题更像是综合题考察动态规划数据范围区分度很明显。题目的细节我不方便透露太多但解题思路可以讲透。动态规划题在笔试里最怕的不是转移方程写不出来而是状态定义一开始就错了。我自己习惯用三步法第一步确认状态是什么。常见套路是dp[i]表示以 i 结尾的最优值或者dp[i][j]表示两个序列前 i 个和前 j 个之间的最优值。状态定义一定要包含所有会影响后续决策的信息。第二步从最后一步入手推转移方程。比如编辑距离问题dp[i][j]表示串A前 i 个字符变成串B前 j 个字符的最小编辑距离最后一步无非是增、删、改三种操作分别对应dp[i][j-1]1、dp[i-1][j]1、dp[i-1][j-1]cost取最小值就行。第三步确认初始化和遍历顺序。很多DP写错都是因为初始化不对或者遍历方向反了。这个在写代码之前就要想清楚不要编译报错后再去猜。如果题目数据范围达到 1e5O(n²) 的 DP 基本会被卡这个时候就要想优化。比如最长上升子序列O(n²) 可以写但 1e5 的数据必须用贪心加二分维护 tails 数组tails[k]表示长度为 k1 的上升子序列末尾元素的最小值。import bisect def length_of_lis(nums): tails [] for x in nums: idx bisect.bisect_left(tails, x) if idx len(tails): tails.append(x) else: tails[idx] x return len(tails)DP题不是看会的是真的要动手推、动手写。考前建议把最长上升子序列、最长公共子序列、编辑距离、背包问题、区间DP、树形DP这六类经典题各练五道以上笔试遇到基本都能套上。3.4 堆排序与优先队列TopK 和二分答案的配合后面还有一道编程题考到了堆结合了 TopK 和二分答案。题目大意是给一个数组要求做若干次合并操作每次取最大的两个数合并类似哈夫曼的思路问最终的最小代价。这类题最自然的解法就是用优先队列堆。为什么用堆因为我们需要动态维护一组数据中的最大值或最小值每次操作只改变少数几个元素。如果用有序数组插入是 O(n) 的用堆插入和弹出都是 O(log n)整体复杂度能压到 O(n log n)。Python 里直接用heapq模块但要注意默认是小根堆想取最大值就把元素取负号放进去。代码大概是import heapq def min_cost(nums): heap [-x for x in nums] heapq.heapify(heap) cost 0 while len(heap) 1: a -heapq.heappop(heap) b -heapq.heappop(heap) cost a b heapq.heappush(heap, -(a b)) return cost除了这类合并题堆在找第K大元素里也很常见维护一个大小为 K 的小根堆遍历数组时如果新元素比堆顶大就弹出堆顶、插入新元素最后堆顶就是第K大。这样做时间复杂度 O(n log K)空间 O(K)适合海量数据场景。还有一种高频组合是二分答案加贪心题目问最小化最大值或最大化最小值时先写一个判断函数判断某个 limit 是否可行然后二分查找答案。比如把数组分成 m 段让每段和的最大值最小判断函数就用贪心去切段def can_split(nums, m, limit): cnt 1 cur 0 for x in nums: if cur x limit: cnt 1 cur x if cnt m: return False else: cur x return True def split_array(nums, m): lo, hi max(nums), sum(nums) while lo hi: mid (lo hi) // 2 if can_split(nums, m, mid): hi mid else: lo mid 1 return lo这个技巧很值得掌握因为很多看着像DP的题目用二分答案贪心判断反而更简单而且代码不容易写错。笔试时如果你感觉 DP 转移不好推先试着往二分答案方向想一下很多时候会有惊喜。4. 机器学习附加题算法岗笔试的隐藏分4.1 KL散度与ELBO变分推断的基础推导附加题里有一道和变分推断相关关键词就是最近搜索热词里频繁出现的KL散度和ELBO。这道题放在算法岗笔试里非常合理因为现在做搜索、推荐、广告、生成模型的算法工程师多少都会接触到变分自编码器或者扩散模型的训练目标。先把核心公式摆出来。假设真实后验 p(z|x) 不好算我们用 q(z) 去逼近它。KL散度的定义是KL(q(z) || p(z|x)) ∫ q(z) log (q(z) / p(z|x)) dz两边同时加上 log p(x)经过一步简单的变换可以写成log p(x) ELBO KL(q(z) || p(z|x))其中 ELBO 的完整形式是ELBO E_{q(z)}[log p(x, z)] - E_{q(z)}[log q(z)]为什么需要 ELBO因为 log p(x) 是证据但直接算 KL(q(z) || p(z|x)) 需要知道真实后验 p(z|x)这本来就是算不出来的。而 ELBO 只依赖联合分布 p(x, z) 和 q(z)这两者都是可计算的。由于 KL 散度非负ELBO 是 log p(x) 的下界所以最大化 ELBO 就是在间接最小化 KL 散度让 q(z) 尽量贴近真实后验。变分自编码器的损失函数本质上就是负的 ELBO重构项加 KL 正则项。笔试答这道题时不用写多长的推导但一定要把ELBO是证据下界和最大化ELBO等价于最小化KL散度这两句核心说清楚再写一下公式基本就能拿分。4.2 过拟合、正则化与优化器选择附加题后半部分考的是模型训练常识都是选择题题目不难但覆盖面很广。我记得有训练损失下降但验证损失上升说明什么这是典型的过拟合还有 L1 正则和 L2 正则的区别以及 Adam 和 SGD 的对比。这类题要想拿分核心理解几个点过拟合的典型表现是训练集指标好、验证集指标差解决手段有增加数据、降低模型复杂度、加正则化、加 Dropout、早停等。L1 正则化能让一部分权重变成0产生稀疏解适合做特征选择L2 正则化把权重压向0但不至于为0对离群点更平滑。Adam 自适应学习率、收敛快、对学习率不敏感适合快速试错SGD 加 Momentum 在某些任务上泛化性更好但调参成本更高。现在大模型预训练里也常用 AdamW这是 Adam 的改进版很多笔试会作为加分项问到知道就好。还有梯度消失和梯度爆炸简单说就是网络层数深了之后梯度连乘导致太小或太大。解决方案包括BatchNorm、残差连接、梯度裁剪、合理的激活函数选择等。4.3 方向性开放题粒子群、卡尔曼滤波等扩展考点最后一道附加题给了几个方向性的话题其中包括粒子群算法、模拟退火、卡尔曼滤波、PID控制等但不需要全答选一个你熟悉的展开就行。这类题明显是为不同方向的算法岗位准备的比如你做控制或自动驾驶方向可能就选卡尔曼滤波或PID你做优化方向就选粒子群或模拟退火。我当时选了粒子群算法因为之前做过一个参数调优的小项目。回答时我讲了粒子群的核心思想每个解是一只粒子有位置和速度不断向个体历史最优和群体历史最优移动通过惯性权重、认知系数、社会系数三个参数来控制搜索行为。这种题不要求你把公式背得一字不差但一定得能说清楚这个算法解决什么问题、为什么有效、主要参数有哪些、和梯度类优化方法相比优缺点是什么。如果你投的算法岗偏传统优化考前最好把粒子群、模拟退火、遗传算法、蚁群算法这些启发式算法的思路过一遍每个算法准备一段两分钟能讲完的总结笔试和面试都能用上。5. 考后三天我在复盘什么翻车点与笔试避坑清单5.1 我在这场笔试里翻过的三个车第一KMP next 数组定义没看仔细。我把题目里的 next[i] 按前缀函数来算但题目给的其实是失配跳转版本结果答案完全对不上。复盘时发现选择题题干里明明写了next[i] 定义为失配时跳转的位置只是我一看是 KMP 就条件反射用了自己最熟的版本。这个教训太深刻了以后拿到题先找括号里的定义再动笔。第二快速幂的输入取模。我第一遍写的时候忘了a % m自己造了一个 m 很大、a 也很大的测试数据计算过程直接溢出后面修了半天。小细节决定成败这种错误在笔试中非常可惜因为思路完全正确只是少了最前面那一行。第三带权并查集的合并公式符号写反了。我当时想着d[rx] d[x] d[y] w结果样例一直过不去。后来冷静下来按合并后要满足 val[x] - val[y] w这个条件重新推了一遍才改对。所以带权并查集一定要把等量关系写清楚不要凭记忆背公式我上面那个模板是用 val[x] - val[y] w 的方向如果题目方向相反记得把 w 的符号换一下。5.2 时间分配与代码风格的自检清单这次笔试我最庆幸的是提前规划了时间不然附加题根本没时间写。我的时间分配大概是选择题和填空题控制在35分钟以内不会的先标记跳过别恋战编程题每题留30到40分钟按自己最熟练的题先做的顺序排序最后留20分钟给机器学习附加题和整体检查。代码风格方面笔试环境通常不能运行调试所以代码必须一遍写对。我给自己定的自检清单是变量名用有意义的名字不要写 a、b、c 满天飞循环边界写之前先想清楚是 n还是 n所有数组下标从0开始还是从1开始全程保持一致涉及取模的地方检查每一步是否都取模了写完在脑子里跑一个最小样例、一个空样例、一个边界样例。尤其要注意评测机的边界条件比如数组长度为0、n等于1、数据量达到上限的情况。很多时候不是思路错是边界没处理完。5.3 后续备考我调整了什么考完这次笔试我把后面的复习计划重新排了一版重点从刷题量转向知识结构化。第一高频考点做专项整理。字符串、排序、贪心、DP、图论、并查集、快速幂每个方向整理出一页A4纸的笔记包含典型题型、核心公式、易错点。比如把KMP的前缀函数和失配数组两种定义分别列出来下次再遇到直接对号入座。第二每天限时做两道编程题严格按笔试节奏来一道题最多40分钟超时就去看题解然后复盘。不要再一题磨一小时考场上根本不允许。第三机器学习基础公式全部手推一遍。KL散度、ELBO、交叉熵、SVM对偶、朴素贝叶斯、逻辑回归的损失函数这些都是算法岗笔试和面试反复出现的内容。只记住结论不够必须能自己推出来。第四每周做一次模拟笔试。用往年真题或者热门题库里的混合套题按真实笔试的时间和题量来训练自己在限时环境下的心态和策略。模拟笔试最大的价值不是押题而是让你知道每类题应该花多少时间遇到不会的题能不能果断跳过。如果你也在准备算法岗笔试我最大的体会就一句话别把时间浪费在刷偏题怪题上把KMP、排序、贪心、DP、并查集、快速幂这些常客练到条件反射机器学习的基础公式能自己推一遍笔试基本就稳了。最后再分享一个小技巧考试时把题目里的数据范围圈出来再决定用什么算法这个习惯能帮你避开很多复杂度超纲的隐患。后面如果有二面、三面的经历我再回来继续写。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
