爱奇艺2019秋招算法笔试题解析：KMP、动态规划与避坑指南

爱奇艺2019秋招算法方向笔试题A这份卷子我印象还挺深的。那年秋招视频平台赛道竞争激烈爱奇艺这套题不算特别难但考察面覆盖得相当全数据结构、排序、字符串匹配、贪心、动态规划都有涉及而且有些题有明显的“区分度”设计——基础不牢的人会卡在选择题刷题量不够的人会卡在编程题的边界处理上。今天把这份卷子掰开揉碎讲一遍顺便把我当时踩过的坑和后来复盘时觉得“要是早知道就好了”的点都整理出来。这套笔试题适合谁看正在准备大厂算法岗秋招/春招的应届生或者想检验自己算法功底的社招转岗候选人。不管你是刚刷完《剑指Offer》还是已经刷了两百道LeetCode这篇文章都能帮你理清这类视频平台算法岗笔试的出题偏好和复习重点。1. 题型结构与整体策略先看懂爱奇艺想考察什么1.1 试卷构成与时间分配这套笔试题A卷整体分两大块客观题和编程题。客观题以选择题为主覆盖数据结构、算法基础理论、复杂度分析编程题一般是两道到三道难度从“基础数据结构操作”到“中等偏上的动态规划/贪心”不等。考试总时长通常在90分钟到120分钟之间。我当年拿到卷子第一件事不是做题而是先把所有题目扫了一遍——这个习惯强烈建议你们也养成。为什么因为选择题里往往有某几个选项会暗示后面编程题的思路。比如选择题考了KMP的next数组计算那编程题大概率会出现字符串匹配或子串问题选择题考了排序稳定性可能后面编程题就需要你自定义比较器而不是直接调库。先把整张卷子的知识点分布摸清楚你就能预判出题人想把你往哪个方向带避免在选择题上过度纠结而压缩了编程题的时间。我建议的时间分配是这样选择题和填空/简答部分控制在35到40分钟内剩下的时间全留给编程题。如果你选择题遇到卡壳超过3分钟的先标记跳过去别恋战。爱奇艺这类公司的笔试题量大目的就是考察你在时间压力下如何分配精力这也是算法岗的职场常态。1.2 核心知识板块优先级排序结合这套题和同年其他大厂的题目来看视频平台算法岗笔试的高频板块排序是这样的第一梯队必考分值最高排序算法及变种、字符串匹配KMP、BM等、贪心算法、基础动态规划背包、LIS、LCS、数组和链表的操作。第二梯队常考但不一定每场都出二叉树遍历与重建、前缀和与差分、双指针与滑动窗口、二分答案。第三梯队偶尔出现准备到了就是送分题位运算、并查集、拓扑排序、字典树、堆的高级用法。爱奇艺这套题比较典型的特征是“入门题不难进阶题需要思路转换”。我记得当时有一道编程题看起来像是模拟题实际用贪心才能过全部数据——这种题就是专门用来筛选“只会暴力不会优化”的人。所以备考时一定要养成一个习惯写完暴力解法之后停下来想一想有没有更优的解法复杂度的天花板在哪里。2. 客观题核心考点详解从KMP到排序稳定性的理解2.1 KMP算法与next数组的计算逻辑这套选择题里最“送分”但也最要命的就是KMP的next数组计算。题目大概是模式串pabacabanext[i]定义为模式串前i个字符组成的子串中“最长相同真前缀与真后缀”的长度要求写出对应的next数组。这里先说一个很多网课不掰开讲的点next数组有几种不同的定义有的教材next[0]-1有的next[0]0还有的next[i]表示前i个字符的公共前后缀长度也就是下标从1开始。你如果没搞清楚试卷用的是哪种定义一上来就按自己熟悉的那套算必错。这题题目明确说了next[i]定义为“前i个字符”的公共前后缀长度所以下标从1开始算。我们来手推一遍pabacaba的next数组next[1]子串a真前缀和真后缀都为空公共前后缀长度为0。next[2]子串ab真前缀a真后缀b不相等公共长度为0。next[3]子串aba真前缀有a、ab真后缀有ba、a最长相等的是a长度为1。next[4]子串abac前缀a、ab、aba后缀bac、ac、c没有相等的长度为0。next[5]子串abaca前缀a、ab、aba、abac后缀baca、aca、ca、a最长相等的是a长度为1。next[6]子串abacab前缀a、ab、aba、abac、abaca后缀bacab、acab、cab、ab、b最长相等的是ab长度为2。next[7]子串abacaba前缀a、ab、aba、abac、abaca、abacab后缀bacaba、acaba、caba、aba、ba、a最长相等的是aba长度为3。所以结果是[0, 0, 1, 0, 1, 2, 3]。做这种题最稳的方法就是老老实实干手工匹配千万别凭感觉。我见过不少同学算next[7]的时候下意识填成aba长度是3就得出了但前面某一位算错导致连环错——KMP的next数组推演错一步后面全错所以考试时宁可多花一分钟验证一下对称性。2.2 排序算法稳定性与时间复杂度辨析这套选择题里关于排序的题考得比较细核心集中在“哪些排序算法是稳定的”和“不同数据分布下哪个算法效率最优”这两个点上。稳定性这个概念说白了就是如果两个元素的键值相等排序后它们的相对位置会不会改变。稳定的算法保持原有顺序不稳定的算法可能打乱。常考结论直接背算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定希尔排序O(n^1.3~2)O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)~O(n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定这里有个高频易错点很多人以为快速排序是稳定的这其实是错的。快排的partition过程会把等于基准值的元素分类到基准两侧具体怎么换取决于实现但标准实现中相对顺序是保不住的。爱奇艺这套题里我记得有一道干扰项设得很刁钻把快速排序和堆排序的平均/最坏时间复杂度混在一起如果你只记了“快排平均O(n log n)”很容易忽略堆排序最坏也是O(n log n)而快排最坏退化到O(n²)。对这种题强烈建议把“分治递归深度”作为锚点来记快排递归深度取决于基准值划分是否均衡一旦每次都取到最值递归深度就变成n复杂度自然退化。2.3 贪心、DP和字符串操作的分辨这套卷子客观题里还有一类题看起来是在考具体知识点实际上考的是“你能不能识别出这道题该用哪种算法思路”。比如给一个区间调度类的问题描述选项里有贪心有DP有回溯——这时候你要做的不是去计算而是快速判断类型。区间类问题有一个很重要的分辨技巧如果每一步选择都可以通过局部最优达到全局最优比如活动安排每次选结束时间最早的那就是贪心如果当前选择会影响后续选择而且子问题边界不明显比如带权区间调度那就是DP。这个分辨能力你自己刷题可能得几百道才有感觉但笔试时不给你那么多时间所以建议把常见问题的算法归类背熟活动安排、哈夫曼编码、最小生成树Prim/Kruskal、最短路径Dijkstra→ 贪心背包问题、最长公共子序列LCS、最长上升子序列LIS、编辑距离 → 动态规划全排列、组合求和、迷宫寻路 → 回溯/DFS最短步数、层序遍历、拓扑排序 → BFS字符串操作也是爱奇艺这类内容平台笔试的常客特别是字符串匹配、子串统计、前缀/后缀这类因为视频网站的业务里搜索、标签匹配、弹幕审核、字幕对齐全是字符串问题。3. 编程题实战拆解从读题到AC的完整思维链3.1 典型动态规划题最长上升子序列LIS变形这类题在爱奇艺笔试里出现的概率非常高。经典的LIS是求最长上升子序列长度笔试里通常会加一点变形比如“求最长连续上升子序列”或者“按顺序抽取满足条件的最长子序列”。先看最经典的O(n²)动态规划写法这个必须滚瓜烂熟def length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)思路很简单dp[i]表示以nums[i]结尾的最长上升子序列长度枚举j i找到所有能接在后面的位置。如果笔试数据量到了10^5O(n²)会超时必须用二分优化到O(n log n)。这个优化版本笔试很爱考因为能刷掉一批人。核心是维护一个tails数组tails[k]表示长度为k1的上升子序列的最小末尾元素import bisect def length_of_lis_nlogn(nums): tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这个优化版你必须理解背后的原理而不是死记代码tails数组是递增的遍历每个数x时在tails里找第一个不小于x的位置替换掉它。替换不改变数组长度但把“潜力更大”的较小末尾值保留了下来让后续数字更容易接出更长的序列。如果你面试被问到LIS的优化原理从“贪心二分”这个角度去回答最稳妥。3.2 经典背包问题01背包与完全背包的边界处理背包问题是动态规划里的“万金油”爱奇艺这套笔试题里出现的基本是变形的0/1背包。0/1背包最朴素的二维DP转移方程def knapsack_01(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w weights[i - 1] v values[i - 1] for j in range(capacity 1): if j w: dp[i][j] dp[i - 1][j] else: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v) return dp[n][capacity]但笔试时内存不够用的情况很常见因为如果背包容量是10^5、物品数是10^3二维数组10^8个整数直接溢出。所以必须掌握一维滚动数组优化def knapsack_01_1d(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): # 必须倒序遍历保证每个物品只用一次 for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]这里最关键的就是j必须倒序遍历。为什么因为一维数组dp[j]被更新后如果正序继续更新dp[j w]就会可能重复使用当前物品——这刚好是完全背包每种物品无限用的逻辑。所以如果题目换成完全背包只需要把内层循环改成正序遍历。这个“正序完全背包倒序01背包”的口诀笔试前必须刻进脑子里。3.3 字符串处理题从模拟到KMP的思维升级视频平台笔试的字符串题比一般互联网公司的更多一些毕竟业务上搜索、字幕、弹幕等等都需要处理字符串。最典型的题是给两个字符串求第一个在第二个中首次出现的位置或者统计出现次数。暴力的思路就是两层循环匹配时间复杂度O(n*m)。一旦字符串长度超过10^4大样例直接超时。这时候就应该想到KMP。KMP的核心思想是当匹配失败时不回溯主串指针而是利用next数组把模式串向右滑动到合适位置。我当年整理了一个“手撕KMP”的模板笔试直接默写强烈建议你们也准备一份def build_next(p): m len(p) next_arr [0] * m j 0 for i in range(1, m): while j 0 and p[i] ! p[j]: j next_arr[j - 1] if p[i] p[j]: j 1 next_arr[i] j return next_arr def kmp_search(s, p): n, m len(s), len(p) if m 0: return 0 next_arr build_next(p) j 0 for i in range(n): while j 0 and s[i] ! p[j]: j next_arr[j - 1] if s[i] p[j]: j 1 if j m: return i - m 1 return -1注意这个模板里的next_arr用的是“最长相等前后缀长度”这个概念和客观题里算的是同一套逻辑但实现上有微调。如果你习惯用next[0]-1的老模板就必须把整段代码统一换成老模板的写法别混着来。我当时笔试前吃了这个亏模板里混用了两套next定义在某个边界样例上报错排查了半天。3.4 一道模拟贪心的综合题复盘这套卷子编程题里有一道题我印象特别深题干大概是有多个视频任务每个任务有开始时间和结束时间一个转码服务器同一时间只能处理一个任务问最多能处理多少个任务。这就是典型的“活动安排问题”——贪心。只要证明“每次选结束时间最早的任务”是最优策略然后实现起来就很简单按结束时间排序遍历时如果当前任务开始时间不早于上一个选中的结束时间就选它。def max_tasks(tasks): 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这个“贪心选最早结束”的思路在爱奇艺这类视频平台的调度场景里非常常见不只是转码任务CDN节点分配、弹幕审核队列都可以抽象成这个模型。你不仅要会写代码还要能说出贪心策略正确性的直观解释选结束早的任务能给后续任务留下更多时间窗口所以一定不会比选结束晚的任务差。4. 高频考点扩展与刷题策略粒子群、模拟退火与规则引擎的边界在哪4.1 启发式算法粒子群/模拟退火在笔试中的考查方式这里我得提一下很多人在准备算法笔试时看到粒子群算法、模拟退火算法、神经网络这些热搜词就慌了以为笔试会考。实际上爱奇艺2019这套笔试题A里选择题偶尔会问“以下哪些算法属于启发式算法/元启发式算法”或者给一个概念题让选“模拟退火算法中温度参数的作用”。这类题考的是概念辨析不考实现。所以复习策略就是知道它们是什么、能解决什么问题、核心思想是什么即可。粒子群算法就是模拟鸟群觅食每个“粒子”代表候选解通过个体最优和群体最优来迭代更新速度和位置。模拟退火的核心思想是“以一定概率接受更差的解”来跳出局部最优温度高时接受概率大温度越来越低最终收敛。知道这些概念层面的东西笔试选择题足够应付了。但如果岗位是推荐算法或视频分析方向面试官可能会追问启发式算法在超参调优上的应用场景那你就得再多准备一下。4.2 规则引擎Rete算法算法不只活在算法题里热词里还有一个有意思的规则引擎drools的rete算法实现原理和事实匹配过程。这个不是爱奇艺这套笔试题直接考的点但它反映了算法岗笔试的一个趋势——很多大厂会穿插一些“业务相关的基础技术原理”题。Rete算法是规则引擎比如Drools里用来高效匹配事实与规则的核心算法核心思想是构建一个网络结构Alpha网络、Beta网络把规则的匹配过程分解成多个阶段的共享计算避免每条规则独立匹配时的大量重复计算。说白了就是“把规则编译成一个有向图事实数据在网络里流动通过节点缓存和共享来加速匹配”。如果你正在准备爱奇艺这类内容平台的算法岗我建议你有余力时大概了解下规则引擎因为视频推荐策略、审核规则、会员权益策略都可能用到规则引擎面试现场聊到这个你会加分不少。但注意这类题在笔试题里出现的概率很低优先级排在所有算法题之后。4.3 笔试前的刷题清单结合粒子群、PID、卡尔曼滤波等热搜词的正确打开方式我再结合热搜词把备考范围理一理。PID算法、卡尔曼滤波算法、FOC算法、MPPT算法这类控制类算法大多出现在硬件/自动驾驶/电力方向的算法岗笔试题中不是视频平台算法岗的主流但如果你是海投比如同时投了自动驾驶公司那还是得熟悉它们的原理和适用场景。PID算法核心就是比例、积分、微分三个环节的加权控制调整的是系统输出对偏差的响应速度、稳态精度和超调量。卡尔曼滤波是状态估计算法适合对带有噪声的传感器数据进行最优估计在视频目标跟踪里也会用到。这类算法的考查方式通常不是让你手写实现而是给场景、问选哪种算法或者给公式、问各个参数的意义。至于BM25算法、音频重采样算法、Sobel边缘检测、聚类算法——这些反而和爱奇艺的业务更贴近。BM25是搜索排序里的经典相关度算法音频重采样在音视频处理管线里很常见Sobel算子做图像边缘检测视频内容审核会用到聚类在用户画像、视频分类里有大量应用。如果你的目标岗位是搜索/推荐/视频分析方向这些一定要重点准备。我建议的刷题分配方案是这样7成时间花在LeetCode Hot 100和剑指Offer上2成时间复习算法概念题稳定性、复杂度、KMP手工计算、贪心/DP识别1成时间了解业务相关算法的基础原理。别本末倒置——钻研粒子群优化器怎么收敛之前先确保自己能在45分钟内AC一道中等难度的DP题。5. 常见问题与笔试避坑指南5.1 笔试中常见的“非技术性”丢分点技术之外的坑往往比技术本身的坑更容易丢分。第一审题不清。很多编程题看着和LeetCode原题很像但边界条件不一样。比如LeetCode原题是“非递减序列”笔试改成了“严格递增”又比如输入是“排序后的数组”但可能是从大到小排列的。一定要把题目从头到尾读两遍尤其是输入输出格式说明和示例。第二数据类型不够大。如果你用C写题注意int溢出用Python就相对省心但如果中间计算出现浮点数比较注意精度问题。爱奇艺这套题里有的用例数据量给得很大比如10^9的输入如果你选了不合适的算法或数据结构直接超时。第三不处理空输入。笔试环境里输入可能有空行、空格、换行符的坑。写代码前先想清楚怎么读入用sys.stdin.read().split()这种一次性读入再处理的方式通常最稳。第四不输出多余内容。调试用的print如果不删干净就算核心逻辑对了也会判错。我自己就在模拟笔试时干过这种事打印了一行debug信息导致整个case被判定为输出格式错误直接0分。5.2 编程环境与输入输出的实战建议爱奇艺的笔试一般用的是牛客网或赛码网的环境在线编辑器没有本地IDE那么友好。建议提前熟悉这两种平台的环境它们支持的语言版本、输入输出模板、是否有代码补全。平时刷题用LeetCode函数的同学第一次用牛客网会遇到“需要自己写输入输出处理”的情况很容易懵。我提供一个通用的Python在线笔试输入模板拿过去直接改import sys def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 # 读第一个数通常是n或者测试用例数 n int(data[idx]) idx 1 nums [] for _ in range(n): nums.append(int(data[idx])) idx 1 # 在这里写你的核心逻辑 result 0 print(result) if __name__ __main__: solve()注意有些题目是多组输入直到EOF这时就要用for line in sys.stdin循环处理。判断标准就看题目描述是“多组测试数据”还是“单个测试用例”。提示笔试时可以事先准备好常用的算法模板KMP、并查集、Dijkstra、二分查找、快排partition在开考后前几分钟先把这些模板默写在草稿纸上。这不是作弊而是把最机械的记忆工作提前完成把大脑留给真正的思考题。5.3 时间不够时的取舍策略编程题如果第一题属于“签到题”一定要确保AC这是保底分。如果遇到两道题都做不出来的情况先把能写出来的暴力解法写上去哪怕只能过30%的用例也有分——很多笔试是部分得分制不是非对即错。比直接放弃更好的策略是如果你能确定正确解法是贪心或DP但边界处理不完美那就写一个“正确思路但某条件写错”的版本然后把容易错的边界情况用if打补丁。有时候能多过几个case。千万不要在“输入输出格式正好对上但答案错”这种状态下空举40分钟先写上再说。5.4 考后复盘的正确姿势笔试结束不代表结束复盘才是真正拉开差距的地方。每次模拟笔试或正式笔试后把这四类问题记下来第一类是“算法方向想错”的题。比如一眼以为是模拟题实际要用滑动窗口维护最大值或者一眼以为是贪心但局部最优不一定是全局最优。这类错题要仔细记录“什么样的问题特征应该往什么算法上想”形成自己的“题型→算法”映射表。第二类是“想出思路但写不出来”的题。说明你的代码实现能力还跟不上思路这类题要重新手写三遍以上直到不看参考代码能默写。第三类是“差一点就AC”的题。绝大多数是边界条件问题比如数组越界、空集合、结果需要取模等。把这些边界情况集中记下来下次写题之前先在脑子里过一遍。第四类是“完全没思路”的题。这类题如果复盘后发现解法其实很简单说明你的题型覆盖有盲区需要去专项刷这个分类如果解法确实难那笔试时跳过也是合理的取舍。我自己的复盘习惯是建一个Excel表格每一行一道错题列分别是日期、题目来源、知识点、错误原因方向错/边界错/代码错/超时、正确解法的关键思路、重写次数。这个表格坚持三个月你的笔试命中率提升会非常明显。6. 个人经验补充算法岗笔试不仅仅是算法的较量回顾爱奇艺2019秋招算法方向笔试题A客观评价它的难度在当年大厂笔试里属于中等偏易和头条、腾讯的压轴题难度比要低一些。但通过率并不高原因不是题目难而是很多人在选择题上花了45分钟以上编程题根本来不及认真做。如果你现在还在准备阶段我最想强调的不是让你多刷题而是“输出倒逼输入”——每学完一个算法不要满足于看懂亲手写一遍、把复杂度分析写清楚、把典型题目做三遍。你可以和同学互相出题、互相批改或者把自己的题解发到博客/牛客上。这个过程很慢但效率非常高。技术之外笔试时心态也很关键。当年我同考场有个同学选择题卡在KMP手算上急了半小时后面编程题全乱了阵脚。当时我给自己定的规矩是选择题遇到不确定的先选一个再标记编程题保证第一题AC后再看剩下的。这份冷静比我当年多刷两百道题还管用。笔试题再难本质是考察你在资源有限时间、精力情况下的取舍能力——算法功底是其中一环分配策略和心态管理是另一环这恰恰是平时刷题最容易忽略、却又最能拉开差距的地方。最后分享一个小习惯每次笔试结束不管成绩如何花15分钟把整张卷子的知识点分布画成一张思维导图时间久了你会摸到爱奇艺这类公司出题口味的变化规律。这个动作坚持几次之后你再看到一套陌生笔试题就能快速判断哪些题该多花时间、哪些题该果断跳过——这种“题感”一旦形成拿offer就是水到渠成的事。