每年八月底到十月初是校招笔试最密集的一波时间段。我当时白天投简历、晚上刷题手机里塞满了各家公司的笔试通知很多题目做完就忘但爱奇艺2018年秋季校招算法工程师的第三场笔试我到现在还记得不少细节。一是因为那场题目的覆盖面确实广从KMP这种经典字符串算法一路考到卡尔曼滤波、PID控制这种偏工程方向的内容二是因为那场笔试让我第一次意识到视频平台算法岗的考察思路和纯互联网公司不太一样它更重视“算法怎么在具体业务里落地”这件事。这篇文章相当于我对那场笔试的一次完整复盘从题型分布、具体考点到编程题的建模思路都会聊到。如果你正在准备算法岗校招或者对视频网站算法团队到底考什么感兴趣应该能从里面找到一些有用的东西。很多题目细节时隔数年我已经记不全但考点和当时的解题思路是清楚的我会尽量把能还原的部分都写出来。1. 第三场笔试的试卷印象题型分布与答题节奏1.1 投递与笔试安排爱奇艺当年的秋招启动得挺早算法工程师岗位分了好几场笔试我参加的是第三场。当时选择投爱奇艺主要是看中它的业务场景——视频推荐、搜索排序、内容理解、广告CTR预估这些方向都依赖算法模型而且数据量非常大对于一个刚准备入行的算法工程师来说是很好的成长环境。笔试是纯在线形式两道大题中间不设休息整场大概两个半小时。我记得当时为了保证网络稳定特意跑到学校图书馆的独立自习室去考还把手机调成了勿扰模式。现在回想起来这些准备工作其实挺重要的在线笔试最怕中途断网或者被电话打断心态一旦崩了后面做题节奏全乱。1.2 题型构成与做题节奏第三场的题型大致分四块单选题、多选题、编程题和简答题。单多选覆盖的范围很杂从数据结构、算法复杂度到机器学习基础都有涉及编程题有两道一道偏字符串处理一道偏搜索与博弈简答题则是给一个业务场景让你设计算法方案。我的做题策略是先把所有题目快速扫一遍给每道题估一个时间上限。选择题如果30秒内没有思路就先标记跳过等编程题写完再回头琢磨。这个策略后来证明是对的——因为编程题往往需要完整的思考时间如果前面在选择题上犹豫太久后面很容易仓促提交。我记得那场笔试的选择题里至少有三道是我第一遍不会做、最后回来检查时才想明白的可见第一遍扫题的策略有多重要。2. 基础算法题复盘KMP的next数组、排序与贪心2.1 KMP的next数组推导全过程那场笔试的选择题里有一道关于KMP算法的题给的是模式串 p abacaba让求 next 数组。题目里明确写了 next[i] 的定义但在不同教材里 next 数组的定义其实有细微差别有的代表“当前位置失配后跳转的位置”有的代表“最长相等真前后缀的长度”。我当年备考时就被这个定义坑过所以看到题目时特地留意了一下题目给的定义。按最长相等真前后缀长度这一版定义来推导过程是这样下标 i子串 p[0..i]最长相等真前后缀next[i]0a无01ab无02abaa13abac无04abacaa15abacabab26abacabaaba3所以 next 数组是 [0, 0, 1, 0, 1, 2, 3]。我当时在草稿纸上按顺序推了一遍确认这个结果无误后才选的答案。这道题给我的启发是KMP 的核心理解不能停留在“会调用库函数”而是要能手动推导 next 数组。能做到这一步说明对最长相等真前后缀这个概念是真的理解了而不是死记硬背代码模板。当时的代码模板是长这样的def build_next(p): n len(p) nxt [0] * n j 0 for i in range(1, n): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt如果你平时用的是 next[i] 表示失配时跳到 next[i] 位置 那一版定义本质上和这个版本是一致的只是数组整体做了位移和减一。做题时一定要先看题目定义别上来就套自己背的模板这是KMP题最容易翻车的地方。2.2 排序算法复杂度与稳定性对照选择题里还有一道是给出一组排序算法问哪些是稳定的、哪些平均时间复杂度是 O(n log n)。这种题属于送分题但也是最容易记混的因为排序算法太多稳定性和复杂度交叉在一起如果平时没有整理过考场上很容易记错。我当时是这么记的稳定的排序算法有冒泡、插入、归并、计数、基数、桶排序不稳定的有选择、快排、堆排、希尔排序。平均时间复杂度 O(n log n) 的有快排、归并、堆排。结合起来看同时满足稳定和平均 O(n log n)的只有归并排序。排序算法平均时间复杂度最坏时间复杂度稳定性冒泡排序O(n^2)O(n^2)稳定插入排序O(n^2)O(n^2)稳定选择排序O(n^2)O(n^2)不稳定快速排序O(n log n)O(n^2)不稳定归并排序O(n log n)O(n log n)稳定堆排序O(n log n)O(n log n)不稳定这样一张表整理出来考场上几乎不需要思考直接对照选就行。我后来准备面试时也一直用这种整理方式把容易混淆的知识点做成对照表考前扫一遍比反复刷题效率高很多。2.3 贪心与图论的选择题陷阱还有几道选择题涉及贪心算法和图论。贪心那边考的是判断一个经典问题能否用贪心解决比如活动选择问题、哈夫曼编码、最小生成树里的Prim和Kruskal。关键是理解贪心的前提局部最优能推出全局最优且无后效性。Kruskal算法按边权从小到大依次选边能形成最小生成树这是因为最小生成树问题满足贪心选择性而像0-1背包这样的问题就不满足所以不能用贪心。图论那边考了Dijkstra算法和拓扑排序。Dijkstra有一个大坑是不能处理负权边因为它是基于当前距离最小的节点不会再被更新这个假设的一旦出现负权边这个假设就失效了。Kahn算法求拓扑排序则是考了入度数组的操作我当时选择题里遇到的是在Kahn算法中队列初始应该放入哪些节点答案是所有入度为0的节点。这些都是非常基础的考点但如果平时只看代码不理解了原理考场上很容易被选项里的迷惑项带偏。3. 机器学习与深度学习考点内容平台算法岗的必修课3.1 聚类与KNN的考点爱奇艺作为视频内容平台算法工程师的日常工作离不开用户行为分析和内容理解所以笔试里机器学习基础占比不低这也是意料之中的。选择题里有一道关于K-Means与DBSCAN的对比。K-Means需要提前指定簇数K对初始中心点敏感适合凸形簇DBSCAN是密度聚类不需要指定簇数可以发现任意形状的簇还能自动识别噪声点。我当年刚准备校招时对DBSCAN的理解停留在它能处理不规则簇这个层面后来在内容推荐场景里用多了才意识到DBSCAN的真正优势在于它对噪声的鲁棒性——在真实的用户行为数据里噪声用户和异常行为几乎是不可避免的。多选题里则考了KNN的应用能力答案是分类、回归和推荐这三项。很多人只记得KNN能分类其实KNN做回归也很自然比如对目标点的预测值取K个近邻目标值的加权平均。推荐场景里基于物品的协同过滤本质上就是一种KNN的思路——找到与当前物品最相似的K个物品把它们作为推荐结果。这里需要注意大家很容易把KNN和K-Means搞混KNN是惰性学习、有监督方法K-Means是迭代聚类、无监督方法名字像但完全不是一回事。3.2 损失函数、正则化与过拟合简答题里有一道跟训练稳定性相关的问的是训练深度学习模型时如何判断模型是否过拟合以及有哪些常用的缓解手段。这题不涉及具体项目属于基础中的基础但想答好需要条理清晰。判断过拟合的核心标准是训练集和验证集表现的分化训练集loss持续下降验证集loss先降后升基本就是过拟合了。缓解手段我分了四类来答一是数据层面数据增强、扩充训练样本二是模型层面降低模型复杂度、减少网络层数或参数量三是正则化层面L1/L2正则、Dropout、Early Stopping四是训练策略层面Batch Normalization、集成学习等。L1和L2的区别也是爱奇艺这类公司喜欢问的点。L1正则会带来稀疏解因为它在零点不可导优化过程中更容易把某些特征权重压到正好为零L2正则只是让权重趋近于零但不会正好为零它的作用是限制权重范数让模型更平滑。我当时把L1比喻成直接从菜单里删掉不重要的特征L2则像是给每个特征的使用设一个成本限制考场上这么一解释自己也更容易把逻辑理顺。3.3 KL散度、ELBO与变分推断选择题里居然有一道关于KL散度和ELBO的当时看到这题我是有点意外的因为它更偏向生成模型和变分推断方向。题目的大意是判断关于变分推断中最大化ELBO等价于最小化KL散度这个说法的正误。这道题的正误判断依赖于对变分推断目标函数的理解。变分推断想要用分布 q(z) 去近似真实后验 p(z|x)直接最小化 KL(q(z) || p(z|x)) 是可行的但 p(z|x) 往往算不出来所以转而去最大化证据下界 ELBO。数学上可以证明log p(x) ELBO KL(q(z) || p(z|x))由于 log p(x) 对于固定的模型是一个常数最大化 ELBO 等价于最小化 KL(q(z) || p(z|x))。这个关系是变分自编码器VAE的理论基础。我当时之所以能做对是因为之前刚好认真推导过 VAE 的损失函数。这也算是个提醒算法工程师笔试里机器学习考到变分推断并不算超纲相反它说明爱奇艺的算法团队在内容生成、多模态理解这些方向上是有技术储备的。4. 编程题手撕实录字符串、搜索与图论建模4.1 字符串题实现KMP匹配过程第一道编程题考了字符串匹配给定文本串 s 和模式串 p要求返回 p 在 s 中第一次出现的位置。文本串长度和模式串长度都比较大所以要求用线性时间的算法否则会超时。最简单的暴力做法是枚举 s 的每个位置作为起点然后逐位和 p 比较时间复杂度 O(n*m)在数据量大的时候必挂。所以需要KMP核心思想是利用已匹配的信息不让主串指针回退当匹配失败时模式串向右滑动到 next 数组指示的位置而不是从头开始重新匹配。我当时实现的代码大致是这样def str_str(s: str, p: str) - int: if not p: return 0 n, m len(s), len(p) nxt [0] * m j 0 for i in range(1, m): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j j 0 for i in range(n): while j 0 and s[i] ! p[j]: j nxt[j - 1] if s[i] p[j]: j 1 if j m: return i - m 1 return -1这题的关键几个边界条件模式串为空时要返回0匹配成功后如果需要继续找下一个匹配位置应该让 j 回退到 nxt[j-1]而不是清零还有 next 数组的构建过程中j 的回退需要放在比较之前顺序错了整个数组就错了。提醒一下KMP的代码模板一定要自己手写过几遍不要只在IDE里跑过就算数。笔试环境往往没有自动补全连内置的调试功能都有限手写熟练度直接决定你能不能把这类题拿下。4.2 搜索题井字棋的minimax算法第二道编程题有点意思出的是井字棋游戏要求实现一个函数在给定棋盘状态下判断当前玩家是否必胜并返回最佳落子位置。这是一个典型的对抗搜索问题用minimax算法来解决。Minimax的核心思想是在零和博弈中己方选择收益最大的动作对方选择收益最小的动作两者交替进行直到游戏结束。井字棋的搜索空间很小最多9个格子不需要Alpha-Beta剪枝就能在毫秒级返回结果所以直接暴力搜索即可。核心逻辑可以这么写def is_winner(board, player): lines [ [0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6] ] return any(all(board[i] player for i in line) for line in lines) def minimax(board, current): if is_winner(board, X): return 1 if is_winner(board, O): return -1 if all(cell ! for cell in board): return 0 if current X: best -float(inf) for i in range(9): if board[i] : board[i] X best max(best, minimax(board, O)) board[i] return best else: best float(inf) for i in range(9): if board[i] : board[i] O best min(best, minimax(board, X)) board[i] return best def best_move(board): best_score -float(inf) move -1 for i in range(9): if board[i] : board[i] X score minimax(board, O) board[i] if score best_score: best_score score move i return move这里有一个容易踩的坑minimax的递归返回之后一定要撤销棋盘状态也就是恢复board[i] 否则回溯时棋盘已经被污染了后面所有分支的判断都会出错。这个回溯撤销的操作是搜索类题目的通用套路不只是minimax像图的DFS、全排列、组合枚举等题目都要用到。4.3 简答题图论建模与拓扑排序编程题之外还有一道简答题描述了一个课程依赖的场景一共有n门课程给定若干先修课程关系问能否排出一个合法的学习顺序。这其实就是判断有向图是否存在拓扑序列用Kahn算法可以解决。我的答题思路分三步第一步把每门课看成图的一个节点先修关系看成一条有向边第二步统计所有节点的入度把所有入度为0的节点放入队列第三步依次弹出队列中的节点并把它的所有出边指向的节点入度减1如果某个节点入度变为0就放入队列最终如果弹出的节点数等于总节点数说明可以排出合法顺序否则说明图中存在环。from collections import deque def can_finish(n, prerequisites): indeg [0] * n g [[] for _ in range(n)] for a, b in prerequisites: g[a].append(b) indeg[b] 1 q deque([i for i in range(n) if indeg[i] 0]) cnt 0 while q: u q.popleft() cnt 1 for v in g[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) return cnt n这道题本身不难但考场上还是要写清楚时间复杂度和空间复杂度Kahn算法的时间复杂度是O(VE)空间复杂度是O(VE)。我一般习惯在代码前用注释先写出解题思路这样既能理清自己逻辑也能在部分得分环境下多拿一点思路分。5. 跨界考题图像算子、卡尔曼滤波与启发式算法5.1 图像处理里的拉普拉斯算子与Sobel算子第三场笔试还出了几道让我印象深刻的图像处理题应该是考虑到视频平台算法团队日常要处理视频帧、封面图、内容理解等任务所以对图像基础也有要求。有一道多选题问的是图像锐化和边缘检测的算子。拉普拉斯算子是二阶微分算子用于图像锐化因为它对灰度突变区域响应强烈Sobel算子是一阶微分算子通常用于边缘检测通过计算水平方向和垂直方向的梯度近似值来定位边缘。这里有个容易混淆的点拉普拉斯算子虽然能检测边缘但它对噪声非常敏感所以实际使用中通常先做高斯平滑、再用拉普拉斯而Sobel算子因为带有某种程度的平滑效应对噪声的敏感度相对低一些。还有一个考点是拉普拉斯算子应用时如果中心系数为负、周围系数为正则输出需要用原图减去拉普拉斯结果而不是加上具体的符号约定要和实际应用场景对应。卷积核长什么样也是可能的考点。Sobel水平方向卷积核是 [[-1,0,1],[-2,0,2],[-1,0,1]]垂直方向是转置形态拉普拉斯四邻域卷积核是 [[0,1,0],[1,-4,1],[0,1,0]]八邻域是在四邻域基础上连对角线一起考虑。这些卷积核是图像处理的基础笔试出现频率挺高建议直接记住。5.2 PID与卡尔曼滤波在视频场景中的意义如果说图像算子还算是视频平台算法的正常考察范围那选择和简答里出现的PID控制和卡尔曼滤波就有点出乎我的意料了。当时我第一反应是这是不是走错考场了仔细一看才发现题目是结合视频播放场景来出的——问的是在视频码率自适应和播放器缓冲控制中如何利用类似PID的控制思想来调整码率。PID控制器的三大项比例项、积分项、微分项本质上是在处理当前误差、历史误差累积、误差变化趋势三个维度的信息。对应到视频播放里可以把缓冲区剩余量作为误差信号P项负责根据当前缓冲余量调整码率档位I项消除长期偏移比如网络持续变差导致缓冲一直下降D项则对缓冲变化趋势提前做出反应避免频繁切换码率。这种跨领域的题目考的其实是算法工程师的迁移能力——你能不能把一个领域里成熟的控制思想迁移到另一个表面不相关的问题上。卡尔曼滤波那道题考得更直接一些问了卡尔曼滤波在目标跟踪中的两大步骤预测和更新。预测阶段用状态转移方程估计下一时刻的状态更新阶段结合观测值对预测结果进行修正。卡尔曼滤波的核心假设是过程噪声和观测噪声都服从高斯分布因此在线性高斯系统下能得到最优估计。我当时对卡尔曼滤波的理解其实只停留在公式层面但这道题考的是概念理解所以答起来并不吃力。如果你现在准备校招我建议把卡尔曼滤波的五个公式自己手推一遍尤其要理解卡尔曼增益的物理含义——它本质上是预测的不确定性和观测的不确定性之间的一种权衡。5.3 粒子群与模拟退火启发式算法的思路有一道选择题提到粒子群算法PSO和模拟退火算法问的应该是它们属于哪一类优化方法。答案是启发式算法也叫智能优化算法适用于传统梯度下降难以解决的复杂优化问题尤其是非凸、高维、不可导的搜索空间。粒子群算法的核心是模拟鸟群觅食行为每个粒子在解空间里飞行同时受到自身历史最优位置pbest和群体历史最优位置gbest的引导。它的两个关键参数是惯性权重w、个体学习因子c1和社会学习因子c2。w越大全局探索能力越强w越小局部开发能力越强。实际应用中通常让w从0.9线性衰减到0.4这样前期多探索后期多收敛。模拟退火则是模拟金属退火过程的算法以一定概率接受比当前解更差的解从而跳出局部最优。这个概率由温度T控制温度越高接受差解的概率越大随着温度降低接受差解的概率越来越小最终收敛到一个较优解。我当时在复盘笔记里写过一句话启发式算法不保证找到全局最优但能在可接受的时间复杂度内找到逼近最优的解这在工业界里往往是更现实的选择。6. 复盘反思我从这场笔试里带走了什么6.1 从笔试看爱奇艺算法团队的能力模型参加完这场笔试我对爱奇艺算法团队的能力模型有了一个比较清晰的轮廓。它不只是要求你熟练掌握经典数据结构和机器学习算法更看重几个综合维度第一算法基础的扎实程度KMP、排序、图论这些基本功必须达到肌肉记忆的水平第二机器学习与深度学习的理论深度从KNN到变分推断都有涉及说明团队对技术深度有要求第三跨领域迁移能力图像处理、控制论、启发式优化这些看似不搭边的领域都能找到和视频业务结合的切入点。这套考察思路其实很符合视频平台的技术特点。爱奇艺的业务链路非常长视频上传后要做内容理解、封面图处理、视频编码用户端要做推荐、搜索、广告播放过程中又涉及码率自适应、卡顿优化、QoE保障。单一方向的算法知识很难覆盖这条链路的所有问题所以面试官自然会用跨界题目来筛选那些思维开阔、能快速迁移经验的候选人。6.2 如果让我重新准备一次我会怎么安排复盘完这场笔试我自己最大的感受是如果回到2018年我会把更多的精力放在算法原理的深度理解上而不是一味追求刷题数量。KMP的 next 数组手动推导、卡尔曼滤波公式的推导、变分推断的目标函数变换这些都不是靠背题能解决的必须自己动手推一遍才能形成长期记忆。另外我会给自己增加一个跨界算法阅读清单每周至少精读一个超出常规算法面试范围的算法概念比如PID控制、粒子群算法、模拟退火、拉普拉斯算子等。不需要做到能手撕代码的程度但至少要知道它的核心思想、适用场景以及它可能和什么业务问题产生关联。这种积累在笔试里可能只值一道选择题的分数但在面试的开放性讨论环节却能让你比竞争者多一个表达维度。6.3 给当前校招选手的实用清单如果把这场笔试的经验压缩成一张清单大概是下面几项基础算法模块KMP、排序、二分、贪心、拓扑排序、Dijkstra、最小生成树每类至少能手写一道代码题。机器学习模块KNN、K-Means、DBSCAN、逻辑回归、正则化、交叉熵、KL散度与ELBO的关系这些概念要能用自己的话讲清楚。图像与控制模块Sobel、拉普拉斯、PID三要素、卡尔曼滤波的预测与更新不需要精通但要知道它是干什么的、用在什么场景。代码规范手写代码时注意边界条件和复杂度分析遇到搜索类题目不要忘记回溯撤销遇到时间复杂度过高的做法要能主动优化。答题策略先扫卷、标记难题、控制每题时间编程题至少保留40分钟交卷前至少留5分钟检查边界用例。这场笔试过去很多年了但每次回想起来它都像一个十字路口让我在后来的学习和工作中更清楚自己该往哪个方向积累。如果你此时也正被校招笔试折磨得焦头烂额我想说的是把每一道做错的题都当成一次理清知识漏洞的机会考完试后认真复盘一遍比多做一套模拟题有价值得多。