如果你准备过2020年那一届秋招一定对爱奇艺的编程题有印象。当年很多同学拿到这套题的第一反应是怎么这么多字符串和动态规划其实这个出题方向背后是有道理的——视频网站每天要处理海量的内容推荐、弹幕流、用户行为序列和版权审核任务算法题考察的正是这些场景里最底层的计算模型。这篇文章我把爱奇艺2020校招编程题按题型做了一次系统拆解结合我在多家互联网公司参与校招出题和面试的经验把每类题的核心思路、完整代码和考场注意事项全部展开。准备校招、或者想了解视频行业算法题风格的人都可以直接拿这份题单来练。1. 爱奇艺校招编程题的出题风格与备考定位先说结论2020年爱奇艺校招编程题整体难度处在互联网大厂的中游水平难度明显低于腾讯和字节的校招笔试但比普通国企和银行要高出不少。从网上流传的回忆版题目来看三套卷子加起来大概有十几道题核心集中在动态规划、字符串处理、滑动窗口和模拟题这几类而且和业务贴得非常近。1.1 2020年这一批题目的整体画像我根据当年参与讨论的考后回忆整理了一张题型分布表大家可以先对这部分有一个整体概念题型类别出现频率典型考点业务映射动态规划高LIS、背包、状态压缩会员套餐、内容排序字符串/滑动窗口高最小覆盖、回文、编辑距离弹幕过滤、标题相似度图论/BFS中连通域、最短路人脸审核区域、反作弊网络双指针中原地去重、区间合并视频ID清洗、时间轴合并模拟/数学中大数运算、贪心积分结算、匹配规则这个分布不是巧合。视频平台的后端服务每天要处理的不是高并发下单就是海量文本和状态流。技术面试官在选择编程题的时候天然会倾向于那些可以映射到日常业务的题型因为这样能更快筛出真正理解业务抽象的人而不是只会背题目模板的候选人。1.2 出题风格和视频业务高度绑定爱奇艺和字节、腾讯这类公司不一样的地方在于它的用户体量带来了很多刚性的技术问题。比如说弹幕系统核心要求是高并发下维持有序内容审核系统要做海量视频帧里的目标区域检测会员系统要处理各种优惠券叠加下的金额计算。这些真实场景倒逼着技术团队把很多通用算法落在工程里所以校招编程题也会不自觉地向这些领域倾斜。它的编程题很少出那种纯脑筋急转弯更多是给你一个业务包装过的题目卡点往往在状态设计和边界条件处理上。说白了面试官想看的是你把业务问题抽象成算法模型的能力而不是背了多少模板。备考的时候如果只刷LeetCode热门题不做业务映射思考上了考场容易被包装过的题干绕晕。1.3 备考策略定位如果你的目标是爱奇艺这类视频平台或中大型互联网公司的算法岗和研发岗我的建议是把重心放在动态规划、字符串、滑动窗口这三类高频题上。图论不要贪多会用BFS/DFS和最短路的模板就够了。模拟题主要练读题能力和编码细节因为这类题往往代码量大但逻辑简单拼的就是谁在高压下不容易写错。刷题方式上我不建议按题号顺序刷而是按题型归类刷。每道题做完之后强制自己在三分钟内口述一遍完整思路包括状态定义、转移方程、初始化和复杂度。这样到了笔试现场看到题目包装你剥掉外壳的速度会快很多。2. 动态规划是重头戏从LIS到背包变体动态规划在爱奇艺这套题里的地位基本就是压轴题的常客。我见过的回忆版题目里至少有四道可以用DP来解。这一章我挑两道最有代表性的题展开讲一道是LIS变体一道是完全背包变体这两道吃透DP的大题基本就能稳住。2.1 从“最长递增子序列”看状态定义的价值当年有一道题题干讲的是给出一组视频的完播率序列需要找到最长的严格递增子序列用来衡量用户黏性的变化趋势。如果你剥掉业务外壳这就是经典的LIS问题。没做过的人容易想岔一开始以为子序列要求连续其实不需要只要在原序列里保持相对顺序即可。这是LIS最容易踩的第一个坑。第二个坑是状态定义很多第一次接触的人想用dp[i]表示“前i个元素的最长递增子序列长度”这个定义也能做但转移起来很别扭。更标准的定义是dp[i]表示以nums[i]结尾的最长递增子序列长度。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)这段代码的复杂度是O(n^2)在n不超过5000时完全够用。笔试里如果卡的n到了10^5级别就需要优化。优化思路是维护一个tails数组tails[k]表示长度为k1的递增子序列里末尾元素的最小值。遍历每个数时用二分查找找到它应该替换的位置这样整体复杂度降到O(n log n)。def length_of_lis_binary(nums): import bisect 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)实际笔试中O(n^2)能不能过取决于题目给的数据范围。我建议先把O(n^2)版本练熟再理解二分版本两个版本都不难但二分版本更容易在细节上出错。2.2 背包问题会员套餐礼包的最优组合背包问题在爱奇艺的编程题里出现过不止一次。我记得有一道题的大意是会员平台有n种礼包每种礼包有价格cost[i]和权益值value[i]每种礼包可以用无限次现在总预算为M问最多能获得多少权益值。这就是完全背包的裸题。企业里比较贴近的上下文就是优惠券叠加和会员权益组合。假设你的支付接口要支持各种权益包任意组合本质上就是这个模型。完全背包写起来和0-1背包很相似唯一的区别在于遍历顺序def complete_knapsack(costs, values, budget): dp [0] * (budget 1) for i in range(len(costs)): for j in range(costs[i], budget 1): dp[j] max(dp[j], dp[j - costs[i]] values[i]) return dp[budget]很多新手最大的困惑就是为什么0-1背包要倒序遍历而完全背包要正序遍历道理其实很简单。0-1背包要求每个物品最多拿一次如果正序遍历dp[j - costs[i]]可能已经包含了当前物品就会造成重复拿取完全背包本来就允许重复拿取正序遍历反倒让它可以复用当前物品的状态完成无限次的累加。如果你把遍历顺序写反0-1背包会变成完全背包完全背包会变成0-1背包而且很难通过样例发现因为小数据量下恰好能蒙对。这个点我在面试里反复问过候选人能讲清楚的人不多建议你吃透。2.3 DP做题时最容易被扣分的三个点第一初始化不对。dp数组很多题应该初始化为0但LIS这类题要初始化为1因为每个元素自身构成一个长度为1的子序列。第二取结果时取错位置。很多DP的最优解不在dp[-1]比如LIS的最优解可能在数组中间某个位置必须遍历取max。第三忽略n0或者budget0的边界。笔试环境里空输入很常见如果不写判空第一行就会抛异常。另外还有一个经验DP题写完之后一定要自己构造一个小样例手动跑一遍。比如完全背包用costs[2,3], values[3,4], budget7来测手算一下答案是8还是9。这种手动验证能帮你抓住状态转移里最隐蔽的逻辑错误。3. 字符串与滑动窗口文本处理和用户行为序列的常客字符串题在这套题里出现频率很高和爱奇艺的弹幕、搜索、内容去重业务有直接关系。这一章我选两道高频题展开最小覆盖子串和最长回文子串。这两道题在LeetCode上是经典题但在爱奇艺的卷子里被包了一层业务外壳考察点其实没变。3.1 最小覆盖子串关键词覆盖率有一道回忆版题目题干说的是给定一段弹幕文本s和一个关键词集合t假设t中只包含小写字母需要找到s中包含t所有字符的最短连续子串。去掉外壳就是LeetCode 76题。这道题是滑动窗口的经典应用。核心思路是右指针不断向右扩展窗口直到窗口内覆盖了t的所有字符然后收缩左指针找到当前右指针位置下最短的合法窗口记录答案继续移动右指针。这里需要借助一个哈希表来维护窗口内字符的缺口数量。from collections import Counter def min_window(s, t): need Counter(t) missing len(t) left 0 start 0 min_len float(inf) for right, ch in enumerate(s): if need[ch] 0: missing - 1 need[ch] - 1 if missing 0: while need[s[left]] 0: need[s[left]] 1 left 1 if right - left 1 min_len: min_len right - left 1 start left need[s[left]] 1 left 1 missing 1 return s[start:start min_len] if min_len ! float(inf) else 这道题容易错的地方有三处。第一need字典中负数的含义是当前窗口里某个字符多出来的个数收缩左指针时只移动那些need[s[left]] 0的字符第二当missing 0时表示窗口已经覆盖了t中所有字符此时再移动左指针会破坏覆盖状态所以要及时更新missing第三min_len的初值一定要设成无穷大否则窗口为空时返回结果会出错。3.2 最长回文子串中心扩展法回文串在视频场景里的应用常见于内容去重和标题对称性检测。最长回文子串这道题DP可解但中心扩展法更直观而且空间复杂度只有O(1)。思路很朴素遍历字符串的每个位置以它为中心向两边扩展同时要兼容奇数长度和偶数长度两种情况。def longest_palindrome(s): if not s: return max_len 1 start 0 for i in range(len(s)): l, r i - 1, i 1 while l 0 and r len(s) and s[l] s[r]: if r - l 1 max_len: max_len r - l 1 start l l - 1 r 1 l, r i, i 1 while l 0 and r len(s) and s[l] s[r]: if r - l 1 max_len: max_len r - l 1 start l l - 1 r 1 return s[start:start max_len]这里要注意奇数长度和偶数长度的中心是不一样的。奇数中心是单个字符偶数中心是两个相邻字符。如果你只写一个循环大概率有一半的用例过不了。3.3 字符串题的两个隐蔽坑第一个坑是Python的字符串拼接。字符串是不可变对象循环里用拼接会产生大量临时对象复杂度退化成O(n^2)。如果需要在循环里积累字符用list收集再.join()效率高出几个数量级。第二个坑是字符集范围。如果题目限定只包含小写字母可以用长度为26的数组当哈希表下标用ord(ch) - ord(a)计算速度快很多。如果没限定字符集老老实实用字典否则遇到大写字母或数字就会越界。4. 图论搜索与双指针从连通域到原地去重图论搜索在爱奇艺这套题里不是最高频的方向但隔三差五就会出现一次。双指针则更多隐藏在排序和去重类题目里。这一章我把两类放在一起讲因为它们有一个共同点模板固定但边界条件容易写错。4.1 网格连通域审核场景的“岛屿数量”我印象里有一道题题目描述的是内容审核系统给视频帧划分了网格1表示待审核区域0表示正常区域要求统计有多少个连通的待审核区域。去掉业务外壳就是LeetCode 200题岛屿数量。这道题可以用DFS、BFS或并查集解决。笔试环境里最推荐的是用栈模拟的DFS因为递归在Python里一旦遇到大矩阵很容易触发递归深度上限直接Runtime Error。下面是用显式栈的写法def num_islands(grid): if not grid: return 0 count 0 m, n len(grid), len(grid[0]) for i in range(m): for j in range(n): if grid[i][j] 1: count 1 stack [(i, j)] while stack: x, y stack.pop() if x 0 or x m or y 0 or y n or grid[x][y] ! 1: continue grid[x][y] 0 stack.append((x - 1, y)) stack.append((x 1, y)) stack.append((x, y - 1)) stack.append((x, y 1)) return count这种遍历方式有个细节每次从栈里弹出节点后要立刻把grid[x][y]置为0也就是“标记已访问”。如果不及时标记同一个节点可能被多次入栈小数据量还好大数据量直接超时。我在实际调试里遇到过这个问题加了标记之后运行时间从超时降到几十毫秒。4.2 双指针原地去重和区间合并双指针类题目在笔试里经常作为中等题的保底题出现。比如有一道题是这样的给定升序排列的视频ID数组需要原地去重并返回新的长度额外空间要求O(1)。这种题面试官可能会追问为什么两个指针的写法是O(n)的而不是O(n^2)的。def remove_duplicates(nums): if not nums: return 0 i 0 for j in range(1, len(nums)): if nums[j] ! nums[i]: i 1 nums[i] nums[j] return i 1双指针的核心思想其实很简单快指针负责遍历数组把遇到的“新元素”写到慢指针指向的位置慢指针始终指向最后一个不重复元素的下标。因为数组有序所以只要快指针的值和慢指针不同就可以确定快指针遇到了新元素。类似的还有区间合并题比如弹幕的时间段合并。给出一组区间要求合并所有重叠区间。思路是先按起始时间排序再遍历维护当前区间的终点遇到重叠就扩展终点不重叠就把当前区间加入答案。这类题的关键是先排序很多新人容易忽略这一步。4.3 搜索题里常见的优化点BFS适合求最短路径DFS适合判断存在性和连通性两者在复杂度上没有本质差别选择标准是题目要求。如果是求“最少步数”“最短路径”优先BFS如果是判断“是否存在”“共有多少块”DFS写起来更顺手。大矩阵下的连通域题目如果DFS和BFS都超时可以考虑用并查集。并查集适合动态判定连通性的场景但在笔试里写起来代码量偏大我一般只在面试聊方案时才提笔试里还是用栈模拟BFS最稳。5. 模拟题的“业务化包装”与数学思维模拟题在爱奇艺的编程题里占的比重不低而且这类题有一个显著特点逻辑不难但题干很长业务名词很多。很多人不是不会做而是被题干绕晕或者写着写着发现自己对题意理解偏了。这一章我挑两道典型题讲一讲怎么快速抽离出核心逻辑。5.1 从弹幕时间段抽象出最大并发数有一道题目的场景是弹幕系统的负载评估。给定若干弹幕的起止时间需要统计同一时刻最多有多少条弹幕同时显示。如果你直接对每条弹幕做区间相交判断复杂度是O(n^2)n超过一万就基本跑不动。正确做法是把所有开始时间和结束时间分别排序然后用两个指针扫描。遇到开始时间当前并发数加一遇到结束时间当前并发数减一。扫描过程中记录并发数的最大值。这个思路像是给一整天的弹幕事件做了个时间轴逐个事件推进状态。def max_concurrent(starts, ends): starts.sort() ends.sort() i j 0 cur 0 max_cur 0 while i len(starts): if starts[i] ends[j]: cur 1 max_cur max(max_cur, cur) i 1 else: cur - 1 j 1 return max_cur这里要注意结束时间在边界上的处理逻辑。题目如果要求“相同时间点先加后减”那么判断条件写成就是正确的如果要求“先减后加”条件要改成。考试时读清楚题目说明这种细节经常决定AC还是WA。5.2 大数运算会员积分和金额计算的底层大数运算在视频平台里的应用很直接会员积分、虚拟币、优惠券金额都可能超出普通整数范围。有一道回忆版题目就是让实现两个正整数字符串形式数字的乘法不允许直接用内置的大整数类型。大数乘法的核心思路是模拟竖式乘法用数组存放每一位的结果。两个长度分别为m和n的数字相乘结果长度最多为mn位。从低位开始逐位相乘把结果累加到对应的数组位置最后统一处理进位。def multiply(num1, num2): if num1 0 or num2 0: return 0 m, n len(num1), len(num2) res [0] * (m n) for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): mul int(num1[i]) * int(num2[j]) p1, p2 i j, i j 1 total mul res[p2] res[p1] total // 10 res[p2] total % 10 idx 0 while idx len(res) and res[idx] 0: idx 1 return .join(map(str, res[idx:]))大数乘法最容易错的地方有两个一是进位没有累加到更高位二是结果有前导零时没有跳过。我测试过很多次这两个问题在初版代码里几乎必现所以写成模板背下来是性价比很高的选择。5.3 模拟题应试技巧遇到题干的业务包装特别厚的模拟题我一般会先做三件事第一把输入输出格式用一句话写在草稿纸上避免读到一半忘记第二把题目里的业务术语翻译成数据结构术语比如“弹幕”就是“区间”“会员等级”就是“int数组”第三在代码注释里先写伪代码框架再一行行填充实现。模拟题最怕的是写着写着发现理解错了题意所以先花五分钟理清逻辑比闷头写半小时更划算。这类题的赛点不只是在编码更在阅读理解。6. 考场上最实用的应试策略与避坑清单编程题平时刷得再多到了考场上如果时间分配和边界处理没做好一样翻车。这一章我把自己在笔试和面试辅导中总结出来的一些比较实用的考场经验整理出来供大家参考。6.1 时间分配建议假设笔试一共两小时三到四道题我会这样分配时间时间段任务目标前5分钟快速浏览全部题目确定做题顺序标记难度第1题40分钟先做最有把握的题保住基本盘拿到AC第2题30分钟做中等难度题争取AC或拿到大部分用例分第3题30分钟做最难的一题写暴力版保证部分用例通过剩余15分钟检查所有题的边界修正越界、空输入、溢出等低级错误很多人在最难的一题上死磕导致前面能拿的分丢了。笔试的通过标准从来不是全对而是总分过线所以保AC优先于攻克难题。6.2 高频边界条件清单我整理了一个自己每次笔试前都会扫一遍的边界条件清单贴在便利贴上数组长度为0或1时逻辑是否成立输入包含整数、小数、负数时变量类型是否覆盖字符串包含空格、大小写混合时比较逻辑是否出错数值相加或相乘时是否会溢出int范围递归深度是否可能超过Python默认的1000层同一时间点多个事件先加还是先减如果题目没有明确说明边界输入默认处理这些情况不会扣分但如果丢了很可能是批量WA的原因。6.3 从刷题到面试问答的衔接校招面试时面试官大概率会追问算法题的核心思路为什么用这个数据结构复杂度是多少还有没有优化空间特别是爱奇艺这类视频公司面试官很喜欢问“这个算法如果应用在我们的场景里你会怎么做”。所以我刷题时有个习惯每做完一道题脑子里过一遍这个算法可以用在什么业务场景。比如滑动窗口可以用于弹幕关键词实时统计LIS可以用于用户行为路径分析并查集可以用于反作弊的社群发现。到了面试环节这些铺垫会让答案听起来更有工程感而不是背书感。最后再分享一个小经验我从2020年那届开始大量带校招学生刷题总结下来编程题拿高分的核心不是刷题数量而是每道题做完后的复盘质量。建议你拿到任何一份题单先自己限时做一遍再对照最优解法把状态定义、边界条件、复杂度三个维度写进笔记。这样刷30道题的效果比漫无目的刷100道好得多。还有一个小技巧爱奇艺这类公司的笔试环境一般是自研OJ评测机对Python版本和递归深度有限制如果题目里你想到用递归建议提前换成迭代实现。递归写起来好看但在OJ上可能因为一个深坑直接运行时错误换成显式栈或者迭代能省掉很多无谓的麻烦。祝各位笔试顺利。
如果你准备过2020年那一届秋招一定对爱奇艺的编程题有印象。当年很多同学拿到这套题的第一反应是怎么这么多字符串和动态规划其实这个出题方向背后是有道理的——视频网站每天要处理海量的内容推荐、弹幕流、用户行为序列和版权审核任务算法题考察的正是这些场景里最底层的计算模型。这篇文章我把爱奇艺2020校招编程题按题型做了一次系统拆解结合我在多家互联网公司参与校招出题和面试的经验把每类题的核心思路、完整代码和考场注意事项全部展开。准备校招、或者想了解视频行业算法题风格的人都可以直接拿这份题单来练。1. 爱奇艺校招编程题的出题风格与备考定位先说结论2020年爱奇艺校招编程题整体难度处在互联网大厂的中游水平难度明显低于腾讯和字节的校招笔试但比普通国企和银行要高出不少。从网上流传的回忆版题目来看三套卷子加起来大概有十几道题核心集中在动态规划、字符串处理、滑动窗口和模拟题这几类而且和业务贴得非常近。1.1 2020年这一批题目的整体画像我根据当年参与讨论的考后回忆整理了一张题型分布表大家可以先对这部分有一个整体概念题型类别出现频率典型考点业务映射动态规划高LIS、背包、状态压缩会员套餐、内容排序字符串/滑动窗口高最小覆盖、回文、编辑距离弹幕过滤、标题相似度图论/BFS中连通域、最短路人脸审核区域、反作弊网络双指针中原地去重、区间合并视频ID清洗、时间轴合并模拟/数学中大数运算、贪心积分结算、匹配规则这个分布不是巧合。视频平台的后端服务每天要处理的不是高并发下单就是海量文本和状态流。技术面试官在选择编程题的时候天然会倾向于那些可以映射到日常业务的题型因为这样能更快筛出真正理解业务抽象的人而不是只会背题目模板的候选人。1.2 出题风格和视频业务高度绑定爱奇艺和字节、腾讯这类公司不一样的地方在于它的用户体量带来了很多刚性的技术问题。比如说弹幕系统核心要求是高并发下维持有序内容审核系统要做海量视频帧里的目标区域检测会员系统要处理各种优惠券叠加下的金额计算。这些真实场景倒逼着技术团队把很多通用算法落在工程里所以校招编程题也会不自觉地向这些领域倾斜。它的编程题很少出那种纯脑筋急转弯更多是给你一个业务包装过的题目卡点往往在状态设计和边界条件处理上。说白了面试官想看的是你把业务问题抽象成算法模型的能力而不是背了多少模板。备考的时候如果只刷LeetCode热门题不做业务映射思考上了考场容易被包装过的题干绕晕。1.3 备考策略定位如果你的目标是爱奇艺这类视频平台或中大型互联网公司的算法岗和研发岗我的建议是把重心放在动态规划、字符串、滑动窗口这三类高频题上。图论不要贪多会用BFS/DFS和最短路的模板就够了。模拟题主要练读题能力和编码细节因为这类题往往代码量大但逻辑简单拼的就是谁在高压下不容易写错。刷题方式上我不建议按题号顺序刷而是按题型归类刷。每道题做完之后强制自己在三分钟内口述一遍完整思路包括状态定义、转移方程、初始化和复杂度。这样到了笔试现场看到题目包装你剥掉外壳的速度会快很多。2. 动态规划是重头戏从LIS到背包变体动态规划在爱奇艺这套题里的地位基本就是压轴题的常客。我见过的回忆版题目里至少有四道可以用DP来解。这一章我挑两道最有代表性的题展开讲一道是LIS变体一道是完全背包变体这两道吃透DP的大题基本就能稳住。2.1 从“最长递增子序列”看状态定义的价值当年有一道题题干讲的是给出一组视频的完播率序列需要找到最长的严格递增子序列用来衡量用户黏性的变化趋势。如果你剥掉业务外壳这就是经典的LIS问题。没做过的人容易想岔一开始以为子序列要求连续其实不需要只要在原序列里保持相对顺序即可。这是LIS最容易踩的第一个坑。第二个坑是状态定义很多第一次接触的人想用dp[i]表示“前i个元素的最长递增子序列长度”这个定义也能做但转移起来很别扭。更标准的定义是dp[i]表示以nums[i]结尾的最长递增子序列长度。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)这段代码的复杂度是O(n^2)在n不超过5000时完全够用。笔试里如果卡的n到了10^5级别就需要优化。优化思路是维护一个tails数组tails[k]表示长度为k1的递增子序列里末尾元素的最小值。遍历每个数时用二分查找找到它应该替换的位置这样整体复杂度降到O(n log n)。def length_of_lis_binary(nums): import bisect 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)实际笔试中O(n^2)能不能过取决于题目给的数据范围。我建议先把O(n^2)版本练熟再理解二分版本两个版本都不难但二分版本更容易在细节上出错。2.2 背包问题会员套餐礼包的最优组合背包问题在爱奇艺的编程题里出现过不止一次。我记得有一道题的大意是会员平台有n种礼包每种礼包有价格cost[i]和权益值value[i]每种礼包可以用无限次现在总预算为M问最多能获得多少权益值。这就是完全背包的裸题。企业里比较贴近的上下文就是优惠券叠加和会员权益组合。假设你的支付接口要支持各种权益包任意组合本质上就是这个模型。完全背包写起来和0-1背包很相似唯一的区别在于遍历顺序def complete_knapsack(costs, values, budget): dp [0] * (budget 1) for i in range(len(costs)): for j in range(costs[i], budget 1): dp[j] max(dp[j], dp[j - costs[i]] values[i]) return dp[budget]很多新手最大的困惑就是为什么0-1背包要倒序遍历而完全背包要正序遍历道理其实很简单。0-1背包要求每个物品最多拿一次如果正序遍历dp[j - costs[i]]可能已经包含了当前物品就会造成重复拿取完全背包本来就允许重复拿取正序遍历反倒让它可以复用当前物品的状态完成无限次的累加。如果你把遍历顺序写反0-1背包会变成完全背包完全背包会变成0-1背包而且很难通过样例发现因为小数据量下恰好能蒙对。这个点我在面试里反复问过候选人能讲清楚的人不多建议你吃透。2.3 DP做题时最容易被扣分的三个点第一初始化不对。dp数组很多题应该初始化为0但LIS这类题要初始化为1因为每个元素自身构成一个长度为1的子序列。第二取结果时取错位置。很多DP的最优解不在dp[-1]比如LIS的最优解可能在数组中间某个位置必须遍历取max。第三忽略n0或者budget0的边界。笔试环境里空输入很常见如果不写判空第一行就会抛异常。另外还有一个经验DP题写完之后一定要自己构造一个小样例手动跑一遍。比如完全背包用costs[2,3], values[3,4], budget7来测手算一下答案是8还是9。这种手动验证能帮你抓住状态转移里最隐蔽的逻辑错误。3. 字符串与滑动窗口文本处理和用户行为序列的常客字符串题在这套题里出现频率很高和爱奇艺的弹幕、搜索、内容去重业务有直接关系。这一章我选两道高频题展开最小覆盖子串和最长回文子串。这两道题在LeetCode上是经典题但在爱奇艺的卷子里被包了一层业务外壳考察点其实没变。3.1 最小覆盖子串关键词覆盖率有一道回忆版题目题干说的是给定一段弹幕文本s和一个关键词集合t假设t中只包含小写字母需要找到s中包含t所有字符的最短连续子串。去掉外壳就是LeetCode 76题。这道题是滑动窗口的经典应用。核心思路是右指针不断向右扩展窗口直到窗口内覆盖了t的所有字符然后收缩左指针找到当前右指针位置下最短的合法窗口记录答案继续移动右指针。这里需要借助一个哈希表来维护窗口内字符的缺口数量。from collections import Counter def min_window(s, t): need Counter(t) missing len(t) left 0 start 0 min_len float(inf) for right, ch in enumerate(s): if need[ch] 0: missing - 1 need[ch] - 1 if missing 0: while need[s[left]] 0: need[s[left]] 1 left 1 if right - left 1 min_len: min_len right - left 1 start left need[s[left]] 1 left 1 missing 1 return s[start:start min_len] if min_len ! float(inf) else 这道题容易错的地方有三处。第一need字典中负数的含义是当前窗口里某个字符多出来的个数收缩左指针时只移动那些need[s[left]] 0的字符第二当missing 0时表示窗口已经覆盖了t中所有字符此时再移动左指针会破坏覆盖状态所以要及时更新missing第三min_len的初值一定要设成无穷大否则窗口为空时返回结果会出错。3.2 最长回文子串中心扩展法回文串在视频场景里的应用常见于内容去重和标题对称性检测。最长回文子串这道题DP可解但中心扩展法更直观而且空间复杂度只有O(1)。思路很朴素遍历字符串的每个位置以它为中心向两边扩展同时要兼容奇数长度和偶数长度两种情况。def longest_palindrome(s): if not s: return max_len 1 start 0 for i in range(len(s)): l, r i - 1, i 1 while l 0 and r len(s) and s[l] s[r]: if r - l 1 max_len: max_len r - l 1 start l l - 1 r 1 l, r i, i 1 while l 0 and r len(s) and s[l] s[r]: if r - l 1 max_len: max_len r - l 1 start l l - 1 r 1 return s[start:start max_len]这里要注意奇数长度和偶数长度的中心是不一样的。奇数中心是单个字符偶数中心是两个相邻字符。如果你只写一个循环大概率有一半的用例过不了。3.3 字符串题的两个隐蔽坑第一个坑是Python的字符串拼接。字符串是不可变对象循环里用拼接会产生大量临时对象复杂度退化成O(n^2)。如果需要在循环里积累字符用list收集再.join()效率高出几个数量级。第二个坑是字符集范围。如果题目限定只包含小写字母可以用长度为26的数组当哈希表下标用ord(ch) - ord(a)计算速度快很多。如果没限定字符集老老实实用字典否则遇到大写字母或数字就会越界。4. 图论搜索与双指针从连通域到原地去重图论搜索在爱奇艺这套题里不是最高频的方向但隔三差五就会出现一次。双指针则更多隐藏在排序和去重类题目里。这一章我把两类放在一起讲因为它们有一个共同点模板固定但边界条件容易写错。4.1 网格连通域审核场景的“岛屿数量”我印象里有一道题题目描述的是内容审核系统给视频帧划分了网格1表示待审核区域0表示正常区域要求统计有多少个连通的待审核区域。去掉业务外壳就是LeetCode 200题岛屿数量。这道题可以用DFS、BFS或并查集解决。笔试环境里最推荐的是用栈模拟的DFS因为递归在Python里一旦遇到大矩阵很容易触发递归深度上限直接Runtime Error。下面是用显式栈的写法def num_islands(grid): if not grid: return 0 count 0 m, n len(grid), len(grid[0]) for i in range(m): for j in range(n): if grid[i][j] 1: count 1 stack [(i, j)] while stack: x, y stack.pop() if x 0 or x m or y 0 or y n or grid[x][y] ! 1: continue grid[x][y] 0 stack.append((x - 1, y)) stack.append((x 1, y)) stack.append((x, y - 1)) stack.append((x, y 1)) return count这种遍历方式有个细节每次从栈里弹出节点后要立刻把grid[x][y]置为0也就是“标记已访问”。如果不及时标记同一个节点可能被多次入栈小数据量还好大数据量直接超时。我在实际调试里遇到过这个问题加了标记之后运行时间从超时降到几十毫秒。4.2 双指针原地去重和区间合并双指针类题目在笔试里经常作为中等题的保底题出现。比如有一道题是这样的给定升序排列的视频ID数组需要原地去重并返回新的长度额外空间要求O(1)。这种题面试官可能会追问为什么两个指针的写法是O(n)的而不是O(n^2)的。def remove_duplicates(nums): if not nums: return 0 i 0 for j in range(1, len(nums)): if nums[j] ! nums[i]: i 1 nums[i] nums[j] return i 1双指针的核心思想其实很简单快指针负责遍历数组把遇到的“新元素”写到慢指针指向的位置慢指针始终指向最后一个不重复元素的下标。因为数组有序所以只要快指针的值和慢指针不同就可以确定快指针遇到了新元素。类似的还有区间合并题比如弹幕的时间段合并。给出一组区间要求合并所有重叠区间。思路是先按起始时间排序再遍历维护当前区间的终点遇到重叠就扩展终点不重叠就把当前区间加入答案。这类题的关键是先排序很多新人容易忽略这一步。4.3 搜索题里常见的优化点BFS适合求最短路径DFS适合判断存在性和连通性两者在复杂度上没有本质差别选择标准是题目要求。如果是求“最少步数”“最短路径”优先BFS如果是判断“是否存在”“共有多少块”DFS写起来更顺手。大矩阵下的连通域题目如果DFS和BFS都超时可以考虑用并查集。并查集适合动态判定连通性的场景但在笔试里写起来代码量偏大我一般只在面试聊方案时才提笔试里还是用栈模拟BFS最稳。5. 模拟题的“业务化包装”与数学思维模拟题在爱奇艺的编程题里占的比重不低而且这类题有一个显著特点逻辑不难但题干很长业务名词很多。很多人不是不会做而是被题干绕晕或者写着写着发现自己对题意理解偏了。这一章我挑两道典型题讲一讲怎么快速抽离出核心逻辑。5.1 从弹幕时间段抽象出最大并发数有一道题目的场景是弹幕系统的负载评估。给定若干弹幕的起止时间需要统计同一时刻最多有多少条弹幕同时显示。如果你直接对每条弹幕做区间相交判断复杂度是O(n^2)n超过一万就基本跑不动。正确做法是把所有开始时间和结束时间分别排序然后用两个指针扫描。遇到开始时间当前并发数加一遇到结束时间当前并发数减一。扫描过程中记录并发数的最大值。这个思路像是给一整天的弹幕事件做了个时间轴逐个事件推进状态。def max_concurrent(starts, ends): starts.sort() ends.sort() i j 0 cur 0 max_cur 0 while i len(starts): if starts[i] ends[j]: cur 1 max_cur max(max_cur, cur) i 1 else: cur - 1 j 1 return max_cur这里要注意结束时间在边界上的处理逻辑。题目如果要求“相同时间点先加后减”那么判断条件写成就是正确的如果要求“先减后加”条件要改成。考试时读清楚题目说明这种细节经常决定AC还是WA。5.2 大数运算会员积分和金额计算的底层大数运算在视频平台里的应用很直接会员积分、虚拟币、优惠券金额都可能超出普通整数范围。有一道回忆版题目就是让实现两个正整数字符串形式数字的乘法不允许直接用内置的大整数类型。大数乘法的核心思路是模拟竖式乘法用数组存放每一位的结果。两个长度分别为m和n的数字相乘结果长度最多为mn位。从低位开始逐位相乘把结果累加到对应的数组位置最后统一处理进位。def multiply(num1, num2): if num1 0 or num2 0: return 0 m, n len(num1), len(num2) res [0] * (m n) for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): mul int(num1[i]) * int(num2[j]) p1, p2 i j, i j 1 total mul res[p2] res[p1] total // 10 res[p2] total % 10 idx 0 while idx len(res) and res[idx] 0: idx 1 return .join(map(str, res[idx:]))大数乘法最容易错的地方有两个一是进位没有累加到更高位二是结果有前导零时没有跳过。我测试过很多次这两个问题在初版代码里几乎必现所以写成模板背下来是性价比很高的选择。5.3 模拟题应试技巧遇到题干的业务包装特别厚的模拟题我一般会先做三件事第一把输入输出格式用一句话写在草稿纸上避免读到一半忘记第二把题目里的业务术语翻译成数据结构术语比如“弹幕”就是“区间”“会员等级”就是“int数组”第三在代码注释里先写伪代码框架再一行行填充实现。模拟题最怕的是写着写着发现理解错了题意所以先花五分钟理清逻辑比闷头写半小时更划算。这类题的赛点不只是在编码更在阅读理解。6. 考场上最实用的应试策略与避坑清单编程题平时刷得再多到了考场上如果时间分配和边界处理没做好一样翻车。这一章我把自己在笔试和面试辅导中总结出来的一些比较实用的考场经验整理出来供大家参考。6.1 时间分配建议假设笔试一共两小时三到四道题我会这样分配时间时间段任务目标前5分钟快速浏览全部题目确定做题顺序标记难度第1题40分钟先做最有把握的题保住基本盘拿到AC第2题30分钟做中等难度题争取AC或拿到大部分用例分第3题30分钟做最难的一题写暴力版保证部分用例通过剩余15分钟检查所有题的边界修正越界、空输入、溢出等低级错误很多人在最难的一题上死磕导致前面能拿的分丢了。笔试的通过标准从来不是全对而是总分过线所以保AC优先于攻克难题。6.2 高频边界条件清单我整理了一个自己每次笔试前都会扫一遍的边界条件清单贴在便利贴上数组长度为0或1时逻辑是否成立输入包含整数、小数、负数时变量类型是否覆盖字符串包含空格、大小写混合时比较逻辑是否出错数值相加或相乘时是否会溢出int范围递归深度是否可能超过Python默认的1000层同一时间点多个事件先加还是先减如果题目没有明确说明边界输入默认处理这些情况不会扣分但如果丢了很可能是批量WA的原因。6.3 从刷题到面试问答的衔接校招面试时面试官大概率会追问算法题的核心思路为什么用这个数据结构复杂度是多少还有没有优化空间特别是爱奇艺这类视频公司面试官很喜欢问“这个算法如果应用在我们的场景里你会怎么做”。所以我刷题时有个习惯每做完一道题脑子里过一遍这个算法可以用在什么业务场景。比如滑动窗口可以用于弹幕关键词实时统计LIS可以用于用户行为路径分析并查集可以用于反作弊的社群发现。到了面试环节这些铺垫会让答案听起来更有工程感而不是背书感。最后再分享一个小经验我从2020年那届开始大量带校招学生刷题总结下来编程题拿高分的核心不是刷题数量而是每道题做完后的复盘质量。建议你拿到任何一份题单先自己限时做一遍再对照最优解法把状态定义、边界条件、复杂度三个维度写进笔记。这样刷30道题的效果比漫无目的刷100道好得多。还有一个小技巧爱奇艺这类公司的笔试环境一般是自研OJ评测机对Python版本和递归深度有限制如果题目里你想到用递归建议提前换成迭代实现。递归写起来好看但在OJ上可能因为一个深坑直接运行时错误换成显式栈或者迭代能省掉很多无谓的麻烦。祝各位笔试顺利。
