1. 先说说这份卷子为什么值得翻出来细看1.1 一道春招卷藏着一家公司对算法岗的全部期待很多人对直播公司的算法岗有个刻板印象不就是做推荐、做排序、调一调音视频参数吗真正拿到映客2020春招算法A卷的时候我才发现自己想简单了。这套卷子从字符串匹配考到PID控制从KMP的next数组考到卡尔曼滤波跨度大得让人一度怀疑自己投的是算法工程师还是全栈算法工程师。不过换个角度想这恰恰是直播业务的真实映射。映客这种以音视频互动为核心的产品算法链路远比普通App长内容推荐需要机器学习排序直播流需要音视频处理网络波动需要码率控制风控需要规则引擎。所以一套算法笔试题覆盖多个方向不是出题人随意拼凑而是整个技术栈的缩影。我建议准备算法岗笔试的朋友别只盯着LeetCode刷题。先把目标公司的业务链路拆一遍看看它最依赖哪些算法模块再针对性复习效率会高很多。这也是我复盘这份卷子时最大的感触。1.2 从热搜词分布反推考察重点把这份卷子相关的热搜词摊开看能明显看出几个密集区字符串与数据结构、机器学习与搜索排序、音视频处理、控制与规则引擎、安全算法。这些不是孤立的考点而是映客这类直播产品技术体系的五个关键支撑。字符串算法KMP、BM25等对应的是内容检索与匹配排序、贪心、堆等数据结构题是算法基本功聚类、KNN、强化学习等对应推荐与用户增长音频重采样、图像锐化、Sobel对应音视频处理链路PID、规则引擎对应播放控制与内容安全。所以这份卷子的解题思路其实很清晰先过基本功再看机器学习然后落到音视频和工程细节。下面我按这个逻辑把每一类题的核心思路拆开讲。2. 字符串与数据结构题KMP、堆排序、快速幂的实战拆解2.1 KMP的next数组两种定义之间差了什么热搜词里有一个很具体的题目描述对于模式串 pabacaba其 next 数组next[i] 定义为...。这个题我印象太深了因为KMP的next数组在不同教材和不同题库里有两种常见定义答案完全不同。第一种定义next[i] 表示 p[0..i] 这个子串中最长相等前后缀的长度不包含子串自身。按这个定义模式串 abacaba 的 next 数组计算过程如下i子串最长相等前后缀next[i]0a无长度不能为自身01ab无a≠b02abaa 与 a长度为113abac无04abacaa 与 a长度为115abacabab 与 ab长度为226abacabaaba 与 aba长度为33所以 next [0, 0, 1, 0, 1, 2, 3]。第二种定义next[i] 表示当 p[i] 失配时模式串应该回退到的位置下标。这种定义下通常 next[0] -1然后后续数值有偏移。按这个定义abacaba 的 next 数组是 [-1, 0, 0, 1, 0, 1, 2]。我在笔试时吃过这个亏题目文字写的是最长相等前后缀长度结果我按跳转位置的定义填了答案白丢一道题的分。所以拿到KMP题第一件事不是动笔算而是先确认题目用的是哪种定义。如果题目给了next[i]的文字定义就严格按定义推如果没给默认按最长相等前后缀长度来做同时注意是否需要 next[0]-1。def get_next(p): n len(p) nxt [0] * n j 0 for i in range(1, n): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt p abacaba print(get_next(p)) # [0, 0, 1, 0, 1, 2, 3]这个实现对应第一种定义也是我平时写KMP最顺手的版本。笔试时不要现场推实现把模板背熟能省出大量时间给后面的大题。2.2 堆排序的空间复杂度与快速幂的二进制思维堆排序和快速幂是笔试常客但每次考的点不太一样。堆排序常见的追问有三个时间复杂度、空间复杂度、稳定性。堆排序建堆是 O(n)每次调整是 O(log n)整体时间复杂度稳定在 O(n log n)。它最突出的优点是空间复杂度能做到 O(1)因为完全可以用原数组存储堆结构不需要额外数组。但注意堆排序是不稳定的同样关键字的元素在排序后可能改变相对顺序这在面试里经常被追问。我当时在卷子上写堆排序时特意标注了原地建堆、原地排序并解释了建堆从最后一个非叶子节点开始的原因——下沉调整可以保证每个子树先满足堆性质自底向上逐步构建整体堆。这样写阅卷人能看出你不是背代码而是真懂原理。快速幂的核心是二进制分解。比如求 a^n把 n 拆成二进制形式从最低位开始每次将底数平方只有当前位为1时才累乘到结果中。原理和通过乘法快速替代连乘是一样的时间复杂度从 O(n) 降到 O(log n)。def fast_pow(a, n, modNone): res 1 while n 0: if n 1: res res * a if mod is None else (res * a) % mod a a * a if mod is None else (a * a) % mod n 1 return res快速幂在密码学、大数运算、概率计算里经常出现。如果卷子上有模运算的题记得每一步都取模防止中间结果溢出。笔试题不会只考一个孤立的快速幂通常会把它包装成某个实际问题比如倒置链表、循环节计算、大数幂取模等。2.3 贪心与其他经典题型的答题节奏贪心算法在笔试题里出现的频率很高但考的不是能不能想到贪心而是能不能证明贪心正确。活动选择问题、区间调度、找零钱这些都是经典题。我当时答题时习惯先给出贪心策略再用反证法或交换论证法简单写两行证明哪怕不完整也能展示思路。排序算法类的题目我建议把各种排序的复杂度、稳定性、适用场景整理成一张表放在脑子里。笔试时遇到请设计一个时间复杂度O(n log n)且稳定的排序算法第一时间想到归并排序遇到内存受限要求原地排序就选堆排序。这些判断一定要形成条件反射。排序算法 平均时间 最坏时间 空间 稳定性 冒泡排序 O(n²) O(n²) O(1) 稳定 快速排序 O(n log n) O(n²) O(log n) 不稳定 归并排序 O(n log n) O(n log n) O(n) 稳定 堆排序 O(n log n) O(n log n) O(1) 不稳定贪心、二分、双指针这类题答案本身往往不长但边界条件很容易漏。比如二分查找的左右边界收缩条件是还是中间值取(leftright)//2还是(leftright1)//2这些细节直接决定能否通过全部测试用例。我在A卷上做二分变种题时就因为mid的取整方向写反跑挂了两组边界数据这种失误太可惜了。3. 机器学习算法题把推荐和搜索赛道的基本功吃透3.1 聚类、KNN与用户分群从三个应用能力说起热搜词里有一条knn算法的应用能力包括哪三个方面这个表述很像是某道简答题的原文。KNN的三个经典应用方向是分类、回归、缺失值填充或异常检测。分类是最常见的比如根据用户行为特征判断其是否可能付费回归可以预测用户的使用时长缺失值填充则利用近邻样本的信息估计缺失特征。不过直播平台的KNN应用场景更贴近用户分群和相似用户推荐。登录映客这类产品时系统会根据你的年龄、地区、观看偏好找到与你最相似的一群用户然后把他们喜欢的主播推给你。这个逻辑本质上就是KNN的思路找K个最近邻汇总他们的行为偏好排序生成推荐列表。聚类和KNN经常一起考。有一道比较经典的简述题是K-Means和KNN有什么区别。K-Means是无监督学习KNN是有监督学习K-Means用于聚类KNN用于分类/回归K-Means训练过程是迭代更新聚类中心KNN训练过程只是存储样本。笔试时如果遇到这种对比题从有监督/无监督用途训练过程三个维度作答就能拿全分。3.2 强化学习、模拟退火与BM25直播场景里的隐藏考点强化学习在直播平台最典型的应用是推荐策略优化。主播和用户之间的匹配是一个不断试错、不断获得反馈的过程推荐一个主播用户停留时间长、送礼了就是正向奖励用户秒退就是负向奖励。强化学习的智能体在这种环境下学习最优的推荐策略本质上和AlphaGo学下棋的逻辑一致。模拟退火算法在热搜词里出现大概率是作为全局优化算法考察。这个算法的思想很有意思物理退火时高温让粒子自由移动温度降低后粒子逐渐稳定到低能状态。对应到优化问题里算法以一定概率接受比当前解差的新解这个概率随温度下降而减小从而跳出局部最优寻找全局最优。BM25是搜索排序里的经典算法腾讯视频ckey、内容搜索等场景经常用到。BM25的核心是计算查询词和文档之间的相关性得分它融合了词频、逆文档频率和文档长度归一化三个因素。笔试考BM25时往往不是让手写完整公式而是问它和TF-IDF有什么区别——BM25对词频有饱和机制一个词出现太多次时增益会递减而TF-IDF中词频是线性增长的。3.3 粒子群、剪枝与XGBoost扩展知识面的正确姿势粒子群算法PSO是一种模拟鸟群觅食行为的群体智能优化算法。每个粒子代表一个候选解粒子在搜索空间里飞行速度和方向受自身历史最优位置和群体历史最优位置影响。在算法岗笔试中粒子群常作为启发式优化算法的代表被考察与遗传算法、模拟退火并列为三大经典。剪枝算法在直播场景里最直接的应用是搜索树剪枝和推荐候选集剪枝。比如用Minimax算法做井字棋AI时通过alpha-beta剪枝可以大量减少搜索节点让AI在有限时间内算出最优落子。这个知识点在热搜词里单独出现了井字棋minimax算法实现详解说明出题人可能想考察递归搜索与剪枝的结合。XGBoost和聚类算法则是业务实战中的常客。XGBoost在特征稀疏、数据量大的场景下表现突出适合做用户付费意愿预测聚类则用于主播分类、内容标签聚合。这部分知识不一定在笔试中单独出计算题但很可能以简述你熟悉的机器学习算法及其适用场景这类开放性问题出现平时积累几个有深度的案例很有必要。4. 音视频链路里的算法细节重采样、图像锐化与卡尔曼滤波4.1 音频重采样直播场景避不开的基本功直播里不同端的音频采样率常常不一致主播端可能是48kHz观众端播放器可能要求44.1kHz或者需要从48kHz降到16kHz用于语音识别。这个转换过程就是音频重采样。最简单的重采样是线性插值但工程上更常用的是多相滤波器组或基于FFT的重采样方案。多相滤波器的思路是设计一个低通滤波器然后按采样率转换比例抽取或插值再通过多相结构把计算量降下来。笔试如果考重采样原理一般会从三个方面问为什么需要抗混叠滤波器、插值和抽取的顺序是什么、采样率转换比例是整数还是分数时处理有什么区别。我当时看到音频重采样算法这个热搜词第一反应是出题人可能的问法是直播中回声消除的延迟是如何影响重采样设计的。因为回声消除需要把远端参考信号重采样到近端采样率重采样的精度直接影响回声路径估计的准确性。这类题没有标准答案但抓住采样率匹配和滤波器设计两个核心点就能答到点子上。4.2 拉普拉斯与Sobel图像锐化和边缘检测的题眼图像锐化是直播美颜、特效模块的基础。拉普拉斯算子是一个二阶微分算子它突出图像中灰度突变的地方。用拉普拉斯算子锐化的标准公式是g(x, y) f(x, y) c * ∇²f(x, y)其中 f 是原图像∇²f 是拉普拉斯算子作用后的结果c 是增强系数。拉普拉斯算子常用的离散卷积核是0 -1 0 -1 4 -1 0 -1 0或者带对角线扩展的版本。卷积核的本质是中心像素乘以4减去上下左右四个邻域像素结果能提取出边缘信息。把边缘叠加回原图图像看起来就更清晰锐利。Sobel算子则是一阶导数的近似它有两个方向核分别计算水平梯度和垂直梯度Gx [-1 0 1; -2 0 2; -1 0 1] Gy [-1 -2 -1; 0 0 0; 1 2 1]图像在某像素点的梯度幅值约等于 sqrt(Gx² Gy²)。笔试时如果让手写Sobel边缘检测的步骤就是灰度化、分别与Gx和Gy做卷积、求幅值、阈值二值化。这几个算子我在直播图像处理项目里反复用过美颜的皮肤平滑、特效的边缘增强底层都是这些东西。4.3 卡尔曼滤波从抖动的网络里读出真实码率卡尔曼滤波是信号处理与控制领域绕不开的经典算法。直播推流过程中网络带宽是波动的TCP拥塞窗口、发送缓冲区的长度都在变直接测量这些值得到的码率估计值会剧烈抖动。卡尔曼滤波做的事情是通过一个状态空间模型把含有噪声的观测值和系统的运动规律融合起来估计出真实状态。具体到直播场景可以把网络可用带宽看作系统的状态 x观测值 y 是当前的吞吐量或延迟变化。系统模型是带宽缓慢变化过程噪声小观测模型是吞吐量受随机干扰观测噪声大。卡尔曼滤波的迭代分两步预测用上一时刻的状态估计当前状态和更新用当前观测值修正预测结果。笔试题里如果要写卡尔曼滤波的五个核心公式基本是预测 x_pred F * x_prev P_pred F * P_prev * F^T Q 更新 K P_pred * H^T * (H * P_pred * H^T R)^(-1) x_new x_pred K * (z - H * x_pred) P_new (I - K * H) * P_pred这套公式在笔试中不一定要求完整默写但至少要能解释每个变量的含义F是状态转移矩阵H是观测矩阵Q是过程噪声协方差R是观测噪声协方差K是卡尔曼增益。理解预测更新的框架比死记公式更重要。5. 规则引擎、控制类算法与安全算法算法岗的跨界题5.1 Rete算法规则引擎Drools的事实匹配过程看到规则引擎drools的rete算法实现原理和事实匹配过程这个热搜词时我愣了一下因为规则引擎通常不在算法岗笔试的常规复习范围内。但仔细想想直播平台的内容安全、用户风控、审核策略都非常依赖规则引擎考这个并不突兀。Rete算法的核心思想是利用规则结构的相似性减少重复匹配计算。它构建一个网络包含Alpha节点条件匹配单个事实的简单条件和Beta节点多个事实之间关系的联结。当新事实进入工作内存时它沿着网络传递只经过与它相关的路径而不是把每一条规则都重新匹配一遍。笔试如果考Rete最可能出的简答题是请简述Rete算法相比朴素匹配的优势。答案要点是保存了规则匹配的中间状态避免重复计算支持增量更新新增事实时只传播受影响的路径规则多、事实多时效率提升显著。我有个朋友在风控系统里用Drools写了几百条规则匹配性能要求极高Rete算法就是支撑这种场景的关键。5.2 PID、MPPT与FOC控制算法背后的工程思维PID控制算法在热搜词里有pid算法、增量式pid算法、pid算法在crps psu power的作用好几条。PID是比例-积分-微分控制器的缩写根据误差的比例项、累积项和变化趋势项来计算控制量。公式是u(t) Kp * e(t) Ki * ∫e(t)dt Kd * de(t)/dt增量式PID是数字控制中常用的变体它输出的是控制量的增量而不是绝对控制量好处是执行器可以平滑过渡误动作影响小而且不需要累加历史误差不容易积分饱和。MPPT最大功率点跟踪在光伏发电、电源系统里负责让设备始终工作在最大输出功率点附近。FOC磁场定向控制则广泛应用于无人机云台、电机控制中。这几个算法虽然更偏硬件和自动化但出现在直播公司算法试卷里很可能是结合了具体业务场景比如直播间的智慧灯光控制、电动云台的稳定跟随、服务器电源的功耗管理。如果让你现场手写一个PID的代码记住增量式PID的实现会比位置式更简洁class IncrementalPID: def __init__(self, Kp, Ki, Kd): self.Kp Kp self.Ki Ki self.Kd Kd self.last_err 0 self.prev_err 0 def update(self, target, current): err target - current delta (self.Kp * (err - self.last_err) self.Ki * err self.Kd * (err - 2 * self.last_err self.prev_err)) self.prev_err self.last_err self.last_err err return delta5.3 弱哈希修复与国密算法安全方向的基本常识热搜词里有一条ssl证书使用了弱hash算法cve-2005-4900怎么修复这也是算法岗可能会碰到的实际安全问题。CVE-2005-4900涉及使用弱哈希算法如SHA-1签名的SSL证书主要修复手段是用SHA-256或更强的哈希算法重新生成证书签名请求向CA重新申请证书如果内网自签名证书需要更新签发策略并重新部署到所有信任链节点同时检查服务端SSL配置禁用不支持强哈希的加密套件。这里要注意的是证书的哈希算法和加密算法是两回事。哈希算法用于证书签名加密算法用于TLS握手时的密钥交换。修复弱哈希问题核心动作是换签名算法而不是换加密套件。我在实际项目里修过类似问题尤其是一些老旧的内部系统证书链里藏着SHA-1签名的根证书或中间证书光换叶子证书不检查整条链问题依然存在。SM2、SM3、SM4和ZUC是国密算法体系分别对应公钥加密、哈希、分组加密和流加密。有些企业级项目会要求支持国密算法尤其是在政务、金融场景。算法岗笔试即使不细考国密算法的实现细节也可能会问它们和AES、RSA、SHA-256的区别。答这类题的关键是明确SM2基于椭圆曲线SM3输出256位摘要SM4分组长度128位ZUC是祖冲之序列密码。5.4 内容签名与版权保护一个容易被忽略的考点热搜词里还有腾讯视频ckey5.x算法_php版这和视频内容的防盗链、版权保护有关。视频平台会在播放请求中附加签名参数服务端校验签名是否合法、是否过期、是否为特定设备生成。这类算法的核心是请求参数密钥时间戳的签名逻辑通常是一套带特定排列和哈希的算法。我不建议为了笔试去研究某个具体视频平台的签名逆向那是另一个领域的事了。但算法工程师应当理解内容签名和防篡改背后的通用原理是HMAC或RSA签名核心是密钥不出客户端、签名可验证、时间戳防重放。答题时能说清楚这个原理已经能体现对该方向的理解。5.5 工业异常检测与DC3算法边角知识也有存在感工业异常检测算法和dc3算法出现在热搜词里说明这份卷子的考察范围并不局限于常规算法题。工业异常检测通常用重构误差来判断样本是否异常训练一个自编码器正常样本的重构误差小异常样本的重构误差大设定阈值即可区分。这个思路在直播场景的异常流量检测、黑产账号识别中也能迁移使用。DC3算法是线性时间构造后缀数组的算法属于字符串算法的进阶内容。KMP解决单模式匹配后缀数组解决多模式匹配、最长公共子串等问题。如果笔试里考到DC3大概率是问相比倍增加法O(n log n)DC3为什么能做到O(n)答案要点是把字符串分成三类位置递归构造其中两类的后缀排名再线性合并得到完整后缀数组。这类题平时见到的概率不大但真出现了能答出一个核心思路就已经超过大多数考生。6. 现场笔试的答题顺序与复盘总结6.1 我的答题策略先扫一遍全卷再按性价比切题拿到A卷后我习惯先花5分钟快速浏览全部题目标注难度和预估耗时而不是从第一题开始硬做。我的优先顺序是有明确答案的基础题如KMP next数组、排序复杂度先做中等难度的算法实现题快速幂、堆排序次之简述题如Rete算法原理、PID在业务中的作用再往后最后啃综合大题的硬骨头。这样做的好处是保证基础分先落袋不至于在一道大题上卡太久导致后面会做的题没时间写。我当时估算每道题的时间是选择题/填空题每题2分钟代码题每题10-15分钟简述题每题5分钟大题20分钟。总分分配和时间分配对上了考试才不会慌。6.2 我踩过的坑与改进方向现在回头复盘有几个坑值得提醒正在准备笔试的朋友。坑一是看到熟悉的题就掉以轻心。我在KMP那道题上就是因为太自信没看清题目对next数组的定义结果填错了。无论多熟悉的题下笔前把题目要求完整读两遍尤其是那些定义为注意后面的文字。坑二是填空题留白。有些题不会做就直接跳但算法卷的填空题、简答题往往有按点给分的潜规则哪怕只写出部分公式、部分思路也能拿一些步骤分。用代码实现题尤其如此写出一个可运行但不够优化的版本分数会比空着高很多。坑三是不注意代码的边界条件。快速幂没取模、二分查找没有处理空数组、递归没有出口这些是笔试代码最常见的问题。我后来养成一个习惯写完代码后先用一个极简的测试用例在草稿纸上走一遍比如数组长度为0或1、n为0或1的场景能提前发现大部分bug。6.3 适合大多数人的备考Checklist根据这份A卷的考点分布给自己列一个备考清单字符串算法KMP的next数组两种定义、后缀数组基本概念、BM25核心公式数据结构排序时间复杂度与稳定性、堆排序手写、快速幂、二分查找边界机器学习聚类与KNN区别、XGBoost适用场景、强化学习基本流程、模拟退火思想音视频音频重采样原理、拉普拉斯与Sobel卷积核、卡尔曼滤波公式框架工程算法PID与增量式PID代码、Rete算法匹配过程、异常检测思路安全基础弱哈希修复步骤、国密算法分类、内容签名通用原理。这份清单并不追求每个点都深挖到论文级但对于一场算法岗笔试来说覆盖面已经足够了。关键是每个方向都能说出是什么、为什么、怎么用。我后来把这份卷子给准备校招的几个学弟学妹看过他们反馈最有用的是KMP的next数组定义对比和PID增量式实现那段因为网上的资料很少把笔试中的定义差异讲得这么细。也正是这些看起来简单但容易踩坑的知识点才最能拉开考生之间的差距。如果你也正在准备算法岗笔试不妨把这份卷子当作一份模拟题来限时训练做完之后再对着自己的薄弱点专项突击。算法笔试考的从来不只是会不会更是在有限时间内能不能稳定做对这个能力只能靠反复实战来打磨。