当前位置：首页 > news >正文

映客算法笔试复盘：从KMP到卡尔曼滤波的硬核考点

news 2026/8/31 21:56:09

1. 先说说这份卷子为什么值得翻出来细看

1.1 一道春招卷，藏着一家公司对算法岗的全部期待

很多人对"直播公司的算法岗"有个刻板印象：不就是做推荐、做排序、调一调音视频参数吗？真正拿到映客2020春招算法A卷的时候，我才发现自己想简单了。这套卷子从字符串匹配考到PID控制，从KMP的next数组考到卡尔曼滤波，跨度大得让人一度怀疑自己投的是算法工程师还是"全栈算法工程师"。

不过换个角度想，这恰恰是直播业务的真实映射。映客这种以音视频互动为核心的产品，算法链路远比普通App长：内容推荐需要机器学习排序，直播流需要音视频处理，网络波动需要码率控制，风控需要规则引擎。所以一套算法笔试题覆盖多个方向，不是出题人随意拼凑，而是整个技术栈的缩影。

我建议准备算法岗笔试的朋友，别只盯着LeetCode刷题。先把目标公司的业务链路拆一遍，看看它最依赖哪些算法模块，再针对性复习，效率会高很多。这也是我复盘这份卷子时最大的感触。

1.2 从热搜词分布反推考察重点

把这份卷子相关的热搜词摊开看，能明显看出几个密集区：字符串与数据结构、机器学习与搜索排序、音视频处理、控制与规则引擎、安全算法。这些不是孤立的考点，而是映客这类直播产品技术体系的五个关键支撑。

字符串算法（KMP、BM25等）对应的是内容检索与匹配；
排序、贪心、堆等数据结构题是算法基本功；
聚类、KNN、强化学习等对应推荐与用户增长；
音频重采样、图像锐化、Sobel对应音视频处理链路；
PID、规则引擎对应播放控制与内容安全。

所以这份卷子的解题思路其实很清晰：先过基本功，再看机器学习，然后落到音视频和工程细节。下面我按这个逻辑，把每一类题的核心思路拆开讲。

2. 字符串与数据结构题：KMP、堆排序、快速幂的实战拆解

2.1 KMP的next数组：两种定义之间差了什么

热搜词里有一个很具体的题目描述："对于模式串 p='abacaba'，其 next 数组（next[i] 定义为...）"。这个题我印象太深了，因为KMP的next数组在不同教材和不同题库里有两种常见定义，答案完全不同。

第一种定义：next[i] 表示 p[0..i] 这个子串中，最长相等前后缀的长度（不包含子串自身）。按这个定义，模式串 abacaba 的 next 数组计算过程如下：

i	子串	最长相等前后缀	next[i]
0	a	无（长度不能为自身）	0
1	ab	无（'a'≠'b'）	0
2	aba	'a' 与 'a'，长度为1	1
3	abac	无	0
4	abaca	'a' 与 'a'，长度为1	1
5	abacab	'ab' 与 'ab'，长度为2	2
6	abacaba	'aba' 与 'aba'，长度为3	3

所以 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, mod=None): 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) 不稳定

贪心、二分、双指针这类题，答案本身往往不长，但边界条件很容易漏。比如二分查找的左右边界收缩条件是<还是<=，中间值取(left+right)//2还是(left+right+1)//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 delta

5.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)"，答案要点是：把字符串分成三类位置，递归构造其中两类的后缀排名，再线性合并得到完整后缀数组。这类题平时见到的概率不大，但真出现了，能答出一个核心思路就已经超过大多数考生。