vivo算法岗笔试复盘：从KMP到堆排序的备考指南

2024年秋招投vivo的时候我一度以为算法岗笔试就是纯LeetCode刷题直到真上了考场才发现事情没那么简单。两个半小时的在线笔试选择题和编程题混合出卷前面一堆概念题考的是KMP的next数组怎么手算、粒子群算法的速度更新公式、KL散度和ELBO的关系后面的编程题反而看起来“正常”很多。当时我就意识到vivo的算法笔试更看重“算法基本功机器学习原理工程思维”的组合能力不是刷三个月力扣就能应付的。这篇文章我想把这次笔试的完整复盘写出来包括题型结构、各模块的复习重点、编程题的答题策略以及笔试之后面试环节的衔接。如果你正在准备2025届或之后的秋招vivo算法类笔试这一关看这一篇就够了。1. 先把vivo算法笔试的题型结构搞清楚1.1 选择题考的是概念理解的“精确度”vivo的算法笔试不是全编程题而是“选择题编程题”的组合。选择题大概占40到50分覆盖数据结构、算法原理、机器学习、深度学习偶尔还会冒出一两道和vivo业务方向相关的题目。这里有个很容易踩的坑很多人复习算法笔试只刷题不背概念。但vivo的选择题恰恰喜欢考概念的精确表述。比如KMP算法题干专门标注了next[i]的定义方式要求你写出模式串pabacaba的next数组。这种题如果不熟练next数组的求解过程现场推导非常容易出错。再比如它可能会问在KMP算法中模式串pabacaba的next数组是什么这种题在力扣上根本遇不到只能靠你扎扎实实把串匹配的原理搞清楚。我复习的时候把next数组的手算过程用表格推了三遍才算真正过关。选择题还会涉及一些小众但重要的算法原理。比如粒子群算法的速度更新由哪几部分组成模拟退火算法中Metropolis准则的作用二分图最大匹配的匈牙利算法和HK算法的区别KL散度的不对称性以及它和交叉熵的关系快速幂算法的复杂度为什么是O(logN)堆排序建堆和调整的过程。这些内容看着杂其实都有一个共同点它们都是在考“你懂不懂原理”而不是“你会不会写代码”。我建议备考时每复习一个算法都问自己三个问题它解决什么问题它的时间复杂度为什么是这个它的边界条件是什么1.2 编程题难度梯度远比想象中大vivo编程题一般有2到3道难度梯度很明显。第一道通常是简单模拟或者基础数据结构题第二道是中等难度第三道就有点区分度了往往涉及动态规划、贪心、图论这类经典算法。有意思的是从最近的热搜词来看很多人考完都在搜索同一类问题排序算法、堆排序、Dijkstra、二分图匹配、贪心算法、快速幂。这说明vivo编程题考察的范围其实很“教科书”不会出特别偏门的题目但要求你基础足够扎实。我印象比较深的是编程题里有一道和“排序稳定性”有关。题目描述了一个场景要求实现一种排序算法并且要保证相同元素的相对顺序不变。这种题就是在考你对排序算法底层实现的理解哪些排序是稳定的哪些不稳定为什么不稳定怎么改造成稳定版本。所以我的建议是不要只背模板代码要把每种排序算法的比较次数、交换次数、空间复杂度、稳定性都搞清楚。这个积累不仅对笔试有用面试手撕代码的时候同样能让你多一层思考维度。2. 数据结构和基础算法的复习清单2.1 字符串与KMPnext数组必须能手算字符串算法几乎每年都出现在vivo笔试里。KMP又是字符串里最常考的一个。热词里“在KMP算法中对于模式串pabacaba其next数组”反复出现说明这是很多人的高频查寻点。KMP的核心是next数组而next数组的定义有两种常见版本。一种表示“当前字符之前的最长相同前后缀长度”另一种表示“失配时跳转的位置”。vivo的题目通常会在题干里明确给出定义但如果你只会背代码遇到不同的定义方式就会懵。我建议把next数组的手算过程练熟。以模式串abacaba为例p[0]a前后缀为空next[0]一般定义为0或-1取决于题目定义前缀ab最长相同前后缀为0前缀aba最长相同前后缀为a长度为1前缀abac最长相同前后缀为0前缀abaca最长相同前后缀为a长度为1前缀abacab最长相同前后缀为ab长度为2完整串abacaba最长相同前后缀为aba长度为3。整个过程可以列一张表每一行写当前前缀、最长相同前后缀、长度。练过三五个这样的例子之后现场手算就不慌了。如果再配合next数组的代码实现比如用C写一个计算next数组的函数那KMP这一类题基本就稳了。vectorint getNext(const string p) { int m p.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; }这段代码里j始终表示“已经匹配的前缀长度”。每次遇到不匹配就回退到next[j-1]这个回退过程就是KMP相比暴力匹配“不回溯主串指针”的精髓。2.2 排序与堆建堆、调整、堆排序一条龙排序算法是vivo笔试选择题的高频考点没有之一。热词里“数据结构排序算法”、“冒泡排序算法c”、“堆排序算法”扎堆出现说明大家都在为这一块补课。需要准备到的程度是这样的冒泡、插入、选择能写出正确代码知道时间复杂度和稳定性快速排序能手写partition过程理解为什么平均O(NlogN)、最坏O(N^2)归并排序能手写merge过程知道它稳定适合外部排序堆排序能手写建堆和调整过程知道它的空间复杂度是O(1)计数排序、桶排序、基数排序了解适用场景特别是当数据范围有限时线性排序能派上用场。堆排序是很多人的弱点我建议把它拆成三步来练。第一步给定一个乱序数组从最后一个非叶子节点开始向下调整构建大顶堆或小顶堆。第二步把堆顶元素和末尾元素交换然后对缩小后的范围重新调整。第三步重复第二步直到堆里只剩一个元素。写代码的时候有个细节特别容易错堆排序里的“向下调整”函数接收的参数应当是当前需要调整的节点下标和堆的有效长度不是整个数组的长度。每次交换堆顶后有效长度都要减1。这个细节在很多笔试代码题里会直接决定你能不能AC。2.3 图论与搜索从Dijkstra到二分图匹配图论部分vivo的笔试风格偏“应用”。Dijkstra算法是最常考的其次是拓扑排序、并查集偶尔会有二分图匹配。Dijkstra的考察点有两个一是朴素版的实现思路二是堆优化版的代码能力。朴素版适合稠密图复杂度O(V^2)堆优化版适合稀疏图复杂度O((VE)logV)。笔试如果出最短路径的题数据量大基本默认你得上堆优化。priority_queuepairint,int, vectorpairint,int, greater pq; dist[start] 0; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } }这个模板里if (d dist[u]) continue;就是“懒删除”的写法每次弹出的堆顶如果已经不是最短距离就直接跳过。它是堆优化Dijkstra的骨架必须背熟并且知道为什么这样写。二分图匹配的话匈牙利算法是基础HK算法是优化。说实话HK算法在笔试编程题里出现频率不高但选择题如果考“在二分图匹配中HK算法相比匈牙利算法的主要改进是什么”你得知道它用BFSDFS结合的方式把复杂度从O(VE)优化到O(E√V)。拓扑排序我建议用Kahn算法实现。思路是维护一个入度数组先把所有入度为0的点入队然后不断出队、更新相邻节点的入度、再把新的0入度节点入队。它不仅能判断一个有向图能不能拓扑排序还能顺便检测环。vivo笔试如果出“课程安排”或“任务调度”类题目Kahn算法就是标准解。2.4 容易被遗忘的小知识点快速幂、贪心边界与剪枝快速幂是一个“小而美”的算法。它考的不仅仅是代码更是一个数学原理a^b mod m可以把b看成二进制按位累乘。复杂度是O(logB)比循环累乘的O(B)快太多了。笔试如果考到大数幂运算快速幂几乎是唯一解。它经常以“模运算”的形式出现比如(a^b) % p这种题很多人能看懂但写不对原因是对取模运算的分配律不熟。贪心算法在这个环节里很特殊。它不指某一个具体算法而是一类“局部最优能得到全局最优”的问题。vivo笔试里的贪心题往往结合活动安排问题、区间覆盖问题、哈夫曼编码等。备考时不在于刷多少道题重点在于培养“怎么判断一道题能不能用贪心”的敏感度。我的经验是如果一个题目的选择策略可以用“排序之后依次处理”的方式证明那么它大概率是贪心题。剪枝算法在“搜索题”里很常见。笔试编程题如果出现DFS或者回溯裸搜必然超时必须会剪枝。最经典的几个剪枝思路可行性剪枝当前路径已经不可能到达答案、最优性剪枝当前结果已经不可能优于已知最优解、重复性剪枝用vis数组或者状态压缩避免重复搜索。这些技巧不用单独刷很多题把LeetCode的“组合总和”“N皇后”“单词搜索”吃透就够用。3. 机器学习与深度学习原理题的复习路径3.1 KNN与聚类从算法原理到应用边界vivo作为手机厂商算法岗位涉及的方向很多影像算法、推荐算法、语音算法、机器学习平台等。因此笔试选择题里会有一批机器学习基础题KNN和聚类是最常见的。热词里有一句很具体“knn算法的应用能力包括哪三个方面”。这引发了很多人搜索。常规的回答是分类、回归和异常检测或推荐。备考时不能只背这三个词还得能解释清楚KNN做分类时怎么投票做回归时怎么取平均做异常检测时怎么利用距离分布。KNN还有几个重要的细节容易被考到K值怎么选K太小会导致过拟合K太大又会让决策边界过于平滑距离度量方式欧氏距离、曼哈顿距离、余弦相似度各自适合什么场景特征缩放对KNN的影响非常大因为KNN是基于距离的算法量纲不一致会直接让某个特征主导距离。聚类算法里K-Means是核心。选择题会考它的迭代过程初始化、分配样本到最近中心、重新计算中心、迭代直到收敛。它和KNN的区别也经常被作为辨析题K-Means是无监督学习KNN是有监督学习。这两个“K”含义完全不一样很多人考完才意识到自己混淆了。3.2 KL散度、ELBO与VAE进阶考点没那么可怕如果说KNN和K-Means是送分题那KL散度和ELBO就是区分题。热词搜索里“kl elbo算法原理详解”出现频率很高说明这个点已经成了vivo笔试选择题的“常驻选手”。KL散度考得最多的性质是不对称性也就是KL(P||Q)不等于KL(Q||P)所以它不是一个真正的“距离”度量。这个坑每年都有人踩。如果选择题里出现“KL散度满足对称性”不用想直接判错。ELBOEvidence Lower Bound是变分推断的核心概念。选择题通常考它的推导关系logP(X) ELBO KL(q(z)||p(z|X))所以最大化ELBO等价于最小化KL散度。如果笔试里再深入一点会问ELBO的两项分别代表什么第一项是重构误差第二项是KL正则项。这就和VAE对应上了。VAE变分自编码器的复习建议是把它当作“生成模型”而不是“降维工具”来理解。它和普通自编码器的最大区别是在隐变量上添加了高斯先验并通过重参数化技巧来训练。选择题如果考到这里你只需要抓住“重参数化”和“KL散度”这两个关键词基本能定位到正确答案。3.3 强化学习、粒子群与模拟退火优化类问题怎么准备vivo笔试的选择题有时候会跳出一两题“非主流”算法题。粒子群算法、模拟退火算法都属于这一类。粒子群算法的原理一定得知道它的速度更新公式v wv c1r1*(pbest - x) c2r2(gbest - x)。选择题会问其中哪一项代表“个体认知”哪一项代表“社会认知”。w是惯性权重c1、c2是学习因子r1、r2是随机数。把这个公式拆开理解比死记硬背要容易得多。模拟退火算法考的是Metropolis准则当新解比当前解更优时一定接受当新解更差时以一定概率接受这个概率是exp(-Δ/T)。这个“以一定概率接受差解”的机制正是模拟退火能够跳出局部最优的关键。选择题如果问你“模拟退火和爬山法的本质区别”答案就是这点。强化学习在笔试里通常是基础题。会问到MDP四元组、折扣因子γ的作用、Q-learning的更新公式。备考时不需要深入策略梯度但Q-learning的更新式Q(s,a)←Q(s,a)α[rγ*maxQ(s,a)-Q(s,a)]要能默写出来。vivo的AI业务里有智能客服、个性化推荐等场景强化学习作为其中可选的技术方案笔试考到并不意外。3.4 信号与图像方向的专业算法题vivo毕竟是硬件厂商影像和音频是它的核心业务。因此算法笔试偶尔会出现音频重采样算法、图像锐化算法这类题目。这不是随机考而是跟公司业务强相关手机拍照需要图像信号处理音频播放需要重采样适配不同采样率的设备。图像锐化的拉普拉斯算法核心思路是对图像求拉普拉斯算子得到高频分量然后把原始图像加上或减去这个高频分量达到锐化效果。公式是g(x,y) f(x,y) - c*∇^2f(x,y)减号对应的是“高中心”掩膜。选择题可能会给出具体的卷积核问你它是在做平滑还是锐化。拉普拉斯核的中心为负数、周围为正数就是锐化核。音频重采样算法考的是概念为主从44.1kHz转换到48kHz本质是“插值”和“抽取”的组合。高频分量需要先做低通滤波否则会产生混叠。选择题如果问你“重采样时为什么需要低通滤波”答案就是抗混叠。这些题虽然出现频率不高但一旦出现就能筛掉不少只在力扣刷题、没有关注业务场景的候选人。所以备考时多想一想“这个算法在手机里会用在什么场景”对答题很有帮助。4. 编程题的答题顺序与部分分策略4.1 拿到题先做“题型判断”编程题3道时间通常只有90到120分钟。很多人的失败不是不会做而是时间分配出了问题。我的经验是拿到题先花5分钟把三道题都看一遍为每道题打一个标签。标签可以分成几类模拟题、数据结构题、DP题、图论题、贪心题。题目只要读完基本能判断出来。这样做的目的是不在一道题上耗死。我见过有人第一题卡了半小时结果后面两道题连看都没看。先扫一遍题哪怕只花3分钟都能有效避免“局部最优”的时间分配策略。4.2 时间不够时如何拿部分分vivo的编程题是按用例给分的。也就是说你即使算法不是最优只要暴力解法能在部分测试用例下通过也能拿到部分分。所以当一道题确定没有AC思路时可以先写一个正确的暴力解法保底。比如一道动态规划题状态转移方程没推出来可以先用DFS加备忘录写一个“能跑但是有冗余”的版本。等把暴力版本提交一遍、确认能过一些用例之后再回头优化。部分分的另一个拿法是用特判。比如题目明确了一些小规模输入时可以直接返回固定结果那就可以在代码里先加特判再走主逻辑。这在笔试中也算有效策略。4.3 边界条件与输入输出的坑编程题最容易丢分的地方不是算法本身而是边界条件。有一个我每次笔试前都会默念的检查清单数组为空时代码会不会越界只有一个元素时会不会直接崩溃输入的数很大时int会不会溢出题目要求输出“-1”表示不存在时你的代码有没有覆盖多组输入时每个用例的临时变量是否被正确重置。vivo的在线笔试系统用的是牛客或者赛码。这两种平台输入输出格式略有不同建议考前去官网熟悉一下。尤其是多行输入、每行多个整数这类场景写一个读取函数能节省大量时间。5. 笔试复盘与面试衔接5.1 考后如何做知识查漏补缺笔试结束之后第一件事不是放松而是趁记忆还热乎把题目里没做出来的知识点整理一遍。vivo笔试通常不会直接公布每道题的答案但你可以根据回忆把题复现出来。我在笔试后做了一次完整的复盘分了三个维度哪些选择题是概念记忆不牢导致的失分哪些编程题是思路正确但代码能力不够导致的超时或bug哪些知识点是完全没有接触过、需要重新学习的。如果你是算法基础没那么扎实的选手建议把“数据结构排序算法”“贪心算法”“快速幂”“Dijkstra”这四块放在最前面补。它们是vivo笔试的热点也是后续面试手撕代码的高频题。5.2 面试被追问时最容易被问到的知识点vivo的面试环节和笔试之间的联系比想象中紧密。面试官会拿到你的笔试记录如果你在某道编程题上花了很长时间或者没做出来面试会针对性追问。我后来被问到最多的是KMP、堆排序和KNN。KMP是考察你对next数组的定义和构造是否清楚堆排序是考察建堆的时间和空间复杂度KNN则是考察你能否结合业务场景说明它的应用。如果笔试时你KMP的next数组算错了面试官很可能会让你现场再算一个。所以我的建议是笔试结束到面试之间的几天不要把精力全放在新项目上把自己笔试答错的知识点重新会一遍。这个“笔试-面试衔接”的思路比漫无目的地刷题效率高得多。ESR还有一个小细节。vivo会让你填意向城市笔试通过后是各城市各自推进面试的。城市不同部门不同面试风格差异也大。但算法题的高频考点是稳定的数据结构、排序、机器学习原理、字符串匹配这几块一定要扎实。如果时间允许把粒子群、模拟退火、ELBO这类“非主流考点”也过一遍考场上的心态会稳很多。