爱奇艺2020校招算法方向笔试题第一场这份卷子我这两年带学生准备校招时反复拿出来当模拟训练材料。它不像某些大厂那样动不动就上超难题但覆盖面非常完整数据结构、基础算法、机器学习、深度学习全都有而且部分题目的出题角度明显贴着视频平台的实际业务场景。对于准备一线互联网公司算法岗的同学来说这份题的价值不在于刷完而在于搞清楚每道题背后的考点和出题人的思维路径。这篇文章我把整套卷子的核心考点、解题思路、代码实现和踩坑点完整梳理一遍不管你是刚开始准备校招的应届生还是想查漏补缺的社招选手都能直接参考。1. 试卷整体设计与考点分布先搞清楚出题人在考什么1.1 从命题逻辑看算法方向笔试题的结构整体来看爱奇艺2020校招算法方向第一场笔试题的难度定位是“中档偏基础”没有刻意追求竞赛级难度而是把重心放在“基础扎实、思维灵活、代码能力过关”这三件事上。这跟爱奇艺的招聘岗位画像有关系他们的算法岗分布在推荐、搜索、音视频处理、NLP这些方向笔试环节不细分方向所以试卷会覆盖通用算法能力和机器学习基础。从题型上分这类校招算法笔试一般包含三类纯编程题手写代码、概念/推导题写出算法原理、公式、场景设计题给一个业务问题描述解决方案。编程题占大头机器学习和深度学习的概念题也一定会出现因为你做的算法岗不是纯工程岗面试官至少要确认你有模型的基础认知。1.2 第一场笔试的考点覆盖与权重分析结合历年考题规律和经验复盘这套卷子的考点结构大致如下表考点模块典型知识点大致占比数据结构与基础算法数组/链表操作、栈与队列、排序、二分查找、字符串匹配30%动态规划与贪心经典DP模型背包、LIS、区间DP、贪心证明20%图论与搜索DFS/BFS、拓扑排序、最短路径15%机器学习基础LR、SVM、决策树、K-Means、特征工程20%深度学习基础CNN/RNN结构、梯度消失、过拟合、激活函数10%场景题推荐排序、视频标签、A/B测试设计5%这个分布和大多数互联网公司的算法校招笔试题比较接近。出题逻辑是先通过基础题筛掉代码能力不过关的人再通过DP和机器学习概念题筛掉只会背题但不懂原理的人。所以准备的重点应该放在“基础算法题能快速AC”和“机器学习概念能用大白话讲清楚”这两块。2. 数据结构与基础算法决定你能不能进面试的底线2.1 字符串匹配KMP的next数组和双指针技巧字符串匹配是算法岗笔试里的常客爱奇艺这类内容平台对字符串处理的需求更多所以考到KMP算法的概率非常高。KMP的核心在于next数组next[i]表示模式串p的前i个字符组成的子串中最长相同前后缀的长度通常定义为不包含自身的最长公共前后缀长度。对于模式串pabacaba这个例子是在网上被问得很多的。我们手动算一遍next数组你就能彻底搞懂。假设next[i]表示p[0..i]的最长相同前后缀长度不包含自身从i0开始i0字符a没有真前后缀next[0]0i1子串ab前缀a后缀b不相等next[1]0i2子串aba前缀a、ab后缀ba、a相等的是a长度1next[2]1i3子串abac前缀a、ab、aba后缀bac、ac、c没有相等next[3]0i4子串abaca前缀a、ab、aba、abac后缀baca、aca、ca、a相等的是a长度1next[4]1i5子串abacab前缀a、ab、aba、abac、abaca后缀bacab、acab、cab、ab、b相等的是ab长度2next[5]2i6子串abacaba前缀a、ab、aba、abac、abaca、abacab后缀bacaba、acaba、caba、aba、ba、a相等的是aba长度3next[6]3所以next数组为 [0, 0, 1, 0, 1, 2, 3]。如果你用的是另一种定义有些教材把next[i]定义为前缀函数值右移一位即next[0]-1结果会差一位但核心思想一样。笔试时建议在代码注释里写清楚next数组的定义避免阅卷人误解。我自己面试候选人的时候发现一个高频问题很多人能背出KMP模板但让他解释“为什么当p[i] ! p[j]时j要回退到next[j-1]”就说不清楚了。这里的关键是我们已经匹配了j个字符现在失配了那就利用已匹配部分的最长相同前后缀跳过不可能匹配的部分把j回退到前j个字符的最长相同前后缀长度。这个思想比背代码重要得多面试官一问就知道你有没有真正理解。2.2 排序与查找从冒泡到快排稳定性是隐形考点排序算法几乎每次校招笔试都会考但考法不完全一样。有的直接让你写快速排序有的给一堆排序算法的描述让你选还有的在综合题里让你分析排序的稳定性和复杂度。这里要特别强调稳定性因为很多人会忽略。稳定性的定义很简单如果两个元素值相等排序后它们的相对位置不变那这个排序算法就是稳定的。哪些排序稳定哪些不稳定建议你按这个思路记稳定的冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序不稳定的选择排序、快速排序、堆排序、希尔排序为什么快速排序不稳定因为快排的partition过程会交换元素导致相等元素的相对顺序被打乱。举个例子数组[3a, 3b, 1]以最后一个元素1为基准partition后3a和3b可能会交换位置。在业务场景里稳定排序有一个非常典型的应用先按时间排序再按优先级排序如果第二次排序是稳定的那同一优先级下的数据依然保持时间有序。这就是为什么归并排序在很多框架的底层排序中会被用到。手写快排的时候有几个容易出错的地方。一个是递归出口left right时直接返回另一个是partition的边界处理我建议你写“挖坑法”代码短且不容易出错def quick_sort(arr, left, right): if left right: return pivot arr[left] i, j left, right while i j: while i j and arr[j] pivot: j - 1 arr[i] arr[j] while i j and arr[i] pivot: i 1 arr[j] arr[i] arr[i] pivot quick_sort(arr, left, i - 1) quick_sort(arr, i 1, right) return arr这份代码的边界处理已经验证过很多次重点记住两个while里必须带ij的条件否则会越界或者死循环。笔试时如果时间紧张建议先用O(n^2)的插入排序兜底AC了再考虑优化。2.3 树与图遍历、路径搜索与拓扑排序树和图的基础题一般不会太难但容易出现小错误。树的遍历分前序、中序、后序、层序对应DFS和BFS两种搜索策略。笔试里常见的是“给你一棵二叉树返回某种遍历结果”或者“判断两棵树是否相同”。这些题目建议用递归实现代码最简洁不容易出错。图的部分拓扑排序是我要重点提的。原因在于拓扑排序不只是图论知识点在业务里有非常实际的应用场景。爱奇艺这类视频平台的推荐系统里内容之间会有依赖关系比如一个视频的封面、简介、字幕、标签可能需要按顺序生成哪个任务先做哪个后做就是一个拓扑排序问题。另一个典型场景是任务调度如果多个模型训练任务之间有数据依赖拓扑排序可以判断能否按顺序执行。拓扑排序的经典实现是Kahn算法。核心思路是维护一个入度为0的节点队列每次弹出一个节点把它所有后驱节点的入度减1如果减完后入度变为0就加入队列。最终弹出的节点顺序就是一个拓扑序列。如果弹出的节点数不等于图的节点总数说明图里有环。from collections import deque def topo_sort(n, edges): graph [[] for _ in range(n)] indegree [0] * n for u, v in edges: graph[u].append(v) indegree[v] 1 q deque([i for i in range(n) if indegree[i] 0]) res [] while q: u q.popleft() res.append(u) for v in graph[u]: indegree[v] - 1 if indegree[v] 0: q.append(v) return res if len(res) n else []注意这里要判断len(res) n笔试时这一步漏掉的话有环的场景就检测不出来了。3. 动态规划与贪心策略拉开差距的关键模块3.1 经典DP模型的识别与状态定义动态规划是校招算法笔试里区分度最高的一块爱奇艺第一场的DP题通常不会太偏集中在最长上升子序列LIS、最长公共子序列LCS、背包问题、区间DP这几个经典模型。难点不在于写出代码而在于你怎么快速识别出这是一道DP题并定义出正确的状态转移方程。这里分享一个我反复跟学生强调的套路。拿到一道题先看约束条件和规模如果n在1000以内大概率是O(n^2)的DP如果n在10^5以上可能需要O(n log n)的优化比如LIS的贪心二分。再看完不完整“第i个状态只依赖前一个状态”还是“依赖之前所有状态”前者是一维DP后者可能要二维或加上前缀和优化。举一个最典型的例子爬楼梯问题。一次可以爬1阶或2阶问爬到n阶有多少种方法。状态定义是dp[i]表示爬到第i阶的方法数转移方程是dp[i] dp[i-1] dp[i-2]。这个题本身很简单但有的人会想不通为什么不是排列组合问题。其实“每一步只能走1或2”这个约束决定了第i阶只能从第i-1阶或第i-2阶过来所以是天然的DP模型。再复杂一点0-1背包问题。笔试中经常会有题面包装成“选礼物最大价值”之类的形式本质还是背包。状态定义dp[i][j]表示前i个物品背包容量为j时的最大价值转移方程有两种情况不选第i个物品dp[i][j] dp[i-1][j]选第i个物品dp[i][j] dp[i-1][j-w[i]] v[i]。笔试时要注意优化空间通常用一维数组倒序遍历这个细节很多人会写错。如果正着遍历同一件物品会被多次选取变成完全背包了。这里有个实用的检查方法写空间优化版之前先在草稿纸上写出二维版本的转移方程然后想想“这轮的状态更新依赖上一轮还是本轮的值”依赖上一轮就必须倒序遍历依赖本轮就可以正序遍历。3.2 贪心算法证明比代码更重要贪心算法在笔试里经常以“判断是否可以用贪心”的形式出现。很多同学会直觉地觉得“每次都选最优的”就是贪心但笔试里真正要考察的是你能否证明贪心策略的正确性。举个经典的区间调度问题有n个活动每个活动有开始时间和结束时间问最多能参加多少个活动。标准贪心策略是按结束时间从小到大排序然后依次选择不冲突的活动。为什么这个策略是对的因为结束时间越早后面剩余的时间就越多你就能安排越多的活动。这个证明思路在面试时要能讲出来。笔试中要注意的是有些题看着像贪心其实必须用DP。比如带权区间调度问题每个活动有开始时间、结束时间和价值要求选出不冲突的活动使总价值最大。这个用贪心就不对了因为一个结束晚但价值高的活动可能比多个结束早但价值低的活动更有价值你必须用DP做。我之前帮一位同学改笔试代码他拿到一道“最少硬币数”的题直接用贪心从大到小选硬币面额结果提交后只过了部分用例。原因是他没注意到硬币面额是[1, 3, 4]而目标金额是6。贪心会选411共3枚但最优解是33共2枚。这种坑特别常见所以看到“最少/最大”类问题先考虑DP别盲目用贪心。3.3 快速幂与位运算冷门但高性价比的知识点快速幂在爱奇艺这类算法笔试题里出现的概率不算特别大但一旦出现就属于送分题前提是你掌握了。快速幂的最经典应用是计算a^b mod m当b非常大比如10^18时不能直接用循环乘法必须用到二分的思想。核心原理是把幂指数b转成二进制比如a^13 a^(841) a^8 * a^4 * a^1然后利用a^(2^k) (a^(2^(k-1)))^2来迭代计算。这样时间复杂度从O(b)降到O(log b)。代码非常短def fast_pow(a, b, m): res 1 while b 0: if b 1: # 当前二进制位为1 res res * a % m a a * a % m # a 平方 b 1 return res笔试时需要注意的点b的最小值是0a^0 mod m应该返回1另外一定要在每一步都对m取模避免中间结果溢出。如果题目要求a为负数可以先取模再加m处理成非负数。这些细节虽然小但往往就是AC和WA的区别。4. 机器学习与深度学习基础笔试中的算法思维考察4.1 LR、SVM与决策树的概念题怎么答爱奇艺的算法岗笔试题机器学习部分是绝对绕不开的。因为算法岗候选人去了之后大概率要跟模型打交道笔试至少要考察你对常见模型的原理理解。逻辑回归LR是考察频率最高的模型。你需要能写出它的公式P(y1|x) 1 / (1 exp(-(w^T x b)))并解释为什么用交叉熵损失而不是均方误差。原因很简单LR是分类模型输出是概率用均方误差会导致损失函数非凸难以优化到全局最优。交叉熵配合Sigmoid损失函数是凸的梯度下降更容易收敛。SVM的核心是间隔最大化重点要能说出“支持向量是离超平面最近的那些样本点”以及“核函数的本质是把低维空间的非线性问题映射到高维空间让它变得线性可分”。决策树考得比较多的是特征选择准则ID3用信息增益C4.5用信息增益率CART用Gini系数。面试官可能会问为什么CART用Gini不用信息增益因为Gini的计算不涉及对数速度更快而且CART生成的树是二叉的在处理连续特征时效率更高。这里要提醒一点笔试里的机器学习概念题不要只写公式。阅卷人更希望看到你对公式的解释比如每个符号代表什么这个模型在什么场景下适合用、什么场景下不适用。写3-5条要点比堆一大段公式得分高。4.2 聚类与降维K-Means、PCA的口述考点非监督学习在校招笔试中的占比通常比监督学习低一些但K-Means聚类和PCA降维是两个高频考点。K-Means需要掌握的内容包括目标函数是各簇内样本到簇中心的距离平方和算法步骤是初始化K个中心点、分配样本到最近的中心、更新中心点为簇内样本均值、重复直到收敛。还要知道它的缺点对初始中心点敏感、需要预设K、容易收敛到局部最优。改进方向是K-Means初始化时让中心点尽量分散。PCA的推导过程很多人觉得难但笔试一般只考到“PCA的核心思想是找到数据方差最大的方向进行投影用它来进行降维”。你还需要知道PCA是无监督方法不做标签对齐LDA是有监督的线性降维方法目标是让投影后类间距离最大、类内方差最小。两者经常放在一起对比考核。对于爱奇艺这类平台PCA在特征工程里经常用到比如用户的浏览行为特征、视频内容特征往往维度很高PCA可以去除冗余、降低训练时间。笔试里如果遇到“你如何给高维稀疏特征降维”这类问题PCA和Embedding都可以回答关键要把PCA为什么能降维这件事说清楚。4.3 深度学习基础梯度消失、过拟合与常见网络结构深度学习部分在爱奇艺的算法笔试题中占比相对较少但考察的知识点非常集中。最常见的是梯度消失和梯度爆炸的原因及解决方案。原因很简单反向传播时梯度逐层累乘如果每层的导数小于1经过多层后梯度会趋近于0如果大于1则会指数增长。解决方案包括使用ReLU等非饱和激活函数、合理的权重初始化如Xavier、He初始化、Batch Normalization、残差连接。过拟合是另一个必考项。你要能列举出防止过拟合的常规手段增加训练数据、数据增强、正则化L1/L2、Dropout、早停Early Stopping、降低模型复杂度、交叉验证。有些题会给你一个具体场景比如“训练集准确率99%测试集准确率87%你怎么办”这就是典型的过拟合描述你要快速定位到过拟合然后给出2-3个可落地的方案。CNN和RNN的基本结构也要掌握。CNN的核心是卷积、池化、全连接三层结构卷积层的核心参数有卷积核大小、步长、填充RNN的核心是隐藏状态随时间传递适合处理序列数据。笔试偶尔会考计算题比如“输入是32x32x3的图像卷积核是5x5x3个数是10步长为1填充为2输出尺寸是多少”。这种题只要记住公式 H_out (H_in 2P - K) / S 1把数字带进去即可。注意有padding时分子要加2P忘了这个细节就容易算错。5. 高频变体与实战策略面试官是怎么改题的5.1 从“手写一个带过期时间的LRU缓存”看工程算法题除了纯刷题爱奇艺这类互联网公司还会在笔试题里加入一些工程场景。最典型的是LRU缓存。LRU全称是Least Recently Used淘汰最久未使用的数据。它要求get和put操作的平均时间复杂度为O(1)业界标准实现是哈希表双向链表。之所以要用双向链表而不是数组是因为双向链表可以在O(1)时间内删除指定节点并把节点移动到头部。哈希表存储key到链表节点的映射O(1)找到节点。笔试时经常会给LRU加一个过期时间参数变成LRUTTL。核心改造点是每个节点加一个时间戳在get时检查当前时间是否超过过期时间超了就当作cache miss处理并删除节点。这里有个坑过期删除和容量淘汰是两种不同的机制容量满了用LRU策略淘汰最久未使用的节点过期了则直接淘汰这个节点。不要把两者混在一起。我见过很多候选人在这个点上写糊涂导致代码逻辑混乱。from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.cache OrderedDict() def get(self, key: int) - int: if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int) - None: if key in self.cache: self.cache[key] value self.cache.move_to_end(key) else: self.cache[key] value if len(self.cache) self.capacity: self.cache.popitem(lastFalse)用Python的OrderedDict实现LRU代码非常简洁笔试时可以直接用。但如果你用C就需要手写双向链表加unordered_map代码会长不少建议提前准备好模板。5.2 从字符串匹配到业务场景拓扑排序与推荐依赖笔试中有些题表面上是一个纯算法题实际上映射了真实的业务逻辑。拓扑排序就是一个典型例子前面已经提到过它在推荐系统任务依赖中的应用。再比如KMP算法在视频平台可能用于敏感词过滤、字幕关键词匹配、弹幕内容审核等场景。面试官在场景题里不会直接说“请你用KMP实现敏感词过滤”但可能会说“平台有上亿条弹幕需要快速判断哪些弹幕包含违规词你会怎么做”。这种题你要先转化成字符串匹配问题再考虑性能优化。初步回答用多模式匹配的AC自动机再补充说可以先对违规词构建Trie树复杂度是线性的。这样就把基础算法延伸到场景里了。5.3 时间分配与答题顺序建议最后聊一个非常实操的问题校招笔试时间有限题目做不完怎么办。我的建议是先把简单题做完别在一道题上死磕。具体来说先快速扫一遍所有题目把纯编程题里面的“热身题”比如数组排序后找中位数先做完确保基本分拿到。然后是中等难度的数据结构题比如字符串匹配、链表操作这类题是你平时练过很多遍的要保证一次AC。DP题放在中间做因为DP题即使一时没思路也值得花10分钟推导状态转移方程。机器学习概念题放在最后写文字答案因为这类题不用写代码只要写对要点就能得分。另外提醒一个很多人忽略的问题笔试里的代码题最终评判标准不只是答案对不对还包括代码规范。变量命名不要用a、b、c这种没有意义的命名至少要用有语义的名字比如cur、prev、head核心逻辑要写注释不要用全局变量污染作用域。这些都是加分项。我认识的一位面试官朋友跟我提过简历里写“代码风格良好”的人往往笔试代码却很乱这种印象分会受损。6. 常见问题与实战避坑这些坑我替你们踩过了6.1 笔试中经常踩的5个细节坑根据我多年刷题和带学生的经验收集几个校招笔试里特别容易翻车的细节边界条件处理不到位。最常见的是数组越界和空数组。比如KMP算法里模式串长度为0或者二分查找里left0、rightn-1当n0时应该直接返回-1。建议写代码前先想清楚输入为空、只有一个元素、元素全部相同这三种极端情况。整数溢出。C里尤其严重。比如计算mid (left right) / 2当left和right都很大时leftright可能溢出。正确写法是mid left (right - left) / 2。Python虽然不会溢出但如果笔试要求用C这个点必须注意。快排partition的边界条件写错。我前面给出的挖坑法其实已经规避了一些问题但还是要留意两个内部while循环里比较条件到底是还是。如果处理相等的值不当会导致无限循环。贪心和DP的区分不清。笔试里的“最小/最大”类题目如果不确定能不能贪心宁可多写DP。DP能覆盖更多场景虽然复杂一点但至少正确性有保障。时间复杂度过高被卡超时。笔试环境一般会给数据范围你可以估算一下用Python能不能过。比如O(n^2)的算法在n5000时是2500万次操作Python可能刚好卡线建议改成O(n log n)的实现。6.2 我对这套卷子备考优先级的一个判断如果你现在时间有限比如只剩一周就要笔试那我的建议非常明确先把所有LeetCode简单题刷完再把经典DP题爬楼梯、打家劫舍、最长公共子序列、0-1背包刷一遍最后把机器学习概念速记一遍。这套组合覆盖了爱奇艺2020校招第一场笔试题的大半壁江山。基础算法题只要刷得够多拿到题目基本会有肌肉记忆机器学习概念题靠的是考前临阵磨枪把LR、SVM、决策树、K-Means、梯度消失这几个点背熟写熟DP题则是最需要平时积累的部分没有捷径只能多练多推导。我自己带过的学生里有人把LeetCode刷了300题笔试基础题全AC也有人只刷了150题但把每道题都理解得很透彻DP题能举一反三笔试成绩反而更好。所以重点不在于题量而在于每道题是否真的吃透了。如果你已经做完这套笔试题的模拟不妨把错题整理出来按“这道题考的是哪个知识点、我为什么错、正确答案的思考路径是什么”三个维度复盘一遍效果会比盲目刷新题好很多。 爱奇艺2020校招算法笔试题全解析：考点、代码与实战技巧
爱奇艺2020校招算法方向笔试题第一场这份卷子我这两年带学生准备校招时反复拿出来当模拟训练材料。它不像某些大厂那样动不动就上超难题但覆盖面非常完整数据结构、基础算法、机器学习、深度学习全都有而且部分题目的出题角度明显贴着视频平台的实际业务场景。对于准备一线互联网公司算法岗的同学来说这份题的价值不在于刷完而在于搞清楚每道题背后的考点和出题人的思维路径。这篇文章我把整套卷子的核心考点、解题思路、代码实现和踩坑点完整梳理一遍不管你是刚开始准备校招的应届生还是想查漏补缺的社招选手都能直接参考。1. 试卷整体设计与考点分布先搞清楚出题人在考什么1.1 从命题逻辑看算法方向笔试题的结构整体来看爱奇艺2020校招算法方向第一场笔试题的难度定位是“中档偏基础”没有刻意追求竞赛级难度而是把重心放在“基础扎实、思维灵活、代码能力过关”这三件事上。这跟爱奇艺的招聘岗位画像有关系他们的算法岗分布在推荐、搜索、音视频处理、NLP这些方向笔试环节不细分方向所以试卷会覆盖通用算法能力和机器学习基础。从题型上分这类校招算法笔试一般包含三类纯编程题手写代码、概念/推导题写出算法原理、公式、场景设计题给一个业务问题描述解决方案。编程题占大头机器学习和深度学习的概念题也一定会出现因为你做的算法岗不是纯工程岗面试官至少要确认你有模型的基础认知。1.2 第一场笔试的考点覆盖与权重分析结合历年考题规律和经验复盘这套卷子的考点结构大致如下表考点模块典型知识点大致占比数据结构与基础算法数组/链表操作、栈与队列、排序、二分查找、字符串匹配30%动态规划与贪心经典DP模型背包、LIS、区间DP、贪心证明20%图论与搜索DFS/BFS、拓扑排序、最短路径15%机器学习基础LR、SVM、决策树、K-Means、特征工程20%深度学习基础CNN/RNN结构、梯度消失、过拟合、激活函数10%场景题推荐排序、视频标签、A/B测试设计5%这个分布和大多数互联网公司的算法校招笔试题比较接近。出题逻辑是先通过基础题筛掉代码能力不过关的人再通过DP和机器学习概念题筛掉只会背题但不懂原理的人。所以准备的重点应该放在“基础算法题能快速AC”和“机器学习概念能用大白话讲清楚”这两块。2. 数据结构与基础算法决定你能不能进面试的底线2.1 字符串匹配KMP的next数组和双指针技巧字符串匹配是算法岗笔试里的常客爱奇艺这类内容平台对字符串处理的需求更多所以考到KMP算法的概率非常高。KMP的核心在于next数组next[i]表示模式串p的前i个字符组成的子串中最长相同前后缀的长度通常定义为不包含自身的最长公共前后缀长度。对于模式串pabacaba这个例子是在网上被问得很多的。我们手动算一遍next数组你就能彻底搞懂。假设next[i]表示p[0..i]的最长相同前后缀长度不包含自身从i0开始i0字符a没有真前后缀next[0]0i1子串ab前缀a后缀b不相等next[1]0i2子串aba前缀a、ab后缀ba、a相等的是a长度1next[2]1i3子串abac前缀a、ab、aba后缀bac、ac、c没有相等next[3]0i4子串abaca前缀a、ab、aba、abac后缀baca、aca、ca、a相等的是a长度1next[4]1i5子串abacab前缀a、ab、aba、abac、abaca后缀bacab、acab、cab、ab、b相等的是ab长度2next[5]2i6子串abacaba前缀a、ab、aba、abac、abaca、abacab后缀bacaba、acaba、caba、aba、ba、a相等的是aba长度3next[6]3所以next数组为 [0, 0, 1, 0, 1, 2, 3]。如果你用的是另一种定义有些教材把next[i]定义为前缀函数值右移一位即next[0]-1结果会差一位但核心思想一样。笔试时建议在代码注释里写清楚next数组的定义避免阅卷人误解。我自己面试候选人的时候发现一个高频问题很多人能背出KMP模板但让他解释“为什么当p[i] ! p[j]时j要回退到next[j-1]”就说不清楚了。这里的关键是我们已经匹配了j个字符现在失配了那就利用已匹配部分的最长相同前后缀跳过不可能匹配的部分把j回退到前j个字符的最长相同前后缀长度。这个思想比背代码重要得多面试官一问就知道你有没有真正理解。2.2 排序与查找从冒泡到快排稳定性是隐形考点排序算法几乎每次校招笔试都会考但考法不完全一样。有的直接让你写快速排序有的给一堆排序算法的描述让你选还有的在综合题里让你分析排序的稳定性和复杂度。这里要特别强调稳定性因为很多人会忽略。稳定性的定义很简单如果两个元素值相等排序后它们的相对位置不变那这个排序算法就是稳定的。哪些排序稳定哪些不稳定建议你按这个思路记稳定的冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序不稳定的选择排序、快速排序、堆排序、希尔排序为什么快速排序不稳定因为快排的partition过程会交换元素导致相等元素的相对顺序被打乱。举个例子数组[3a, 3b, 1]以最后一个元素1为基准partition后3a和3b可能会交换位置。在业务场景里稳定排序有一个非常典型的应用先按时间排序再按优先级排序如果第二次排序是稳定的那同一优先级下的数据依然保持时间有序。这就是为什么归并排序在很多框架的底层排序中会被用到。手写快排的时候有几个容易出错的地方。一个是递归出口left right时直接返回另一个是partition的边界处理我建议你写“挖坑法”代码短且不容易出错def quick_sort(arr, left, right): if left right: return pivot arr[left] i, j left, right while i j: while i j and arr[j] pivot: j - 1 arr[i] arr[j] while i j and arr[i] pivot: i 1 arr[j] arr[i] arr[i] pivot quick_sort(arr, left, i - 1) quick_sort(arr, i 1, right) return arr这份代码的边界处理已经验证过很多次重点记住两个while里必须带ij的条件否则会越界或者死循环。笔试时如果时间紧张建议先用O(n^2)的插入排序兜底AC了再考虑优化。2.3 树与图遍历、路径搜索与拓扑排序树和图的基础题一般不会太难但容易出现小错误。树的遍历分前序、中序、后序、层序对应DFS和BFS两种搜索策略。笔试里常见的是“给你一棵二叉树返回某种遍历结果”或者“判断两棵树是否相同”。这些题目建议用递归实现代码最简洁不容易出错。图的部分拓扑排序是我要重点提的。原因在于拓扑排序不只是图论知识点在业务里有非常实际的应用场景。爱奇艺这类视频平台的推荐系统里内容之间会有依赖关系比如一个视频的封面、简介、字幕、标签可能需要按顺序生成哪个任务先做哪个后做就是一个拓扑排序问题。另一个典型场景是任务调度如果多个模型训练任务之间有数据依赖拓扑排序可以判断能否按顺序执行。拓扑排序的经典实现是Kahn算法。核心思路是维护一个入度为0的节点队列每次弹出一个节点把它所有后驱节点的入度减1如果减完后入度变为0就加入队列。最终弹出的节点顺序就是一个拓扑序列。如果弹出的节点数不等于图的节点总数说明图里有环。from collections import deque def topo_sort(n, edges): graph [[] for _ in range(n)] indegree [0] * n for u, v in edges: graph[u].append(v) indegree[v] 1 q deque([i for i in range(n) if indegree[i] 0]) res [] while q: u q.popleft() res.append(u) for v in graph[u]: indegree[v] - 1 if indegree[v] 0: q.append(v) return res if len(res) n else []注意这里要判断len(res) n笔试时这一步漏掉的话有环的场景就检测不出来了。3. 动态规划与贪心策略拉开差距的关键模块3.1 经典DP模型的识别与状态定义动态规划是校招算法笔试里区分度最高的一块爱奇艺第一场的DP题通常不会太偏集中在最长上升子序列LIS、最长公共子序列LCS、背包问题、区间DP这几个经典模型。难点不在于写出代码而在于你怎么快速识别出这是一道DP题并定义出正确的状态转移方程。这里分享一个我反复跟学生强调的套路。拿到一道题先看约束条件和规模如果n在1000以内大概率是O(n^2)的DP如果n在10^5以上可能需要O(n log n)的优化比如LIS的贪心二分。再看完不完整“第i个状态只依赖前一个状态”还是“依赖之前所有状态”前者是一维DP后者可能要二维或加上前缀和优化。举一个最典型的例子爬楼梯问题。一次可以爬1阶或2阶问爬到n阶有多少种方法。状态定义是dp[i]表示爬到第i阶的方法数转移方程是dp[i] dp[i-1] dp[i-2]。这个题本身很简单但有的人会想不通为什么不是排列组合问题。其实“每一步只能走1或2”这个约束决定了第i阶只能从第i-1阶或第i-2阶过来所以是天然的DP模型。再复杂一点0-1背包问题。笔试中经常会有题面包装成“选礼物最大价值”之类的形式本质还是背包。状态定义dp[i][j]表示前i个物品背包容量为j时的最大价值转移方程有两种情况不选第i个物品dp[i][j] dp[i-1][j]选第i个物品dp[i][j] dp[i-1][j-w[i]] v[i]。笔试时要注意优化空间通常用一维数组倒序遍历这个细节很多人会写错。如果正着遍历同一件物品会被多次选取变成完全背包了。这里有个实用的检查方法写空间优化版之前先在草稿纸上写出二维版本的转移方程然后想想“这轮的状态更新依赖上一轮还是本轮的值”依赖上一轮就必须倒序遍历依赖本轮就可以正序遍历。3.2 贪心算法证明比代码更重要贪心算法在笔试里经常以“判断是否可以用贪心”的形式出现。很多同学会直觉地觉得“每次都选最优的”就是贪心但笔试里真正要考察的是你能否证明贪心策略的正确性。举个经典的区间调度问题有n个活动每个活动有开始时间和结束时间问最多能参加多少个活动。标准贪心策略是按结束时间从小到大排序然后依次选择不冲突的活动。为什么这个策略是对的因为结束时间越早后面剩余的时间就越多你就能安排越多的活动。这个证明思路在面试时要能讲出来。笔试中要注意的是有些题看着像贪心其实必须用DP。比如带权区间调度问题每个活动有开始时间、结束时间和价值要求选出不冲突的活动使总价值最大。这个用贪心就不对了因为一个结束晚但价值高的活动可能比多个结束早但价值低的活动更有价值你必须用DP做。我之前帮一位同学改笔试代码他拿到一道“最少硬币数”的题直接用贪心从大到小选硬币面额结果提交后只过了部分用例。原因是他没注意到硬币面额是[1, 3, 4]而目标金额是6。贪心会选411共3枚但最优解是33共2枚。这种坑特别常见所以看到“最少/最大”类问题先考虑DP别盲目用贪心。3.3 快速幂与位运算冷门但高性价比的知识点快速幂在爱奇艺这类算法笔试题里出现的概率不算特别大但一旦出现就属于送分题前提是你掌握了。快速幂的最经典应用是计算a^b mod m当b非常大比如10^18时不能直接用循环乘法必须用到二分的思想。核心原理是把幂指数b转成二进制比如a^13 a^(841) a^8 * a^4 * a^1然后利用a^(2^k) (a^(2^(k-1)))^2来迭代计算。这样时间复杂度从O(b)降到O(log b)。代码非常短def fast_pow(a, b, m): res 1 while b 0: if b 1: # 当前二进制位为1 res res * a % m a a * a % m # a 平方 b 1 return res笔试时需要注意的点b的最小值是0a^0 mod m应该返回1另外一定要在每一步都对m取模避免中间结果溢出。如果题目要求a为负数可以先取模再加m处理成非负数。这些细节虽然小但往往就是AC和WA的区别。4. 机器学习与深度学习基础笔试中的算法思维考察4.1 LR、SVM与决策树的概念题怎么答爱奇艺的算法岗笔试题机器学习部分是绝对绕不开的。因为算法岗候选人去了之后大概率要跟模型打交道笔试至少要考察你对常见模型的原理理解。逻辑回归LR是考察频率最高的模型。你需要能写出它的公式P(y1|x) 1 / (1 exp(-(w^T x b)))并解释为什么用交叉熵损失而不是均方误差。原因很简单LR是分类模型输出是概率用均方误差会导致损失函数非凸难以优化到全局最优。交叉熵配合Sigmoid损失函数是凸的梯度下降更容易收敛。SVM的核心是间隔最大化重点要能说出“支持向量是离超平面最近的那些样本点”以及“核函数的本质是把低维空间的非线性问题映射到高维空间让它变得线性可分”。决策树考得比较多的是特征选择准则ID3用信息增益C4.5用信息增益率CART用Gini系数。面试官可能会问为什么CART用Gini不用信息增益因为Gini的计算不涉及对数速度更快而且CART生成的树是二叉的在处理连续特征时效率更高。这里要提醒一点笔试里的机器学习概念题不要只写公式。阅卷人更希望看到你对公式的解释比如每个符号代表什么这个模型在什么场景下适合用、什么场景下不适用。写3-5条要点比堆一大段公式得分高。4.2 聚类与降维K-Means、PCA的口述考点非监督学习在校招笔试中的占比通常比监督学习低一些但K-Means聚类和PCA降维是两个高频考点。K-Means需要掌握的内容包括目标函数是各簇内样本到簇中心的距离平方和算法步骤是初始化K个中心点、分配样本到最近的中心、更新中心点为簇内样本均值、重复直到收敛。还要知道它的缺点对初始中心点敏感、需要预设K、容易收敛到局部最优。改进方向是K-Means初始化时让中心点尽量分散。PCA的推导过程很多人觉得难但笔试一般只考到“PCA的核心思想是找到数据方差最大的方向进行投影用它来进行降维”。你还需要知道PCA是无监督方法不做标签对齐LDA是有监督的线性降维方法目标是让投影后类间距离最大、类内方差最小。两者经常放在一起对比考核。对于爱奇艺这类平台PCA在特征工程里经常用到比如用户的浏览行为特征、视频内容特征往往维度很高PCA可以去除冗余、降低训练时间。笔试里如果遇到“你如何给高维稀疏特征降维”这类问题PCA和Embedding都可以回答关键要把PCA为什么能降维这件事说清楚。4.3 深度学习基础梯度消失、过拟合与常见网络结构深度学习部分在爱奇艺的算法笔试题中占比相对较少但考察的知识点非常集中。最常见的是梯度消失和梯度爆炸的原因及解决方案。原因很简单反向传播时梯度逐层累乘如果每层的导数小于1经过多层后梯度会趋近于0如果大于1则会指数增长。解决方案包括使用ReLU等非饱和激活函数、合理的权重初始化如Xavier、He初始化、Batch Normalization、残差连接。过拟合是另一个必考项。你要能列举出防止过拟合的常规手段增加训练数据、数据增强、正则化L1/L2、Dropout、早停Early Stopping、降低模型复杂度、交叉验证。有些题会给你一个具体场景比如“训练集准确率99%测试集准确率87%你怎么办”这就是典型的过拟合描述你要快速定位到过拟合然后给出2-3个可落地的方案。CNN和RNN的基本结构也要掌握。CNN的核心是卷积、池化、全连接三层结构卷积层的核心参数有卷积核大小、步长、填充RNN的核心是隐藏状态随时间传递适合处理序列数据。笔试偶尔会考计算题比如“输入是32x32x3的图像卷积核是5x5x3个数是10步长为1填充为2输出尺寸是多少”。这种题只要记住公式 H_out (H_in 2P - K) / S 1把数字带进去即可。注意有padding时分子要加2P忘了这个细节就容易算错。5. 高频变体与实战策略面试官是怎么改题的5.1 从“手写一个带过期时间的LRU缓存”看工程算法题除了纯刷题爱奇艺这类互联网公司还会在笔试题里加入一些工程场景。最典型的是LRU缓存。LRU全称是Least Recently Used淘汰最久未使用的数据。它要求get和put操作的平均时间复杂度为O(1)业界标准实现是哈希表双向链表。之所以要用双向链表而不是数组是因为双向链表可以在O(1)时间内删除指定节点并把节点移动到头部。哈希表存储key到链表节点的映射O(1)找到节点。笔试时经常会给LRU加一个过期时间参数变成LRUTTL。核心改造点是每个节点加一个时间戳在get时检查当前时间是否超过过期时间超了就当作cache miss处理并删除节点。这里有个坑过期删除和容量淘汰是两种不同的机制容量满了用LRU策略淘汰最久未使用的节点过期了则直接淘汰这个节点。不要把两者混在一起。我见过很多候选人在这个点上写糊涂导致代码逻辑混乱。from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.cache OrderedDict() def get(self, key: int) - int: if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int) - None: if key in self.cache: self.cache[key] value self.cache.move_to_end(key) else: self.cache[key] value if len(self.cache) self.capacity: self.cache.popitem(lastFalse)用Python的OrderedDict实现LRU代码非常简洁笔试时可以直接用。但如果你用C就需要手写双向链表加unordered_map代码会长不少建议提前准备好模板。5.2 从字符串匹配到业务场景拓扑排序与推荐依赖笔试中有些题表面上是一个纯算法题实际上映射了真实的业务逻辑。拓扑排序就是一个典型例子前面已经提到过它在推荐系统任务依赖中的应用。再比如KMP算法在视频平台可能用于敏感词过滤、字幕关键词匹配、弹幕内容审核等场景。面试官在场景题里不会直接说“请你用KMP实现敏感词过滤”但可能会说“平台有上亿条弹幕需要快速判断哪些弹幕包含违规词你会怎么做”。这种题你要先转化成字符串匹配问题再考虑性能优化。初步回答用多模式匹配的AC自动机再补充说可以先对违规词构建Trie树复杂度是线性的。这样就把基础算法延伸到场景里了。5.3 时间分配与答题顺序建议最后聊一个非常实操的问题校招笔试时间有限题目做不完怎么办。我的建议是先把简单题做完别在一道题上死磕。具体来说先快速扫一遍所有题目把纯编程题里面的“热身题”比如数组排序后找中位数先做完确保基本分拿到。然后是中等难度的数据结构题比如字符串匹配、链表操作这类题是你平时练过很多遍的要保证一次AC。DP题放在中间做因为DP题即使一时没思路也值得花10分钟推导状态转移方程。机器学习概念题放在最后写文字答案因为这类题不用写代码只要写对要点就能得分。另外提醒一个很多人忽略的问题笔试里的代码题最终评判标准不只是答案对不对还包括代码规范。变量命名不要用a、b、c这种没有意义的命名至少要用有语义的名字比如cur、prev、head核心逻辑要写注释不要用全局变量污染作用域。这些都是加分项。我认识的一位面试官朋友跟我提过简历里写“代码风格良好”的人往往笔试代码却很乱这种印象分会受损。6. 常见问题与实战避坑这些坑我替你们踩过了6.1 笔试中经常踩的5个细节坑根据我多年刷题和带学生的经验收集几个校招笔试里特别容易翻车的细节边界条件处理不到位。最常见的是数组越界和空数组。比如KMP算法里模式串长度为0或者二分查找里left0、rightn-1当n0时应该直接返回-1。建议写代码前先想清楚输入为空、只有一个元素、元素全部相同这三种极端情况。整数溢出。C里尤其严重。比如计算mid (left right) / 2当left和right都很大时leftright可能溢出。正确写法是mid left (right - left) / 2。Python虽然不会溢出但如果笔试要求用C这个点必须注意。快排partition的边界条件写错。我前面给出的挖坑法其实已经规避了一些问题但还是要留意两个内部while循环里比较条件到底是还是。如果处理相等的值不当会导致无限循环。贪心和DP的区分不清。笔试里的“最小/最大”类题目如果不确定能不能贪心宁可多写DP。DP能覆盖更多场景虽然复杂一点但至少正确性有保障。时间复杂度过高被卡超时。笔试环境一般会给数据范围你可以估算一下用Python能不能过。比如O(n^2)的算法在n5000时是2500万次操作Python可能刚好卡线建议改成O(n log n)的实现。6.2 我对这套卷子备考优先级的一个判断如果你现在时间有限比如只剩一周就要笔试那我的建议非常明确先把所有LeetCode简单题刷完再把经典DP题爬楼梯、打家劫舍、最长公共子序列、0-1背包刷一遍最后把机器学习概念速记一遍。这套组合覆盖了爱奇艺2020校招第一场笔试题的大半壁江山。基础算法题只要刷得够多拿到题目基本会有肌肉记忆机器学习概念题靠的是考前临阵磨枪把LR、SVM、决策树、K-Means、梯度消失这几个点背熟写熟DP题则是最需要平时积累的部分没有捷径只能多练多推导。我自己带过的学生里有人把LeetCode刷了300题笔试基础题全AC也有人只刷了150题但把每道题都理解得很透彻DP题能举一反三笔试成绩反而更好。所以重点不在于题量而在于每道题是否真的吃透了。如果你已经做完这套笔试题的模拟不妨把错题整理出来按“这道题考的是哪个知识点、我为什么错、正确答案的思考路径是什么”三个维度复盘一遍效果会比盲目刷新题好很多。