1. 试卷整体设计与考察思路1.1 映客算法岗笔试在考什么2020年春招那阵我在牛客网上刷到映客的算法A卷做完第一感觉是这份卷子谈不上多难但很能看出一个算法工程师的基本功和业务直觉。跟BAT那种上来就甩一道冷门DP优化题的做法不太一样映客的A卷明显带着直播平台自己的味道——既考通用算法又考跟音视频、推荐、内容分发相关的工程能力。先说结论这份试卷的考察维度可以拆成三层第一层是数据结构和基础算法比如KMP、贪心、动态规划、排序、图论这部分占比最大也最考验刷题功底。第二层是机器学习与深度学习的基础概念KNN、聚类、模型评估、过拟合、正则化这些都会涉及考察方式以选择题和简答为主。第三层是直播场景下的算法应用题比如音频重采样、推荐排序、实时链路里的PID控制和卡尔曼滤波题目会直接给业务场景让你去设计算法方案。这三层恰好对应一个直播平台算法工程师日常要干的活处理海量数据、训练推荐模型、优化音视频体验。所以这套卷子的参考价值不局限于映客本身凡是做内容平台、直播方向、音视频方向的算法岗复习路径都大同小异。从我实际做下来的体感来看这套A卷的题量控制得比较合适90分钟要完成大约4道编程8道选择题2道场景问答。编程题不需要用特别冷门的算法但要求代码干净利落边界条件严谨。选择题里有一些概念辨析是故意设坑的能不能拿分就看你对机器学习理论的理解是否扎实。场景问答题是拉开差距的关键光会背算法不行得能结合直播业务把方案讲清楚。1.2 为什么这份卷子值得反复琢磨很多同学备考算法岗笔试喜欢把注意力放在刷难题上觉得面试官会出一些ACM级别的题目来卡人。但实际上像映客这种体量的互联网公司算法笔试的核心目的是筛选“能干活的人”而不是筛选“竞赛选手”。A卷里有两道题我印象特别深一道是KMP的next数组计算一道是音频重采样方案设计前者考察基础是否扎实后者考察能不能把算法落到真实业务里。如果你只刷LeetCode不思考业务场景第二类题很容易懵。所以我个人一直建议准备算法岗笔试时要“两手抓”一方面把经典算法练到能默写的程度另一方面要主动去了解目标公司的业务形态想想算法在里面扮演什么角色。映客是直播平台直播的核心链路无非就是推流、转码、分发、播放、互动、推荐这里面每一个环节都有算法在起作用。知道这些你再看A卷的题目就明白出题人为什么这么设计了。这套卷子还有一个值得琢磨的点是它的难度曲线。基础题占了60%以上难题大概只有一两道分布上有明显的梯度。这说明出题人希望大家都能拿一些基础分再用后面的大题去甄别真正有算法思维的人。所以你在做题的时候也应有同样的策略先把稳的分数拿到手再花时间攻坚难题千万不要在一道选择题上耗太久。后面我会把每类题目的具体解法拆开讲。2. 核心基础算法题详解KMP、贪心与动态规划2.1 KMP的next数组最容易翻车的送分题A卷的编程题里有一道字符串匹配相关题目模式串给的是abacaba要求手推next数组并写出KMP匹配主串的完整过程。这道题单独看不难但它考察的是你到底是真懂KMP还是只会背模板因为next数组有几种不同的定义方式不同定义下边界条件是会变形的。先说最常见的定义方式next[i]表示模式串前i个字符组成的子串中最长相等前后缀的长度。注意这里说的“前缀”不包含整个子串“后缀”同样不包含整个子串。如果你采用这种定义那么next[0]一般置为-1或0具体看教材和平台要求A卷题目在题干里其实给出了定义提示next[i]定义为失配时模式串指针回退的位置。我按这个定义手推一遍i0next[0]-1这是初始值。i1只看字符a不存在相等前后缀next[1]0。i2子串ab的前缀有a后缀有b不相等next[2]0。i3子串aba的前缀a和后缀a相等更长一点的前后缀都不行next[3]1。i4子串abab的前缀ab和后缀ab相等next[4]2。i5子串ababa的前缀aba和后缀aba相等next[5]3。i6子串ababac的前缀a和后缀c不相等往前找前缀ab和后缀ac不相等前缀aba和后缀bac不相等最终next[6]0。最终next数组为{-1, 0, 0, 1, 2, 3, 0}如果你按“最长相等前后缀长度”来定义则是{0, 0, 0, 1, 2, 3, 0}。这两个结果在这个题里就差在next[0]上失配回退时用的位置会有区别但核心思想是一样的。做题的时候我建议大家先把题目对next的定义读三遍再动手算。很多人在KMP上丢分不是因为不会而是因为默认了某种定义结果跟题目要求对不上。笔试环境里没有调试机会一旦错了就是整道题零分这个成本太高了。KMP的匹配过程就不完整推导了关键是记住那两句话主串指针永远不回头模式串指针按next数组回退。这道题如果扩展到实际场景就是字符串匹配在文本检索、敏感词过滤、日志分析里的应用。推荐系统里做关键词匹配、弹幕过滤、内容审核底层都离不开KMP这类字符串算法。2.2 贪心算法与区间调度写清楚排序依据是关键A卷里有一道非常经典的贪心题给定若干个直播场次的时间区间要求选出尽可能多的互不重叠的场次进行推荐排期输出最大可选数量。这道题就是区间调度问题贪心策略是所有区间按结束时间从小到大排序然后依次选择不冲突的区间。为什么按结束时间排序而不是开始时间我当年学贪心的时候也迷糊过这里用一句人话解释结束时间越早后面留下的空档就越大越有可能塞进更多区间。这跟现实里安排会议是一个道理你想在一天里开尽量多的短会肯定优先选最早结束的那场而不是最早开始的那场。伪代码非常简单def max_events(intervals): intervals.sort(keylambda x: x[1]) count 0 last_end -float(inf) for start, end in intervals: if start last_end: count 1 last_end end return count这道题真正的坑在两个地方。第一区间端点是否允许重叠如果题目允许“首尾相接”也就是前一个结束时间等于后一个开始时间也算不冲突那判断条件就是start last_end如果不允许就得改成start last_end。第二输入数据可能有乱序和重复排序前务必确认key取的是结束时间而不是开始时间重复区间不影响贪心结果但会影响你对答案的自信。区间调度往深了说还可以延展到会议室问题、任务调度、CPU进程调度。直播平台的转码任务分配本质上也是一个区间调度问题哪个任务优先用哪台转码机器要看任务紧迫度和资源空闲窗口。面试官可能会顺着这道题问你“如果有权重怎么办”那就变成了加权区间调度贪心失效要改成动态规划用二分加速到O(n log n)。这一层递进在面试中很常见笔试没考不代表面试不考复习时要把这个链条打通。2.3 动态规划最长上升子序列的O(n log n)解法A卷的动态规划题考的是最长上升子序列LIS输入一个数组输出最长严格递增子序列的长度。常规解法是O(n^2)的DP状态转移方程是dp[i] max(dp[i], dp[j] 1)其中j i且nums[j] nums[i]。但A卷明确要求时间复杂度O(n log n)这就需要用“贪心二分”的优化版本。优化版本的思路很巧妙维护一个数组dd[i]表示长度为i的最长上升子序列的末尾元素的最小值。遍历原数组时如果当前元素比d的最后一个元素大就追加到末尾否则在d里二分查找第一个大于等于当前元素的位置替换掉它。替换这个操作不会改变子序列的长度但能让后续元素有更多机会接上来这就是贪心思想在DP里的应用。import bisect def length_of_lis(nums): d [] for x in nums: idx bisect.bisect_left(d, x) if idx len(d): d.append(x) else: d[idx] x return len(d)这段代码看起来简单真正理解它需要想明白一个问题d数组里的值并不是一个真实的上升子序列它只是记录了每个长度的最小末尾值。比如nums [4, 10, 4, 3, 8, 9]d数组最终是[3, 8, 9]d[0]3d[1]8d[2]9但你并不能在原始数组里找到一个严格按这个顺序递增的子序列。这并不影响答案的正确性因为d[i]的定义保证了如果存在一个长度为i1的子序列那么末尾值一定大于等于d[i]。想清楚这一层这个算法才算真正掌握。笔试时如果时间紧张我建议先写O(n^2)拿部分分再优化到O(n log n)。部分分在算法笔试里是很重要的不是你AC了才有分而是你过了多少测试用例就拿多少分。这道题的后续延伸是“最长递增子序列的个数”以及树上LIS、二维LIS等变体大厂面试经常考建议大家把底层的贪心二分思想彻底吃透。3. 机器学习与深度学习基础考察3.1 分类算法与聚类KNN的K值怎么选A卷的选择题和简答题里机器学习部分考到了KNN和K-Means。有一道选择题问的是在KNN算法中K值的增大对模型偏差和方差的影响是什么。答案是K值增大模型偏差增大方差减小。为什么K值变大意味着决策时参考的邻居更多模型会变得更平滑对局部细节的捕捉能力下降所以偏差增大但对单一噪声样本的敏感度降低方差减小。这跟“过拟合和欠拟合”的经典权衡是一个道理。KNN本身是一种惰性学习算法训练阶段几乎不做什么事真正计算发生在预测时。因此在样本量大、特征维度高的场景下KNN的预测效率很低这也限制了它在工业界的应用。我们做推荐召回的时候几乎不会直接用KNN而是用向量检索替代但其核心思想——物以类聚、近朱者赤——在产品里无处不在。K-Means的考点集中在初始质心选择、距离度量、K值确定这三个地方。初始质心选不好容易陷入局部最优所以才有K-Means这种改进方法。K值怎么定常见做法是手肘法和轮廓系数法。手肘法看的是SSE误差平方和随K值变化的拐点因为拐点处的K值往往就是“性价比”最高的聚类数。轮廓系数法则是同时考虑簇内紧密度和簇间分离度取值范围在-1到1之间越接近1越好。如果你在简答题里遇到“如何确定K”把这两种方法都写出来再结合业务解释一下分数会明显不一样。另外分类算法里还有一个高频考点是距离度量。欧氏距离、曼哈顿距离、余弦相似度分别适用什么场景文本向量用余弦相似度因为文本向量的模长往往受文档长度影响余弦可以消除模长差异突出方向上的相似性。数值型特征用欧氏距离直观但要注意特征归一化否则量纲大的特征会主导距离计算。这些细节我在笔试时是靠刷面经总结出来的建议你也按照“算法原理适用场景优缺点”的结构去整理每个模型。3.2 模型评估与损失函数AUC和交叉熵A卷有一道题考AUC的含义选项里混了几个干扰项。AUC是ROC曲线下的面积表示随机正样本排在随机负样本前面的概率。如果你的模型对所有样本打分都是随机的AUC就是0.5如果是完美的排序AUC就是1。AUC的值不依赖具体的分类阈值所以它特别适合评估排序质量这也是为什么推荐系统和广告系统里那么看重AUC。不过AUC有一个问题它对正负样本比例不敏感所以样本严重不均衡时还要同时关注召回率、精确率或GAUC。简答题里让我写交叉熵损失函数的公式并解释为什么分类问题不用均方误差。交叉熵的公式是L -[y * log(y_hat) (1 - y) * log(1 - y_hat)]。不用MSE做分类的原因有两个层面。第一逻辑回归加MSE会让损失函数变成非凸函数梯度下降容易陷入局部最优第二交叉熵配上softmax梯度形式是(y_hat - y)梯度大小跟预测误差线性相关训练稳定而MSE的梯度里带sigmoid导数的项在预测值接近0或1时梯度几乎消失模型学不动。很多同学在复习损失函数时只背公式不理解背后的动机结果题目换个问法就懵了。比如考你“交叉熵和KL散度的关系”其实交叉熵等于熵加上KL散度机器学习里最小化交叉熵等价于最小化KL散度。这个知识点在热词里也有“kl elbo算法原理详解”ELBO在VAE里就是变分下界跟KL散度密切相关。你觉得考得偏其实这些都是算法工程师的基本功。3.3 深度学习必考概念过拟合、正则化、梯度消失深度学习的考察点并不深主要还是基础概念。有一道单选题问L1和L2正则化的区别答案是L1能把参数稀疏化L2把参数压缩到接近0但不等于0。为什么L1能产生稀疏解因为L1的约束区域是菱形尖点落在坐标轴上目标函数的最优解更容易出现在坐标轴的尖点上所以很多参数直接变成0。这个几何解释是高频考点建议记住。过拟合的解决办法可以列一个清单数据层面增加样本量、数据增强、欠采样/过采样模型层面降低模型复杂度、减少网络层数或参数量训练层面早停、正则化、Dropout、Batch Normalization集成层面Bagging、Dropout的本质也是训练多个子网络的集成遇到这类简答题我建议不要只写方法名要简单解释一下原理。比如Dropout为什么能缓解过拟合因为它每次训练随机让一部分神经元失活迫使网络学习到更鲁棒的特征而不是过度依赖某几个神经元。这种“原理作用”的答题结构能让阅卷人一眼看出来你是真懂还是背的。梯度消失和梯度爆炸也是必考。sigmoid函数在输入绝对值较大时梯度趋近于0多层反向传播梯度连乘后就消失了所以深层网络用ReLU这类激活函数。如果你被问到“为什么ReLU能缓解梯度消失”可以从正区间梯度恒为1来解释。但ReLU也有缺点神经元死亡问题负数区间梯度恒为0反向传播时该神经元永远得不到更新。所以后来才有LeakyReLU、PReLU这些变体。这些知识点在复习深度学习时都要串联起来而不是孤立地背。4. 直播场景应用题从音频重采样到推荐排序4.1 音频重采样算法为什么线性插值不行A卷的场景题里有一道音频重采样相关的题大意是直播过程中用户的网络环境不同播放端需要把接收到的音频从一种采样率转换成另一种采样率请说明重采样的原理并设计一个可行的实现方案。这道题当时让我愣了一下因为它不是单纯的算法题还涉及信号处理的基础知识。音频重采样的本质是采样率转换常见场景是把48kHz的音频转成44.1kHz或者反过来。最简单的思路是线性插值在两个已知采样点之间按比例插出一个新点。但线性插值在音频处理里是下策因为它等效于一个性能很差的低通滤波器会引入高频失真和混叠噪声。实际工程里一般用多相滤波器组或者基于FFT的重采样方案先把信号从时域变到频域在频域里完成采样率变换再逆变换回时域。我在答题时写了这样一条技术路线先做抗混叠滤波再做抽取或插值。因为降低采样率时如果信号中存在高于目标采样率一半的频率分量就会发生混叠所以必须先用低通滤波器把高频部分干掉再进行抽取。提高采样率时则需要插值并通过低通滤波消除镜像频谱。这种解释既专业又完整阅卷人一看就知道你有信号处理的基础。如果你只是写“用插值算法”而没提抗混叠这道题基本就拿不到高分。类似的信号处理算法在直播链路里还有很多。卡尔曼滤波用于去抖动和预测PID用于码率控制。A卷虽然没有直接考这些算法的推导但在场景题里提到过“如何优化弱网下的播放体验”这其实就是把卡尔曼滤波和PID串起来的经典问题。所以你不要只盯着教材里的理论要把它们放到真实场景里去理解。4.2 推荐系统中的协同过滤与排序场景题的第二问是推荐相关的直播平台首页有大量直播间如何为用户做个性化推荐请设计一个简化版的推荐系统并说明召回和排序两个阶段的做法。这类题在互联网公司笔试里很常见关键是看你能不能把经典算法讲清楚。我答题时给了一个比较中规中矩的方案召回阶段用协同过滤基于用户的协同过滤或者基于物品的协同过滤排序阶段用GBDT或逻辑回归做CTR预估。基于物品的协同过滤核心是计算物品之间的相似度矩阵直播场景里“物品”就是直播间两个直播间同时被一批用户看过就认为它们相似。用户点开某个直播间后可以给他推荐相似直播间。这个方案在计算复杂度上比基于用户的协同过滤更可控而且可以离线计算相似度矩阵在线只做查表排序。排序阶段是重头戏。特征工程上用户维度的特征有性别、年龄、活跃时段、历史观看时长内容维度有直播分类、标签、主播等级、在线人数上下文维度有当前时间、网络类型。把这些特征拼成一个样本交给GBDT训练输出一个点击概率再结合业务规则做最终排序。当时我还补了一句如果追求效果可以上双塔模型做向量召回用FM或DeepFM做排序。在笔试里写这种“经典方案可选升级”的结构能让阅卷人看到你的知识深度。4.3 实时音视频链路中的算法细节直播系统的体验受网络波动影响非常大A卷的问答里有一道题问推流端网络变差时如何用算法保证直播的流畅性我在回答时提到了PID算法和卡尔曼滤波的配合使用这跟我平时看的一些音视频工程文章有关。PID控制在直播里的一个典型应用是码率自适应。编码器可以基于网络带宽估计值动态调整视频码率但直接使用瞬时带宽估计很容易让码率剧烈抖动所以需要一个控制器让码率平滑变化。简单地说P项对误差立即反应I项消除稳态误差D项抑制超调。在带宽下降时PID控制器会渐进地降低码率避免画面突然模糊带宽恢复时再逐步上调避免频繁切换引发卡顿。卡尔曼滤波则常用于网络延迟和抖动估计。接收端每收到一个RTP包就能算出一个传输时间差样本但这个样本有噪声直接拿它做缓冲控制会不稳定。卡尔曼滤波能根据历史观测和运动模型递归地估计出真实延迟和延迟变化率。你不需要完整推导卡尔曼公式但至少要能画出状态转移和观测更新的基本结构然后解释它为什么能在有噪声的观测中保持平滑估计。这两个算法组合起来就是在弱网下保障直播体验的底层技术。写这类场景题的时候我最怕同学只写“用PID控制码率”而不展开。你至少要说清楚控制量是什么、被控对象是什么、反馈量是什么。好的回答应该是被控对象是编码器码率控制量是码率调整步长反馈量是从接收端回传的卡顿率或缓冲时长目标是把卡顿率控制在阈值以下。这样回答既体现工程思维又展现算法功底。5. 踩坑记录与备考复盘5.1 我在这次笔试中踩过的坑说实话这套A卷我做的时候并不是一帆风顺有几个地方现在想起来还觉得可惜。第一个坑出在KMP的next数组上我做题时默认了“最长相等前后缀长度”的定义结果题目给的定义是“失配时模式串指针回退的位置”两种定义在某些下标上差一位我在next[3]和next[4]上算偏了。所以还是那句话先审题再审题再审题尤其是算法基础题定义不同结果不同。第二个坑是区间调度那道题我一开始用了按开始时间排序的贪心样例过了但提交后只过了部分测试用例。后来复盘才意识到按开始时间排序的问题是一个很早起但是很长的区间会堵住后面所有区间导致结果偏小。按结束时间排序则没有这个问题。这种“样例能过、大数据挂掉”的情况在笔试里非常致命因为在线笔试不给你提示到底哪组数据没过只能靠你自己想清楚贪心策略的正确性证明。第三个坑暴露在音频重采样那道题上我只写了“用插值”三个字没有提抗混叠滤波。虽然不一定是零分但肯定没有踩到得分点。场景题最怕的是答得太浅算法选型、数据处理流程、实现细节、可能的优化点这四个层次写全了才能拿高分。所以我后面复习“算法加场景”类题目时都会刻意让自己按这个框架去组织答案。5.2 算法岗笔试的时间分配与答题策略经过这套卷子的洗礼我总结了一套自己的笔试时间分配策略。拿到卷子别急着做题先把所有题目扫一遍看看每道题的分值和难易程度心里有个谱。我的分配原则是分值高而且会做的题先做分值低但是要花很长时间的题放到最后。选择题一道一般只有一两分即使做对了对总分影响也不大但如果卡住十分钟后面二十分的大题可能就来不及了。代码题我是按照“先暴力后优化”的策略来写。比如LIS那道题如果一时间想不起O(n log n)的写法我会先把O(n^2)的DP写出来拿到部分分然后看剩余时间再优化。很多同学喜欢死磕AC结果一道题做一小时最后卷子没做完这是最不划算的。在实际笔试中AC率比题数更重要你要确保自己做的每道题都尽量拿到大部分测试用例的分数。场景题和简答题的答题框架也很重要。我一般用“先说结论再展开原理最后举例落地”的结构每个概念先给出定义或结论然后用一段话解释为什么最后结合直播场景说怎么用。这样改卷老师快速扫一眼就能抓住你的答题脉络。如果题目明确要求结合业务一定要把业务词糅进答案里比如“直播间推荐”“礼物打赏人群聚类”“弹幕实时过滤”哪怕只是举例也能让答案更贴题。5.3 后续复习路线建议考完这套A卷之后我重新调整了自己的算法复习路线这里分享出来供参考。基础算法部分我不再追求刷难题数量而是把高频考点分门别类做专项训练字符串KMP、Trie、AC自动机、排序快排、堆排、归并、动态规划背包、LIS、区间DP、图论Dijkstra、拓扑排序、并查集、贪心区间类、分配类。每个专题做十道左右典型题做到能默写模板的程度。机器学习部分我用“模型原理损失函数评估指标适用场景”的四段式结构整理了笔记每个模型都按这个框架过一遍。KNN、K-Means、逻辑回归、决策树、GBDT、随机森林、SVM是笔试和面试的常客把这些彻底吃透比什么模型都追新要靠谱。深度学习部分重点掌握多层感知机、CNN、RNN、LSTM的结构和各自优缺点以及调参技巧和防止过拟合的手段。如果时间充裕可以把常见的面试题整理成QA文档睡前过一遍。很多算法岗的笔试和面试考察内容其实高度重叠一份好的复习笔记能反复用。最后再分享一个实用小技巧我习惯把做过的场景题和热词里的算法概念归类存档比如音频重采样、PID控制、卡尔曼滤波、推荐召回排序这些每类写一段“业务背景技术方案可优化点”。这样遇到类似的场景题时我直接调取自己的知识库能节省大量现场思考时间。这套A卷虽然过去了几年但它的题型和考察思路在今天仍然有参考价值尤其是直播、音视频、推荐方向的算法岗备考逻辑一直没有变过。 映客算法岗笔试A卷解析：从KMP到直播场景算法应用
1. 试卷整体设计与考察思路1.1 映客算法岗笔试在考什么2020年春招那阵我在牛客网上刷到映客的算法A卷做完第一感觉是这份卷子谈不上多难但很能看出一个算法工程师的基本功和业务直觉。跟BAT那种上来就甩一道冷门DP优化题的做法不太一样映客的A卷明显带着直播平台自己的味道——既考通用算法又考跟音视频、推荐、内容分发相关的工程能力。先说结论这份试卷的考察维度可以拆成三层第一层是数据结构和基础算法比如KMP、贪心、动态规划、排序、图论这部分占比最大也最考验刷题功底。第二层是机器学习与深度学习的基础概念KNN、聚类、模型评估、过拟合、正则化这些都会涉及考察方式以选择题和简答为主。第三层是直播场景下的算法应用题比如音频重采样、推荐排序、实时链路里的PID控制和卡尔曼滤波题目会直接给业务场景让你去设计算法方案。这三层恰好对应一个直播平台算法工程师日常要干的活处理海量数据、训练推荐模型、优化音视频体验。所以这套卷子的参考价值不局限于映客本身凡是做内容平台、直播方向、音视频方向的算法岗复习路径都大同小异。从我实际做下来的体感来看这套A卷的题量控制得比较合适90分钟要完成大约4道编程8道选择题2道场景问答。编程题不需要用特别冷门的算法但要求代码干净利落边界条件严谨。选择题里有一些概念辨析是故意设坑的能不能拿分就看你对机器学习理论的理解是否扎实。场景问答题是拉开差距的关键光会背算法不行得能结合直播业务把方案讲清楚。1.2 为什么这份卷子值得反复琢磨很多同学备考算法岗笔试喜欢把注意力放在刷难题上觉得面试官会出一些ACM级别的题目来卡人。但实际上像映客这种体量的互联网公司算法笔试的核心目的是筛选“能干活的人”而不是筛选“竞赛选手”。A卷里有两道题我印象特别深一道是KMP的next数组计算一道是音频重采样方案设计前者考察基础是否扎实后者考察能不能把算法落到真实业务里。如果你只刷LeetCode不思考业务场景第二类题很容易懵。所以我个人一直建议准备算法岗笔试时要“两手抓”一方面把经典算法练到能默写的程度另一方面要主动去了解目标公司的业务形态想想算法在里面扮演什么角色。映客是直播平台直播的核心链路无非就是推流、转码、分发、播放、互动、推荐这里面每一个环节都有算法在起作用。知道这些你再看A卷的题目就明白出题人为什么这么设计了。这套卷子还有一个值得琢磨的点是它的难度曲线。基础题占了60%以上难题大概只有一两道分布上有明显的梯度。这说明出题人希望大家都能拿一些基础分再用后面的大题去甄别真正有算法思维的人。所以你在做题的时候也应有同样的策略先把稳的分数拿到手再花时间攻坚难题千万不要在一道选择题上耗太久。后面我会把每类题目的具体解法拆开讲。2. 核心基础算法题详解KMP、贪心与动态规划2.1 KMP的next数组最容易翻车的送分题A卷的编程题里有一道字符串匹配相关题目模式串给的是abacaba要求手推next数组并写出KMP匹配主串的完整过程。这道题单独看不难但它考察的是你到底是真懂KMP还是只会背模板因为next数组有几种不同的定义方式不同定义下边界条件是会变形的。先说最常见的定义方式next[i]表示模式串前i个字符组成的子串中最长相等前后缀的长度。注意这里说的“前缀”不包含整个子串“后缀”同样不包含整个子串。如果你采用这种定义那么next[0]一般置为-1或0具体看教材和平台要求A卷题目在题干里其实给出了定义提示next[i]定义为失配时模式串指针回退的位置。我按这个定义手推一遍i0next[0]-1这是初始值。i1只看字符a不存在相等前后缀next[1]0。i2子串ab的前缀有a后缀有b不相等next[2]0。i3子串aba的前缀a和后缀a相等更长一点的前后缀都不行next[3]1。i4子串abab的前缀ab和后缀ab相等next[4]2。i5子串ababa的前缀aba和后缀aba相等next[5]3。i6子串ababac的前缀a和后缀c不相等往前找前缀ab和后缀ac不相等前缀aba和后缀bac不相等最终next[6]0。最终next数组为{-1, 0, 0, 1, 2, 3, 0}如果你按“最长相等前后缀长度”来定义则是{0, 0, 0, 1, 2, 3, 0}。这两个结果在这个题里就差在next[0]上失配回退时用的位置会有区别但核心思想是一样的。做题的时候我建议大家先把题目对next的定义读三遍再动手算。很多人在KMP上丢分不是因为不会而是因为默认了某种定义结果跟题目要求对不上。笔试环境里没有调试机会一旦错了就是整道题零分这个成本太高了。KMP的匹配过程就不完整推导了关键是记住那两句话主串指针永远不回头模式串指针按next数组回退。这道题如果扩展到实际场景就是字符串匹配在文本检索、敏感词过滤、日志分析里的应用。推荐系统里做关键词匹配、弹幕过滤、内容审核底层都离不开KMP这类字符串算法。2.2 贪心算法与区间调度写清楚排序依据是关键A卷里有一道非常经典的贪心题给定若干个直播场次的时间区间要求选出尽可能多的互不重叠的场次进行推荐排期输出最大可选数量。这道题就是区间调度问题贪心策略是所有区间按结束时间从小到大排序然后依次选择不冲突的区间。为什么按结束时间排序而不是开始时间我当年学贪心的时候也迷糊过这里用一句人话解释结束时间越早后面留下的空档就越大越有可能塞进更多区间。这跟现实里安排会议是一个道理你想在一天里开尽量多的短会肯定优先选最早结束的那场而不是最早开始的那场。伪代码非常简单def max_events(intervals): intervals.sort(keylambda x: x[1]) count 0 last_end -float(inf) for start, end in intervals: if start last_end: count 1 last_end end return count这道题真正的坑在两个地方。第一区间端点是否允许重叠如果题目允许“首尾相接”也就是前一个结束时间等于后一个开始时间也算不冲突那判断条件就是start last_end如果不允许就得改成start last_end。第二输入数据可能有乱序和重复排序前务必确认key取的是结束时间而不是开始时间重复区间不影响贪心结果但会影响你对答案的自信。区间调度往深了说还可以延展到会议室问题、任务调度、CPU进程调度。直播平台的转码任务分配本质上也是一个区间调度问题哪个任务优先用哪台转码机器要看任务紧迫度和资源空闲窗口。面试官可能会顺着这道题问你“如果有权重怎么办”那就变成了加权区间调度贪心失效要改成动态规划用二分加速到O(n log n)。这一层递进在面试中很常见笔试没考不代表面试不考复习时要把这个链条打通。2.3 动态规划最长上升子序列的O(n log n)解法A卷的动态规划题考的是最长上升子序列LIS输入一个数组输出最长严格递增子序列的长度。常规解法是O(n^2)的DP状态转移方程是dp[i] max(dp[i], dp[j] 1)其中j i且nums[j] nums[i]。但A卷明确要求时间复杂度O(n log n)这就需要用“贪心二分”的优化版本。优化版本的思路很巧妙维护一个数组dd[i]表示长度为i的最长上升子序列的末尾元素的最小值。遍历原数组时如果当前元素比d的最后一个元素大就追加到末尾否则在d里二分查找第一个大于等于当前元素的位置替换掉它。替换这个操作不会改变子序列的长度但能让后续元素有更多机会接上来这就是贪心思想在DP里的应用。import bisect def length_of_lis(nums): d [] for x in nums: idx bisect.bisect_left(d, x) if idx len(d): d.append(x) else: d[idx] x return len(d)这段代码看起来简单真正理解它需要想明白一个问题d数组里的值并不是一个真实的上升子序列它只是记录了每个长度的最小末尾值。比如nums [4, 10, 4, 3, 8, 9]d数组最终是[3, 8, 9]d[0]3d[1]8d[2]9但你并不能在原始数组里找到一个严格按这个顺序递增的子序列。这并不影响答案的正确性因为d[i]的定义保证了如果存在一个长度为i1的子序列那么末尾值一定大于等于d[i]。想清楚这一层这个算法才算真正掌握。笔试时如果时间紧张我建议先写O(n^2)拿部分分再优化到O(n log n)。部分分在算法笔试里是很重要的不是你AC了才有分而是你过了多少测试用例就拿多少分。这道题的后续延伸是“最长递增子序列的个数”以及树上LIS、二维LIS等变体大厂面试经常考建议大家把底层的贪心二分思想彻底吃透。3. 机器学习与深度学习基础考察3.1 分类算法与聚类KNN的K值怎么选A卷的选择题和简答题里机器学习部分考到了KNN和K-Means。有一道选择题问的是在KNN算法中K值的增大对模型偏差和方差的影响是什么。答案是K值增大模型偏差增大方差减小。为什么K值变大意味着决策时参考的邻居更多模型会变得更平滑对局部细节的捕捉能力下降所以偏差增大但对单一噪声样本的敏感度降低方差减小。这跟“过拟合和欠拟合”的经典权衡是一个道理。KNN本身是一种惰性学习算法训练阶段几乎不做什么事真正计算发生在预测时。因此在样本量大、特征维度高的场景下KNN的预测效率很低这也限制了它在工业界的应用。我们做推荐召回的时候几乎不会直接用KNN而是用向量检索替代但其核心思想——物以类聚、近朱者赤——在产品里无处不在。K-Means的考点集中在初始质心选择、距离度量、K值确定这三个地方。初始质心选不好容易陷入局部最优所以才有K-Means这种改进方法。K值怎么定常见做法是手肘法和轮廓系数法。手肘法看的是SSE误差平方和随K值变化的拐点因为拐点处的K值往往就是“性价比”最高的聚类数。轮廓系数法则是同时考虑簇内紧密度和簇间分离度取值范围在-1到1之间越接近1越好。如果你在简答题里遇到“如何确定K”把这两种方法都写出来再结合业务解释一下分数会明显不一样。另外分类算法里还有一个高频考点是距离度量。欧氏距离、曼哈顿距离、余弦相似度分别适用什么场景文本向量用余弦相似度因为文本向量的模长往往受文档长度影响余弦可以消除模长差异突出方向上的相似性。数值型特征用欧氏距离直观但要注意特征归一化否则量纲大的特征会主导距离计算。这些细节我在笔试时是靠刷面经总结出来的建议你也按照“算法原理适用场景优缺点”的结构去整理每个模型。3.2 模型评估与损失函数AUC和交叉熵A卷有一道题考AUC的含义选项里混了几个干扰项。AUC是ROC曲线下的面积表示随机正样本排在随机负样本前面的概率。如果你的模型对所有样本打分都是随机的AUC就是0.5如果是完美的排序AUC就是1。AUC的值不依赖具体的分类阈值所以它特别适合评估排序质量这也是为什么推荐系统和广告系统里那么看重AUC。不过AUC有一个问题它对正负样本比例不敏感所以样本严重不均衡时还要同时关注召回率、精确率或GAUC。简答题里让我写交叉熵损失函数的公式并解释为什么分类问题不用均方误差。交叉熵的公式是L -[y * log(y_hat) (1 - y) * log(1 - y_hat)]。不用MSE做分类的原因有两个层面。第一逻辑回归加MSE会让损失函数变成非凸函数梯度下降容易陷入局部最优第二交叉熵配上softmax梯度形式是(y_hat - y)梯度大小跟预测误差线性相关训练稳定而MSE的梯度里带sigmoid导数的项在预测值接近0或1时梯度几乎消失模型学不动。很多同学在复习损失函数时只背公式不理解背后的动机结果题目换个问法就懵了。比如考你“交叉熵和KL散度的关系”其实交叉熵等于熵加上KL散度机器学习里最小化交叉熵等价于最小化KL散度。这个知识点在热词里也有“kl elbo算法原理详解”ELBO在VAE里就是变分下界跟KL散度密切相关。你觉得考得偏其实这些都是算法工程师的基本功。3.3 深度学习必考概念过拟合、正则化、梯度消失深度学习的考察点并不深主要还是基础概念。有一道单选题问L1和L2正则化的区别答案是L1能把参数稀疏化L2把参数压缩到接近0但不等于0。为什么L1能产生稀疏解因为L1的约束区域是菱形尖点落在坐标轴上目标函数的最优解更容易出现在坐标轴的尖点上所以很多参数直接变成0。这个几何解释是高频考点建议记住。过拟合的解决办法可以列一个清单数据层面增加样本量、数据增强、欠采样/过采样模型层面降低模型复杂度、减少网络层数或参数量训练层面早停、正则化、Dropout、Batch Normalization集成层面Bagging、Dropout的本质也是训练多个子网络的集成遇到这类简答题我建议不要只写方法名要简单解释一下原理。比如Dropout为什么能缓解过拟合因为它每次训练随机让一部分神经元失活迫使网络学习到更鲁棒的特征而不是过度依赖某几个神经元。这种“原理作用”的答题结构能让阅卷人一眼看出来你是真懂还是背的。梯度消失和梯度爆炸也是必考。sigmoid函数在输入绝对值较大时梯度趋近于0多层反向传播梯度连乘后就消失了所以深层网络用ReLU这类激活函数。如果你被问到“为什么ReLU能缓解梯度消失”可以从正区间梯度恒为1来解释。但ReLU也有缺点神经元死亡问题负数区间梯度恒为0反向传播时该神经元永远得不到更新。所以后来才有LeakyReLU、PReLU这些变体。这些知识点在复习深度学习时都要串联起来而不是孤立地背。4. 直播场景应用题从音频重采样到推荐排序4.1 音频重采样算法为什么线性插值不行A卷的场景题里有一道音频重采样相关的题大意是直播过程中用户的网络环境不同播放端需要把接收到的音频从一种采样率转换成另一种采样率请说明重采样的原理并设计一个可行的实现方案。这道题当时让我愣了一下因为它不是单纯的算法题还涉及信号处理的基础知识。音频重采样的本质是采样率转换常见场景是把48kHz的音频转成44.1kHz或者反过来。最简单的思路是线性插值在两个已知采样点之间按比例插出一个新点。但线性插值在音频处理里是下策因为它等效于一个性能很差的低通滤波器会引入高频失真和混叠噪声。实际工程里一般用多相滤波器组或者基于FFT的重采样方案先把信号从时域变到频域在频域里完成采样率变换再逆变换回时域。我在答题时写了这样一条技术路线先做抗混叠滤波再做抽取或插值。因为降低采样率时如果信号中存在高于目标采样率一半的频率分量就会发生混叠所以必须先用低通滤波器把高频部分干掉再进行抽取。提高采样率时则需要插值并通过低通滤波消除镜像频谱。这种解释既专业又完整阅卷人一看就知道你有信号处理的基础。如果你只是写“用插值算法”而没提抗混叠这道题基本就拿不到高分。类似的信号处理算法在直播链路里还有很多。卡尔曼滤波用于去抖动和预测PID用于码率控制。A卷虽然没有直接考这些算法的推导但在场景题里提到过“如何优化弱网下的播放体验”这其实就是把卡尔曼滤波和PID串起来的经典问题。所以你不要只盯着教材里的理论要把它们放到真实场景里去理解。4.2 推荐系统中的协同过滤与排序场景题的第二问是推荐相关的直播平台首页有大量直播间如何为用户做个性化推荐请设计一个简化版的推荐系统并说明召回和排序两个阶段的做法。这类题在互联网公司笔试里很常见关键是看你能不能把经典算法讲清楚。我答题时给了一个比较中规中矩的方案召回阶段用协同过滤基于用户的协同过滤或者基于物品的协同过滤排序阶段用GBDT或逻辑回归做CTR预估。基于物品的协同过滤核心是计算物品之间的相似度矩阵直播场景里“物品”就是直播间两个直播间同时被一批用户看过就认为它们相似。用户点开某个直播间后可以给他推荐相似直播间。这个方案在计算复杂度上比基于用户的协同过滤更可控而且可以离线计算相似度矩阵在线只做查表排序。排序阶段是重头戏。特征工程上用户维度的特征有性别、年龄、活跃时段、历史观看时长内容维度有直播分类、标签、主播等级、在线人数上下文维度有当前时间、网络类型。把这些特征拼成一个样本交给GBDT训练输出一个点击概率再结合业务规则做最终排序。当时我还补了一句如果追求效果可以上双塔模型做向量召回用FM或DeepFM做排序。在笔试里写这种“经典方案可选升级”的结构能让阅卷人看到你的知识深度。4.3 实时音视频链路中的算法细节直播系统的体验受网络波动影响非常大A卷的问答里有一道题问推流端网络变差时如何用算法保证直播的流畅性我在回答时提到了PID算法和卡尔曼滤波的配合使用这跟我平时看的一些音视频工程文章有关。PID控制在直播里的一个典型应用是码率自适应。编码器可以基于网络带宽估计值动态调整视频码率但直接使用瞬时带宽估计很容易让码率剧烈抖动所以需要一个控制器让码率平滑变化。简单地说P项对误差立即反应I项消除稳态误差D项抑制超调。在带宽下降时PID控制器会渐进地降低码率避免画面突然模糊带宽恢复时再逐步上调避免频繁切换引发卡顿。卡尔曼滤波则常用于网络延迟和抖动估计。接收端每收到一个RTP包就能算出一个传输时间差样本但这个样本有噪声直接拿它做缓冲控制会不稳定。卡尔曼滤波能根据历史观测和运动模型递归地估计出真实延迟和延迟变化率。你不需要完整推导卡尔曼公式但至少要能画出状态转移和观测更新的基本结构然后解释它为什么能在有噪声的观测中保持平滑估计。这两个算法组合起来就是在弱网下保障直播体验的底层技术。写这类场景题的时候我最怕同学只写“用PID控制码率”而不展开。你至少要说清楚控制量是什么、被控对象是什么、反馈量是什么。好的回答应该是被控对象是编码器码率控制量是码率调整步长反馈量是从接收端回传的卡顿率或缓冲时长目标是把卡顿率控制在阈值以下。这样回答既体现工程思维又展现算法功底。5. 踩坑记录与备考复盘5.1 我在这次笔试中踩过的坑说实话这套A卷我做的时候并不是一帆风顺有几个地方现在想起来还觉得可惜。第一个坑出在KMP的next数组上我做题时默认了“最长相等前后缀长度”的定义结果题目给的定义是“失配时模式串指针回退的位置”两种定义在某些下标上差一位我在next[3]和next[4]上算偏了。所以还是那句话先审题再审题再审题尤其是算法基础题定义不同结果不同。第二个坑是区间调度那道题我一开始用了按开始时间排序的贪心样例过了但提交后只过了部分测试用例。后来复盘才意识到按开始时间排序的问题是一个很早起但是很长的区间会堵住后面所有区间导致结果偏小。按结束时间排序则没有这个问题。这种“样例能过、大数据挂掉”的情况在笔试里非常致命因为在线笔试不给你提示到底哪组数据没过只能靠你自己想清楚贪心策略的正确性证明。第三个坑暴露在音频重采样那道题上我只写了“用插值”三个字没有提抗混叠滤波。虽然不一定是零分但肯定没有踩到得分点。场景题最怕的是答得太浅算法选型、数据处理流程、实现细节、可能的优化点这四个层次写全了才能拿高分。所以我后面复习“算法加场景”类题目时都会刻意让自己按这个框架去组织答案。5.2 算法岗笔试的时间分配与答题策略经过这套卷子的洗礼我总结了一套自己的笔试时间分配策略。拿到卷子别急着做题先把所有题目扫一遍看看每道题的分值和难易程度心里有个谱。我的分配原则是分值高而且会做的题先做分值低但是要花很长时间的题放到最后。选择题一道一般只有一两分即使做对了对总分影响也不大但如果卡住十分钟后面二十分的大题可能就来不及了。代码题我是按照“先暴力后优化”的策略来写。比如LIS那道题如果一时间想不起O(n log n)的写法我会先把O(n^2)的DP写出来拿到部分分然后看剩余时间再优化。很多同学喜欢死磕AC结果一道题做一小时最后卷子没做完这是最不划算的。在实际笔试中AC率比题数更重要你要确保自己做的每道题都尽量拿到大部分测试用例的分数。场景题和简答题的答题框架也很重要。我一般用“先说结论再展开原理最后举例落地”的结构每个概念先给出定义或结论然后用一段话解释为什么最后结合直播场景说怎么用。这样改卷老师快速扫一眼就能抓住你的答题脉络。如果题目明确要求结合业务一定要把业务词糅进答案里比如“直播间推荐”“礼物打赏人群聚类”“弹幕实时过滤”哪怕只是举例也能让答案更贴题。5.3 后续复习路线建议考完这套A卷之后我重新调整了自己的算法复习路线这里分享出来供参考。基础算法部分我不再追求刷难题数量而是把高频考点分门别类做专项训练字符串KMP、Trie、AC自动机、排序快排、堆排、归并、动态规划背包、LIS、区间DP、图论Dijkstra、拓扑排序、并查集、贪心区间类、分配类。每个专题做十道左右典型题做到能默写模板的程度。机器学习部分我用“模型原理损失函数评估指标适用场景”的四段式结构整理了笔记每个模型都按这个框架过一遍。KNN、K-Means、逻辑回归、决策树、GBDT、随机森林、SVM是笔试和面试的常客把这些彻底吃透比什么模型都追新要靠谱。深度学习部分重点掌握多层感知机、CNN、RNN、LSTM的结构和各自优缺点以及调参技巧和防止过拟合的手段。如果时间充裕可以把常见的面试题整理成QA文档睡前过一遍。很多算法岗的笔试和面试考察内容其实高度重叠一份好的复习笔记能反复用。最后再分享一个实用小技巧我习惯把做过的场景题和热词里的算法概念归类存档比如音频重采样、PID控制、卡尔曼滤波、推荐召回排序这些每类写一段“业务背景技术方案可优化点”。这样遇到类似的场景题时我直接调取自己的知识库能节省大量现场思考时间。这套A卷虽然过去了几年但它的题型和考察思路在今天仍然有参考价值尤其是直播、音视频、推荐方向的算法岗备考逻辑一直没有变过。