最近整理手头的面试笔记翻到一份特别的存档——映客2020春招算法C卷。说是“C卷”实际上它不是一套单独的限时题目而是映客算法岗笔试的完整考点结合体覆盖了基础数据结构、图论、动态规划、音视频信号处理、机器学习和推荐算法。这个方向在当年不少直播公司里都比较典型既要考察候选人的算法基本功又要把题目往真实业务上靠一靠检验你能不能把算法落到直播间的场景里。这篇复盘我想做两件事第一把C卷涉及的算法考点重新梳理一遍告诉你每类考点背后到底在考什么能力答题时应该怎么切入第二结合我自己刷题和带校招新人的经验把这些考点按优先级排个序让准备算法岗笔试的同学有个清晰的方向。如果你是今年准备卷校招算法岗的或者对映客这种直播业务场景下的算法要求感兴趣这篇文章值得你读下去。1. 整张C卷的考点地图从热搜词看映客在考什么拿到一张没有标准答案的回忆版试卷第一步不是急着逐题去做而是先把考点归类。我翻了当年记录下来的题目碎片再对照做题时的搜索记录整理出来的考点版图大概是这样的字符串和模式匹配、排序和堆、贪心和动态规划、图论最短路、二分图匹配这是“常规算法”的部分然后是PID控制算法、卡尔曼滤波、粒子群算法、音频重采样、图像锐化和边缘检测这是“工程信号算法”的部分再往外延伸一点还有聚类、KNN、决策树、深度学习分类模型、推荐系统里的BM25和RETE规则匹配这一块偏算法应用和工程架构。这个分布很能说明问题。映客的算法岗位不是纯后端算法工程师需要面对直播间的真实场景卡顿优化、音质处理、美颜特效、内容推荐、用户分群。所以C卷的命题逻辑就是基础题用来筛掉“不会写代码”的人工程算法题用来筛掉“只会背题”的人机器学习题用来判断你有没有参与过真实项目。三块缺一块后面都很难聊下去。1.1 基础算法与数据结构是绝对主干热搜词里有相当大比例是数据结构排序算法、堆排序算法、贪心算法、KMP算法、快速幂算法。这说明C卷的题干中基础题是绝对的大头分数占比也最高。为什么大厂和像映客这样体量的互联网公司都要把基础算法放在第一关因为我后来参与过几次校招笔试出题知道出题的逻辑基础算法题是最公平的筛选器。它不依赖你做过什么项目、用过什么框架只要你把《算法导论》或数据结构教材里的经典问题吃透就能写出正确答案。而且基础算法题的评分维度很明确时间复杂度是否达标、边界条件是否处理干净、代码风格是否规范这些都是可以直接量化的。从题型分布来看C卷中的基础算法题并不是最难的但一定是最容易被扣分的。后面我会单独把KMP、贪心、堆排序这三个高频考点拿出来展开因为它们对应的热搜词最多也是最容易在“似懂非懂”状态下翻车的题目。1.2 工程类算法占了C卷的差异化比重大部分公司的笔试考完基础算法就结束了。但映客C卷有一个明显区别——它用了不小的篇幅去考音视频和信号处理方向的算法。热搜词里的PID算法、卡尔曼滤波算法、粒子群算法原理、音频重采样算法、图像锐化的拉普拉斯算法、Sobel算法几乎可以看作是C卷中“工程题”的索引。这类题目的特点是没有标准输入输出不会真的让你在笔试系统里跑出一个accept而是给你一段场景描述比如“直播过程中音频采样率不匹配你会怎么处理”或者“美颜功能里的边缘检测算子怎么选”让你用算法语言去设计方案。这类题目对经历过音视频项目或者做过图像处理实验的同学来说很简单但对只刷LeetCode的科班同学反而有点懵。我自己刚毕业那会儿甚至不知道PID算法是干嘛的第一次看到这种题完全不知道怎么下手。通过这份C卷的考点拆解我想把这块的脑补路径说清楚。1.3 机器学习与推荐算法是隐形的加分项除了基础算法和工程信号算法C卷里还零星出现了一些机器学习关键词聚类算法、KNN算法、强化学习算法、xgboot以及一个比较新的EVA-02分类算法。这些题在笔试里占比不高通常以选择题或简答题形式出现但它们是面试的敲门砖。映客的业务本质上是内容平台直播间推荐、秀场分发、用户增长都需要用机器学习模型去驱动。所以哪怕笔试不考深度学习大题面试也一定会聊到你对推荐链路和排序模型的想法。如果能在笔试里把聚类、KNN这些基本概念写清楚面试官会默认你是做过功课的后面聊项目时会更有耐心。2. 基础题里最容易被扣分的三个考点KMP、贪心与排序这一节我把自己当年踩过的坑和后来改卷时看到的高频错误整理一下。不是让大家背题而是把这些考点背后的思维逻辑理清楚理解了之后不管题目怎么变你都能应付。2.1 KMP的next数组背模板没用要会推导KMP是最经典的字符串匹配算法C卷中给出的例子是模式串pabacaba让你求next数组。这个题目看起来很老套但每年都能筛掉一大批人因为很多人只是背了求next数组的模板代码并不知道next数组到底存的是什么、为什么这么求。先理清定义next[i]表示模式串p[0..i]这个前缀子串中最长相等的前缀和后缀长度有的教材里定义为最长公共前后缀有的版本定义为失配后跳转的位置具体看题目约定。以abacaba为例我习惯用“最长相等前后缀”的定义手推i0子串a没有真前缀和真后缀next[0]0i1子串ab前缀a不等于后缀bnext[1]0i2子串aba前缀a等于后缀a且前缀ab不等于后缀banext[2]1i3子串abac最长相等前后缀的长度为0next[3]0i4子串abaca前缀a等于后缀anext[4]1i5子串abacab最长相等前后缀是ab长度2所以next[5]2i6子串abacaba最长相等前后缀是aba长度3所以next[6]3所以得到的next数组是[0,0,1,0,1,2,3]。提示不同教材对next数组的第0位定义不同有的是-1有的是0。笔试答题时如果题目没有明确说明最好先在答案里写清楚自己用的定义再给结果。我在面试时遇到过几个候选人答案其实是对的但没写清楚定义面试官只能按自己的习惯去读结果产生误解。手推的过程比背模板更重要因为笔试简答题会要求你写推导过程。KMP的核心思想是当主串和模式串在某个位置失配时模式串指针不用回退到开头而是回退到next数组指示的位置因为前面的部分已经匹配过了不需要再次比较。理解了这一点面试聊到KMP的复杂度为什么是O(mn)时也能答得上来。2.2 贪心算法看起来简单证明才是分水岭贪心算法是笔试题里的“送分题”和“送命题”并存的存在。如果题目刚好能用贪心解代码可能十行就写完但如果题目伪装成贪心题而实际不能用贪心你用了贪心就很容易掉进陷阱。C卷中的贪心题大多是经典的区间问题比如区间调度选最多不重叠区间、跳跃游戏最少步数到达末尾、分发饼干、加油站问题。我见过很多人解跳跃游戏时代码写对了但问为什么贪心是对的答不上来。练习时一定要养成写证明的习惯哪怕不写在纸上也要在脑子里过一遍。贪心正确性的常用证明方法是交换论证法假设最优解和我们贪心选择的第一个决策不同把最优解里的第一个选择和贪心的选择交换结果不会变差然后归纳到下一个决策。比如跳跃游戏每次维护“当前能跳到的最远位置”如果这一步选了更远的点作为下一次起跳点那么后续能覆盖的范围一定不会比选更近的点小所以贪心成立。这个证明思路不仅适用于笔试面试时说出来面试官的印象分会明显提升。只看有没有写出代码和同时能讲清楚证明完全是两个评价层级。2.3 排序算法不只是快排堆排序和快速幂是重点热搜词里冒泡排序算法C、堆排序算法、排序算法这几个词的热度高到离谱说明很多人在笔试前还在临时翻排序的代码。C卷里排序题一般不直接让你写快排而是考察复杂度的分析和排序算法的应用。举例来说如果题目要求“找出N个数里最大的K个数”最合适的方案不是O(N logN)全排序而是用大小为K的最小堆维护或者用快速选择算法的平均O(N)。这个题目在C卷里出现过其实就是在考堆排序的数据结构理解。堆的插入和删除都是O(log K)维护K个元素的总复杂度是O(N log K)这就是为什么堆在处理TopK问题时比直接排序更优。快速幂算法也值得单独提一下。它和排序没有直接关系但因为经常出现在“大数幂次取模”题里所以很多备考笔记把它和排序放在一起。快速幂的核心是二分幂思想a^b可以拆成a^(b/2) * a^(b/2)b为偶数时每一步把指数减半所以时间复杂度是O(log b)。C实现时要注意用long long临时变量因为两个大数相乘可能溢出int。3. 数据结构与进阶算法Dijkstra、DP和二分图的高频考法如果说基础算法是送分题区那这一节的内容就是拉开差距的分水岭。C卷中图论和动态规划的占比不低而且难度往往比基础题高一个档。3.1 Dijkstra的堆优化与图论题的边界条件Dijkstra算法在C卷中属于“基础中的进阶”几乎所有准备过笔试的人都背过它的模板但真正动手写时很多人会卡在堆优化的实现上。C卷考Dijkstra考的不是你能不能背出伪代码而是你能不能处理边界条件——比如图中有重边时你要保留权值最小的边起点和终点相同时结果为0图不连通时输出什么。堆优化版本的思路很简单维护一个优先队列队列里放的是(当前最短距离, 节点编号)每次弹出距离最小的节点如果这个节点已经被处理过直接跳过否则用它去松弛相邻节点。这个“跳过已处理节点”的判断很关键很多人写堆优化Dijkstra时忘了这一步导致算法因为重复入堆而超时。另外用pairint,int存优先队列时默认是按first从小到大排序正好可以用来存距离。Dijkstra不能处理负权边这是面试必问的考点。如果面试官问“为什么Dijkstra不能处理负权边”答案是因为贪心策略的前提是“当前已确定最短路的节点后续不可能再被更短距离更新”而负权边会破坏这个前提。如果题目说明有负权边就要换成Bellman-Ford或SPFA但这道题如果没验证过笔试时不要贸然写SPFA因为SPFA最坏时间复杂度其实不低容易被极限数据卡掉。3.2 动态规划的常见套路从状态定义到转移方程DP题在算法岗笔试里几乎从不缺席。C卷里的DP题不会太偏基本就是背包、编辑距离、最长公共子序列、最长递增子序列这几个方向。我在刷题时发现一个规律很多人DP状态定义正确但转移方程写错或者在初始化上翻车。拿编辑距离举例dp[i][j]表示把字符串word1[0..i-1]转换成word2[0..j-1]所需的最少操作数。初始化时第一行和第一列不能全设成0而要表示空串到另一个字符串的转换代价也就是dp[0][j]jdp[i][0]i。转移方程分两种情况如果word1[i-1]word2[j-1]dp[i][j] dp[i-1][j-1]否则等于插入、删除、替换三种操作的最小值加1。这些细节笔试时没有草稿纸很难一次想清建议平时练习时就养成“先写初始化再写转移最后检查边界”的习惯。背包问题则要特别关注“恰好装满”还是“不超过容量”这决定了初始化时到底设0还是负无穷。很多DP题表面看起来是求最大值实际上一开始就把恰好装满的条件写错了整体答案都崩了。这类题在笔试中一旦错很可能整题零分所以宁可多花两分钟检查初始化也不要急着提交。3.3 二分图与HK算法考得不多但考到就是拉分题热搜词里有一个比较冷门的关键词二分图HK算法旁边还有Kahn算法。这两个算法在常规校招笔试里出现频率不高但映客C卷的回忆版中提到了所以我特意把它们拿出来讲一下。HK算法是Hopcroft-Karp算法的简称用于求二分图的最大匹配比朴素的匈牙利算法在稠密图上快不少复杂度是O(E sqrt(V))。笔试时如果遇上二分图匹配题一般数据范围不会太大用匈牙利算法也能过但如果你能写出HK会让面试官觉得你确实认真准备过图论。不过HK算法的实现复杂度更高需要BFS分层加DFS增广我建议备考重点还是放在能用匈牙利算法解决的基础匹配题上HK可以理解为进阶拔高。Kahn算法则是拓扑排序的经典实现核心是不断找入度为0的节点把它加入拓扑序列然后删除它的所有出边重复这个过程。如果最终序列里的节点数少于总节点数说明图里有环。这个算法在“判断有向图是否有环”和“输出一个合法的拓扑顺序”题里非常实用。我个人觉得Kahn算法最大的价值在于实现简单且能直接输出拓扑序比DFS法更直观建议优先掌握。4. 映客C卷的隐藏题源音视频与图像处理算法这部分是映客C卷和其他纯互联网公司笔试最大的不同点也是很多算法岗同学在备考时会忽视的地方。虽然每个人都在用智能手机看直播但当“音频重采样”或“图像锐化”作为笔试题出现时大多数候选人是没有概念的。4.1 音频重采样与音频算法的基础认知音频重采样是音视频开发里的经典问题简单说就是把音频数据从一个采样率转换成另一个采样率。比如直播间里主播端采集的是48kHz但观众端播放器可能只支持44.1kHz这时候就必须做重采样否则声音的播放速度和音调会不对。重采样算法的核心是插值和滤波。最简单的方案是线性插值但质量不高容易产生混叠失真。更常用的做法是先上采样、再低通滤波、最后下采样这个过程在数字信号处理里叫多相滤波器组。直播场景对实时性要求高不太可能用计算量太大的高阶滤波器所以实际工程中经常用查表法和定点数运算来优化把浮点运算转成整数运算以提升性能。笔试题不会要求你把多相滤波器实现出来但会问什么是采样率转换为什么要做抗混叠滤波简要说明重采样的实现思路。这些问题考察的是你有没有工程常识是不是只停留在“会刷题”的层面。我在面试中遇到过几位候选人项目经历里写了“直播伴音优化”但问到底层采样率转换时支支吾吾这种就非常减分。4.2 图像锐化、Sobel与拉普拉斯算子图像处理这块C卷的考点集中在边缘检测和锐化上。Sobel算子是最经典的边缘检测算子之一它用两个3x3的卷积核分别计算水平和垂直方向的梯度然后合成梯度幅值。拉普拉斯算子则是二阶微分算子它能检测图像中的快速变化区域常被用来做图像锐化。现在的人脸美颜、背景虚化、人像分割这些功能底层都离不开边缘检测。例如要在直播画面里把人物和背景分开首先要找到人物轮廓而Sobel算子能快速给出梯度图供后续分割算法使用。拉普拉斯算子可以直接用在锐化公式里锐化图像 原图 - 拉普拉斯算子响应也就是在边缘和细节区域增强对比度。笔试遇到这类题不需要你会写OpenCV代码但需要你对卷积核的数值设计原理有所理解。比如Sobel的水平梯度核为什么左边是-1、中间是0、右边是1因为这是对中心像素左右像素差值的近似本质是计算差分。把“差分”和“梯度”这个关系讲清楚面试官会认可你是有图像处理基础功底的。4.3 PID算法与卡尔曼滤波控制与信号处理在直播中的应用PID算法和卡尔曼滤波算法在热搜词里同时出现一个是控制论里的经典算法一个是信号处理里的经典状态估计方法看起来八竿子打不着但它们在直播系统里都能找到应用场景。PID算法全称是比例-积分-微分控制核心思想是对“偏差”做比例、积分、微分三种运算然后把结果叠加作为控制输出。在直播系统里典型的应用是码率自适应控制当网络带宽波动时通过PID调节编码码率让码率既不会因为过低导致画质模糊也不会因为过高导致卡顿。比例项处理当前偏差积分项消除稳态误差微分项则能提前感知偏差变化趋势抑制超调。笔试如果考PID多半会让你解释三个参数的作用或者结合具体场景说明怎么调参。卡尔曼滤波则常用于传感器数据的融合和降噪。它在“预测”和“更新”两个步骤间循环先用状态转移方程预测当前时刻的状态再用观测值去修正预测结果修正的权重取决于预测噪声和观测噪声的协方差。直播间的传感器可能包括手机陀螺仪、加速度计、GPS等卡尔曼滤波可以把这些数据融合起来得到更稳定的设备运动姿态用于防抖和手势识别。这一块的笔试难度不高但对于没有接触过控制论的人来说概念比较难懂。我当时是花了一整个周末把卡尔曼滤波的五个核心公式推了一遍又跑了一个简单的目标跟踪Demo才算真正理解。如果时间充裕强烈建议你也亲手推一下公式不要只看视频讲解否则隔几天就忘。5. 粒子群、聚类与推荐算法C卷压轴题的常见方向热搜词里粒子群算法、聚类算法、KNN算法、BM25算法、RETE算法出现得非常集中排在一起看基本上就是C卷最后几道综合题的命题背景。这部分的题往往没有唯一正确答案但很能看出一个人是否具备“把算法应用到业务”的能力。5.1 粒子群算法原理与优化问题粒子群优化算法Particle Swarm OptimizationPSO是一种启发式优化算法灵感来自鸟群觅食。每个“粒子”代表候选解粒子在搜索空间里用自己的位置和速度更新同时参考“个体历史最优位置”和“群体历史最优位置”来调整飞行方向。经过多轮迭代群体逐渐收敛到最优解附近。笔试里考察PSO通常不是让你实现完整算法而是让你描述基本流程初始化粒子群计算适应度更新个体最优和全局最优更新速度和位置重复直到满足停止条件。有时候会结合一个具体函数比如求f(x, y) x^2 y^2的最小值让你写出用PSO求解的思路。和模拟退火、遗传算法相比PSO的优点是实现简单、参数少、收敛较快缺点是容易早熟收敛陷入局部最优。所以实际应用中经常把PSO和局部搜索结合或者用自适应惯性权重来调节全局搜索和局部开发能力。回答这类题时如果能主动提到“早熟收敛”这个缺陷和应对方案会显得你有真实算法调优经验。5.2 聚类算法与KNN无监督和有监督的边界聚类算法是典型的无监督学习它的目标是把无标签数据分成若干簇使得同一簇内的样本尽可能相似不同簇的样本差异尽可能大。K-Means是面试中最常考的聚类算法流程简单随机选择K个初始中心交替执行“分配样本到最近中心”和“更新中心为簇内均值”两个步骤直到中心不再变化或达到迭代次数。不过K-Means对初始中心很敏感而且要求簇的形状是凸的。笔试简答题如果问“K-Means的改进方向有哪些”可以从K-Means初始化、Mini-Batch K-Means、以及用轮廓系数选择K这几个角度回答。另外聚类里还有一个经典的“肘部法则”通过画簇内平方误差和随K值变化的曲线找到拐点作为合适的K。KNN则是标准的监督学习算法热搜词里“KNN算法的应用能力包括哪三个方面”这个问法在网上很流行。拆开来看KNN的三大核心能力是分类、回归和异常检测。分类时一个样本的类别由它最近的K个邻居投票决定回归时预测值取这K个邻居的均值或加权均值异常检测时距离所有样本都很远的点被认为是异常点。KNN的缺点是计算复杂度高因为它需要计算新样本和所有训练样本的距离实际工程里经常用KD树或球树来加速。5.3 从BM25到推荐系统搜索和内容分发里的算法影子BM25算法在热搜词里出现这让我有点意外因为它的知名度远不如TF-IDF。BM25是信息检索领域里用于文档相关度排序的经典算法它的核心思想是对查询词和文档中的每个词计算一个分数然后加权求和。相比于TF-IDFBM25引入了文档长度归一化和词频饱和函数相关性排序效果通常更好。映客作为直播平台用户的搜索和推荐都离不开这样的排序算法。如果C卷的压轴题是“设计一个直播间搜索排序系统”你不需要真的调起一个搜索引擎而是应该给出一个完整的链路召回层用文本匹配或者向量检索粗排层用BM25或者双塔模型过滤候选精排层用GBDT、LR或者深度排序模型打分。再往细了说还要考虑业务规则比如付费直播间加权、新人主播扶持、低质量内容降权等。RETE算法则是规则引擎Drools底层的匹配算法它通过构建一个判别网络把事实Fact在规则网络里逐层传递来高效地找到所有匹配的规则。这个算法和直播推荐看起来关系不大但它代表了“规则匹配优化”的思维。如果题目里出现“大量规则需要实时匹配”的场景RETE算法就是非常好的回答素材。6. 我复盘后的备考建议哪些坑要避开、哪些分必须拿复盘完整张C卷的考点分布我想把备考优先级和实战技巧放在最后说。这部分是我作为一个过来人最想告诉后来者的东西。6.1 校招算法备考的优先级排序根据C卷的考点权重我把备考内容分成了三个梯队。第一梯队是绝对的拿分核心数组、字符串、链表、二叉树、排序、二分查找、贪心、动态规划这些必须达到“闭眼能写”的程度。第二梯队是拉分项图论Dijkstra、拓扑排序、并查集、前缀和与差分、字典树、单调栈。第三梯队是行业相关算法音视频处理、图像处理、PID、卡尔曼滤波、机器学习基础。第三梯队虽然占比不如前两个梯队高但在映客这类业务导向的公司里往往是面试官判断匹配度的关键。我给几个参加过校招的同学做模拟面试时发现一个通病花大量时间刷冷门题的代码模板却忽略了第一梯队的深度。实际上笔试系统里最容易被卡住的不是某道难题而是那些“一看就会、一写就错”的基础题。边界条件、空值处理、溢出判断这些细节才是通过率的分水岭。6.2 实际笔试中的时间分配与调试技巧算法笔试的时间一般比较紧我的建议是先花两三分钟快速浏览所有题目把题目按“能立刻写”“需要想一想”“大概率做不出来”分成三档。优先完成第一档稳住基本盘再去做第二档。第三档如果时间不够至少写上暴力解法因为在部分评分规则里暴力法的部分得分能救你一命。在线笔试的调试环境通常不如本地IDE友好所以平时刷题就要锻炼“一次提交通过”的能力。写完代码后不要急着提交先在草稿纸上或者注释里写几个测试用例空输入、单元素输入、重复元素输入、超大数值输入、负值边界这五个用例能覆盖大多数隐藏的边界bug。另外如果代码里用了递归一定要检查递归深度防止栈溢出。C里如果用了vectorint要确定是否包含头文件我见过不少同学因为漏了#include vector而白白丢分的案例。6.3 简历与项目怎么拔高算法岗匹配度最后一条建议是给简历关和面试关的但笔试备考阶段就要开始积累。单纯在简历里写“熟悉常用算法和数据结构”没有太多说服力面试官更想看到你把算法用在什么项目里。比如你做过一个直播延迟优化项目哪怕只是课程设计也可以结合PID控制算法来写用PID调节缓冲队列大小在延迟和卡顿率之间做权衡。你用过OpenCV做图像处理就可以把Sobel边缘检测和拉普拉斯锐化写进项目描述里。这里有一个很大的误区以为把项目里的技术名词堆得越多越好。实际上面试官只要追问两个问题就能知道你懂不懂第一个问原理第二个问为什么选它不选别的方案。写项目时要对这两个问题准备好充足的说法不是背稿子而是真的理解。提示如果你是跨专业或者没有项目经历的同学建议在笔试前找几个经典音视频、图像或者推荐相关的开源项目跑一下不追求做完重点是把核心算法的输入、输出、性能瓶颈和优化方向搞清楚。这样即使笔试没遇到面试自我介绍时也能有话说。我复盘完整个映客2020春招算法C卷个人体会最深的一点是算法笔试不只是考“你会不会写这道题”而是在考“你有没有解决问题的完整思路框架”。题目可以千变万化但底层的能力要求是固定的——会分析复杂度、会处理边界条件、能把算法和业务场景结合、能清晰表达自己的思路。这四点就是整张C卷想筛选出的核心能力。