2020年映客春招算法A卷我印象挺深。当时直播行业正处于风口映客作为老牌移动直播平台算法题出的很有业务味儿不搞那种纯ACM的偏难怪题反而把字符串、排序、动态规划这些基础算法往弹幕、排行榜、推荐场景里套。后来我在帮学弟学妹做校招辅导时发现这套卷子的出题逻辑很有代表性考的不是你会不会背模板而是你能不能把算法用到“直播间真实问题”里。这篇文章适合两类人看一类是正在备战校招算法笔试的同学想快速了解直播类公司算法卷的方向和难度另一类是已经拿到卷子、卡在某些边界条件里出不来的人可以对照我整理的解题思路和代码模板自查。我会尽量把做题时的推演过程写完整包括在草稿纸上怎么画、遇到哪些情况容易翻车以及为什么有些题必须用某个算法而不是另一个。如果你是第一次接触这类笔试建议先按顺序读如果你已经在刷题可以直接跳到第4章看避坑清单。1. 这份A卷考什么先看懂出题人的意图1.1 试卷结构与难度梯度映客2020春招算法A卷整体结构基本沿用了当年互联网公司校招的主流形式单选题加多选题用于快速过滤基础概念编程题用于考察真实编码能力。我当时拿到的试卷分三块单选题大概10道每道题覆盖一个核心知识点难度不高但覆盖面很广数据结构的性质、时间复杂度的比较、网络协议的基础常识都会涉及多选题5道左右这个模块最大的坑是“少选多选都不得分”所以不确定的选项宁可不选最后是编程题一般是4到5道从易到难排开。编程题的难度梯度很有规律前两道属于热身题基本是链表操作、数组遍历、字符串处理这类的模板题只要基础扎实就能快速拿下。中间一到两道是主流难度通常会把排序、二分、哈希、动态规划这些核心算法藏在一个业务场景里比如给一堆弹幕找出出现次数最多的词、给一个粉丝团列表算出在线时长TopK。压轴题才是真正拉开差距的地方它往往考察的是数据结构的组合使用或者比较巧妙的思维比如区间问题、滑动窗口、单调栈、甚至状态压缩DP这类题不仅要求你能写出来还要能卡着时间复杂度的边界优化到最优解。整套卷子的做题时间一般是90到120分钟编程题不要求你跑通完整的OJ环境很多时候给你一个核心函数让你补全或者让你直接在答题区写伪代码。我见过不少同学在选择题上纠结太久导致后面编程题时间不够这是最可惜的失分方式。我的建议是选择题平均每题控制在1分钟以内多选题最多给2分钟把大量时间留给编程题因为编程题一道的分值往往顶得上好几道选择题。1.2 直播业务在考察点里的映射出题人为什么要这么考说白了是因为映客的核心业务就是直播算法题必须能跟业务场景对上。直播平台每天会产生海量弹幕弹幕里夹杂着广告引流、辱骂、违规内容这部分就需要字符串匹配和敏感词过滤所以字符串算法基本是必考项KMP、AC自动机、字典树这些知识点会反复出现。热门直播间会有礼物榜单、粉丝团榜单、小时榜榜单本质上就是TopK问题考察的是堆排序和快速选择推荐系统要给用户推直播间里面会用到排序、协同过滤、相似度计算这些更偏机器学习的算法但笔试阶段通常只考它们的基础——排序和哈希。还有一类业务场景是连麦、PK、音画同步这里面有音频重采样、卡尔曼滤波、PID控制这类偏信号的算法但笔试基本不会硬考偶尔会出现在选择题的概念题里。我后来和做直播后端的朋友聊过他说实际工程里这些算法确实在用但校招笔试考察的是你的算法基本功而不是具体的工程算法实现所以只要你能理解卡尔曼滤波是干什么的、PID的三个参数各管什么就足够应付概念题了。换句话说别把这份A卷想成玄学它的出题逻辑非常清晰先确认你数据结构基础扎实不扎实再看你能不能把高频算法用到具体场景里。你把这层逻辑想明白了做题的时候就不会被各种包装过的题目搞晕剥开场景的外壳底下还是那些你熟悉的经典算法。2. 高频题型逐个拆解每一类都要有保底思路2.1 字符串算法KMP的next数组到底怎么算字符串匹配是映客这类直播公司笔试的常客因为弹幕敏感词过滤、昵称合法性校验、URL解析全都要用到。A卷里如果出现字符串题大概率会考察KMP而且很容易直接在题目里抛出一个模式串让你手算next数组。热词里提到的那个例子非常典型“模式串 pabacaba求其next数组”。这道题看起来简单但每年都有大量同学栽在next数组的定义和边界处理上。先统一口径。KMP里的next数组按主流教材有两种定义方式。第一种是前缀函数写法next[i]表示“模式串前i1个字符组成的子串中最长的相等真前后缀的长度”。第二种是失配跳转表写法next[i]表示“当第i位字符失配时模式串指针应该跳转到的位置”这种写法通常会把前缀函数整体右移一位并在开头补-1。以pabacaba为例我按前缀函数定义手算一遍这个表你可以直接当模板记子串长度对应子串最长相等真前后缀前缀函数值1a无02ab无03abaa14abac无05abacaa16abacabab27abacabaaba3所以 pabacaba 的前缀函数数组是 [0, 0, 1, 0, 1, 2, 3]。如果你用的是失配跳转表定义那就是 [-1, 0, 0, 1, 0, 1, 2]。这两个答案在不同教材里都是对的但考试时一定要看清题目给的next[i]定义否则写错一个符号就是全错。还有一个高频细节是如果题目要求用KMP完成一次匹配那么模式串匹配成功之后不能直接break而是要把 j 回退到 next[j-1]才能继续统计重叠出现的次数。我写过很多次KMP最常踩的坑就是while循环里忘记判断 j 0导致数组越界。下面是完整的KMP计数模板可以直接背。def prefix_function(p): n len(p) pi [0] * n for i in range(1, n): j pi[i - 1] while j 0 and p[i] ! p[j]: j pi[j - 1] if p[i] p[j]: j 1 pi[i] j return pi def kmp_count(text, pattern): if not pattern: return 0 pi prefix_function(pattern) j 0 cnt 0 for ch in text: while j 0 and ch ! pattern[j]: j pi[j - 1] if ch pattern[j]: j 1 if j len(pattern): cnt 1 j pi[j - 1] return cnt2.2 排序与TopK排行榜场景的取舍排行榜在直播平台里太常见了热门礼物榜、粉丝团榜、观看时长榜本质都是从一个很大的集合里取前K个。笔试里如果考排序很少直接让你写一个完整的快排而是会把问题包装成“给10万个主播ID按礼物数排序后输出前100名”这种业务题。这种题考察的核心是你知不知道排序算法之间的复杂度差异以及TopK为什么要用堆而不是全量排序。先看一张对照表笔试选择题经常考排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定快排O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定如果你要全量排序通常选快排因为平均常数小如果对稳定性有要求选归并如果只是找TopK最优方案不是全排序而是维护一个大小为K的小顶堆。小顶堆的意思是堆顶永远是堆里最小的元素当新元素比堆顶大时就替换堆顶并调整这样遍历完所有数据后堆里留下的就是最大的K个元素。这样做的复杂度是 O(n log K)当K远小于n时比全排序高效得多。我在这里强调一个容易错的地方找前K大的数用“小顶堆”找前K小的数用“大顶堆”。很多同学一听到“前K大”就下意识用大顶堆结果堆顶永远是最大的那个无法淘汰足够小的元素最后堆里装不下K个正确的值。做题前先在草稿纸上画一遍数据流想清楚堆顶元素到底是要淘汰谁。2.3 动态规划与贪心怎么快速判断该用哪个动态规划是笔试压轴题的常客也是拉开分数的主要模块。A卷里的DP题一般不会太难常见的有背包问题、最长递增子序列、编辑距离、爬楼梯变体、区间DP等。我自己的经验是做DP题不要一上来就想着写代码先在草稿纸上完成五步定义状态写出转移方程确定初始值确定遍历顺序最后再考虑空间优化。这五步里任何一步卡住了都说明你对题目理解还不到位。以最长递增子序列LIS为例经典做法是定义 dp[i] 表示“以 nums[i] 结尾的最长递增子序列的长度”转移方程是dp[i] max(dp[j] 1)其中 j i 且 nums[j] nums[i]。初始化时每个元素的 dp[i] 1因为单个元素自己就是一个递增子序列。遍历顺序从左往右最终答案取整个dp数组的最大值。这个版本的时间复杂度是O(n^2)如果数据规模到了10^5量级就需要用“辅助数组加二分”的优化版本把复杂度降到O(n log n)。贪心算法则不一样它不需要状态转移核心在于每一步都做局部最优选择。但贪心能用的前提是“全局最优可以由一系列局部最优组成”这需要严格证明或者至少举不出反例。笔试里我用一个很实用的判断方法如果这道题你隐约觉得“每一步选最大的/最小的就行了”那很可能在考贪心但如果发现局部最优会导致后面没得选那就该改用DP。比如经典的找零钱问题如果硬币面额是1、5、11要找15元贪心会选11加4个1共5枚但最优其实是3个5所以这个题不能贪心必须DP。做题时多花30秒验证一下反例比写完代码再调试省时间得多。2.4 二分查找的边界处理二分查找看起来简单但每次笔试都有人写错而且不是错在思路上而是错在边界条件上。A卷里的二分题通常不会直接说“请你二分”而是包装成“在一个有序数组里找目标值”或者“找一个满足条件的最小值/最大值”比如在升序数组里找第一个大于等于target的位置。二分最核心的坑是区间定义不统一。我习惯用“左闭右闭”的写法while (l r)mid (l r) // 2当 nums[mid] target 时l mid 1否则 r mid - 1。让我给出一个完整的模板def lower_bound(nums, target): # 返回第一个 target 的下标如果不存在返回 len(nums) l, r 0, len(nums) while l r: mid (l r) // 2 if nums[mid] target: l mid 1 else: r mid return l这个模板用的是“左闭右开”区间好处是最终 l 和 r 会收敛到同一个位置不需要纠结返回l还是r。实际写的时候有两个稳定的小技巧第一mid取中间值用 (l r) // 2 而不是 (l r) // 2 的变体当心整数溢出可以用 l (r - l) // 2但在Python里没这个问题第二判断条件里到底是 还是 取决于你要找的是“第一个符合条件的”还是“最后一个符合条件的”。我建议你固定记住一个模板考试时只改判断逻辑不要临场换区间风格那是翻车的最主要原因。3. 完整做题流程模拟像考试一样走一遍接下来我模拟一套典型的A卷做题流程。要说明的是这套模拟题是根据映客这类直播公司校招笔试题型整理的不是原卷原题但题型和难度贴近真题你可以把它当作考前演练。3.1 开考前5分钟通读全卷给题目分类打标拿到卷子后的前5分钟千万不要动手做题。先把所有题目扫一遍在每道编程题旁边标上难度一眼就能想到解法的标“易”需要构思一下的标“中”暂时没有思路的标“难”。然后检查一下总题量合理分配时间。我一般会把时间切成三块选择题用30%中等编程题用35%压轴题用25%剩下10%用于检查和填坑。分类打标的好处是一旦你发现某道题超过10分钟还没有头绪可以果断跳过先去做后面的容易题。很多同学喜欢死磕一道题结果一道题花了40分钟后面的题仓促写完甚至没写分数反而更低。考试本质是拿分效率的博弈不是证明自己每个题都能做出来。3.2 编程题1的完整实现字符串匹配模拟题给定一个文本串T和一个模式串PP的长度不超过10^5统计P在T中出现的次数要求O(n)复杂度。这个问题直接用2.1节的KMP模板就能解决。我先用草稿纸推演一下比如 Tabababa, Paba肉眼可以看到P出现了3次重叠部分也算分别是下标0、2、4。用KMP跑一遍先计算P的前缀函数pi[0,0,1]然后遍历T当j1时T[1]b与P[1]b匹配成功当j2时T[2]a与P[2]a匹配成功j变成3说明匹配成功一次计数器加1j回退到pi[2-1]pi[1]0继续往后找。这里最关键的细节是匹配成功后 j 要回退否则会漏掉重叠匹配。把这套逻辑写成代码就是2.1节给过的模板。平时刷题时我建议把KMP、前缀函数、AC自动机这三个模板分别整理成函数考试时直接调用能省下大量调试时间。3.3 编程题2的完整实现TopK模拟题一个直播间有N条弹幕每条弹幕对应一个用户ID后台统计每个用户发送弹幕的数量输出发送量前K大的用户IDN最大为10^6K为100。这道题用到哈希表加小顶堆。先用哈希表统计每个用户发送弹幕数再维护一个大小为K的小顶堆当堆不满时直接入堆当新用户的弹幕数大于堆顶时替换堆顶并调整。import heapq from collections import Counter def top_k_user(msg_ids, k): counter Counter(msg_ids) heap [] for uid, cnt in counter.items(): if len(heap) k: heapq.heappush(heap, (cnt, uid)) elif cnt heap[0][0]: heapq.heapreplace(heap, (cnt, uid)) return [uid for _, uid in heap]这段代码有一个很值得注意的点堆里存的是(cnt, uid)元组比较的时候先比较cnt。如果两个用户发送弹幕数相同再比较用户ID大小。实际笔试里可能要求按发送量降序、ID升序输出你可以在最后对堆里的元素排序也可以把元组设计成(-cnt, uid)来改变排序方向。不要小看这个细节输出顺序错了会扣分甚至全错。3.4 压轴题的应对策略压轴题常见的是滑动窗口和单调栈。模拟题给定一个连续直播间观看记录数组arr长度为N求所有长度为K的连续子数组中的最大值输出这些最大值组成的数组。经典解法是单调递减双端队列保证队首始终是当前窗口最大值每次窗口右移时把队首所有“过期”的下标弹出去再把新元素入队前把所有比它小的元素从队尾弹出因为它们不可能再成为最大值。from collections import deque def max_sliding_window(nums, k): dq deque() res [] for i, v in enumerate(nums): while dq and nums[dq[-1]] v: dq.pop() dq.append(i) if dq[0] i - k: dq.popleft() if i k - 1: res.append(nums[dq[0]]) return res这道题最容易错的地方是“过期元素处理”的时机必须在入队新元素之后、收集答案之前把队首过期的下标弹出。我见过很多版本把popleft放在入队之前结果窗口还没滑到就已经把有效元素弹掉了。做题时先在纸上模拟一个长度为5的数组、窗口K3把每一步的队列内容写出来基本就不会错了。4. 实战中我踩过的坑从超时到边界4.1 时间复杂度估算失误第一次做这种直播类算法卷时我最常犯的错误就是时间复杂度估算失误。拿到题之后不先算数据规模直接上手写了一版O(n^2)的解法交上去才发现超时。我后来养成了一个习惯看到题先圈出数据范围然后在草稿纸上估算复杂度上限。按经验来说Python在1秒内大概能跑10^7次简单循环C大概能跑10^8到10^9次。如果数据规模是10^5O(n^2)就是10^10Python必超时C也很悬但O(n log n)是10^5乘以17Python完全能承受。数据规模O(n)O(n log n)O(n^2)10^3可行可行可行10^5可行可行基本不可行10^6可行可行完全不可行这套估算表我贴在办公桌上贴了很久。不是每个题都必须最优解但一定要在动手前知道自己写出来的复杂度会不会超时。如果你发现自己需要嵌套两层循环而n又大于10^4先停下来想想有没有堆、二分、前缀和、滑动窗口这类优化手段。4.2 边界条件汇总边界条件是笔试失分的重灾区而且特别可惜因为有些时候只是少写了一个if。我把高频边界条件整理成一张速查表每道题写完代码前对照一遍空输入字符串长度为0、数组为空、K0函数要能返回空结果而不是抛异常。单元素数组只有一个元素时二分、排序、DP都要能直接返回。全部相同数组元素全一样测试TopK、滑动窗口、去重逻辑是否正常。已有序输入已经升序或降序排序和二分不能出问题。最大最小值ID为0或很大、数量为0或1防止数值溢出。负数和浮点数如果题中没有明确说明输入非负要考虑负数情况。我每次写完代码都会用“空、单、全、极”这四个字提醒自己补测试用例。看似浪费时间实际上能帮你救回很多不该丢的分。4.3 题量节奏与策略笔试的节奏比想象中更难控制。我见过太多人选择题做了20分钟编程题只写了两题反过来也有编程题死磕压轴题结果前面的简单题没写。我常用的策略是“二八原则”用80%的时间拿到80%的分数剩下20%的时间去攻难题。具体来说先把所有能做对的题稳稳拿下选择题不确定的标记出来快速猜一个编程题每道至少写出暴力解即使不是最优也能拿到部分分数。很多公司的笔试OJ是分测试点给分的暴力解能过一部分数据点也比你交空代码强。关于代码风格笔试时整洁的代码也能帮你争取印象分。变量名不要用a、b、c至少用nums、target、cnt这种一眼能看懂的复杂逻辑要写注释哪怕是一行。如果你写的代码自己都看不懂考官也很难给你高分。4.4 后续备考建议如果你是冲着映客这类直播公司去的有一个方向千万别忽略字符串算法。KMP、字典树、AC自动机在弹幕风控、内容审核里用得非常多我在多家公司笔试里都碰到过类似的考点。其次是把LeetCode热门100题刷熟特别是数组、链表、二叉树、动态规划这四类。刷题的时候不要只刷一遍建议每隔几天重新做一遍错题把自己当时卡住的地方和正确的解法治愈思路写在旁边。还有一个很实操的建议考前模拟真实笔试环境。用牛客网的在线笔试系统做题因为公司笔试平台通常和牛客很接近代码提交方式和报错信息你需要提前熟悉。我见过一个同学平时在本地IDE写得很溜上了在线OJ因为不熟悉输入输出格式第一道题卡了20分钟整场心态崩了。别让这种低级问题影响你的发挥。我个人在复盘这套卷子时最大的体会是算法笔试考察的远不止算法本身还有你在压力下保持清晰思路的能力。那些复杂的边界条件和时间复杂度的纠结只要提前演练过上了考场就不会慌。你不需要每道题都完美但一定要把能拿的分稳稳拿住。