企业官网建设流程全解析

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数组。热词里提到的那个例子非常典型：“模式串 p='abacaba'，求其next数组”。这道题看起来简单，但每年都有大量同学栽在next数组的定义和边界处理上。

先统一口径。KMP里的next数组，按主流教材有两种定义方式。第一种是前缀函数写法：next[i]表示“模式串前i+1个字符组成的子串中，最长的相等真前后缀的长度”。第二种是失配跳转表写法：next[i]表示“当第i位字符失配时，模式串指针应该跳转到的位置”，这种写法通常会把前缀函数整体右移一位，并在开头补-1。

以p="abacaba"为例，我按前缀函数定义手算一遍，这个表你可以直接当模板记：

所以 p="abacaba" 的前缀函数数组是 [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 cnt

2.2 排序与TopK：排行榜场景的取舍

排行榜在直播平台里太常见了，热门礼物榜、粉丝团榜、观看时长榜，本质都是从一个很大的集合里取前K个。笔试里如果考排序，很少直接让你写一个完整的快排，而是会把问题包装成“给10万个主播ID，按礼物数排序后输出前100名”这种业务题。这种题考察的核心是：你知不知道排序算法之间的复杂度差异，以及TopK为什么要用堆而不是全量排序。

先看一张对照表，笔试选择题经常考：

如果你要全量排序，通常选快排，因为平均常数小；如果对稳定性有要求，选归并；如果只是找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和一个模式串P，P的长度不超过10^5，统计P在T中出现的次数，要求O(n)复杂度。这个问题直接用2.1节的KMP模板就能解决。我先用草稿纸推演一下，比如 T="abababa", P="aba"，肉眼可以看到P出现了3次，重叠部分也算，分别是下标0、2、4。用KMP跑一遍：先计算P的前缀函数pi=[0,0,1]，然后遍历T，当j=1时，T[1]='b'与P[1]='b'匹配成功；当j=2时，T[2]='a'与P[2]='a'匹配成功，j变成3，说明匹配成功一次，计数器加1，j回退到pi[2-1]=pi[1]=0，继续往后找。这里最关键的细节是：匹配成功后 j 要回退，否则会漏掉重叠匹配。

把这套逻辑写成代码，就是2.1节给过的模板。平时刷题时我建议把KMP、前缀函数、AC自动机这三个模板分别整理成函数，考试时直接调用，能省下大量调试时间。

3.3 编程题2的完整实现：TopK

模拟题：一个直播间有N条弹幕，每条弹幕对应一个用户ID，后台统计每个用户发送弹幕的数量，输出发送量前K大的用户ID，N最大为10^6，K为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的数组、窗口K=3，把每一步的队列内容写出来，基本就不会错了。

4. 实战中我踩过的坑：从超时到边界

4.1 时间复杂度估算失误

第一次做这种直播类算法卷时，我最常犯的错误就是时间复杂度估算失误。拿到题之后不先算数据规模，直接上手写了一版O(n^2)的解法，交上去才发现超时。我后来养成了一个习惯：看到题先圈出数据范围，然后在草稿纸上估算复杂度上限。按经验来说，Python在1秒内大概能跑10^7次简单循环，C++大概能跑10^8到10^9次。如果数据规模是10^5，O(n^2)就是10^10，Python必超时，C++也很悬；但O(n log n)是10^5乘以17，Python完全能承受。

这套估算表我贴在办公桌上贴了很久。不是每个题都必须最优解，但一定要在动手前知道自己写出来的复杂度会不会超时。如果你发现自己需要嵌套两层循环，而n又大于10^4，先停下来想想有没有堆、二分、前缀和、滑动窗口这类优化手段。

4.2 边界条件汇总

边界条件是笔试失分的重灾区，而且特别可惜，因为有些时候只是少写了一个if。我把高频边界条件整理成一张速查表，每道题写完代码前对照一遍：

• 空输入：字符串长度为0、数组为空、K=0，函数要能返回空结果而不是抛异常。
• 单元素：数组只有一个元素时，二分、排序、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分钟，整场心态崩了。别让这种低级问题影响你的发挥。

我个人在复盘这套卷子时最大的体会是：算法笔试考察的远不止算法本身，还有你在压力下保持清晰思路的能力。那些复杂的边界条件和时间复杂度的纠结，只要提前演练过，上了考场就不会慌。你不需要每道题都完美，但一定要把能拿的分稳稳拿住。