每年三四月份，大批同学开始投暑期实习简历，其中通信和终端行业头部厂商的机试环节，是很多计算机相关专业学生绕不开的一道坎。我当时参加的就是2021届的暑期实习机试，整体感受是：题量不大但时间紧，表面考算法，实际考的是你在有限时间内解决问题的能力。这篇文章把我当时踩过的坑、总结的套路和复盘思路完整写下来，给后面准备类似大厂机试的同学做个参考。

先说说这东西到底是什么。所谓机试，就是在限定时间内，通过在线评测系统完成若干道编程题。评测系统会给你输入样例，你提交代码后系统自动跑测试用例，对的题得分，错的题零分，部分通过也能拿部分分数。2021届那场机试给我的感觉是：题型偏算法和数据结构的经典应用，不考偏门知识，更看重你的代码熟练度和边界处理能力。CMS（代码提交系统）只反馈通过率，不告诉你挂了哪个用例，这其实很考验人。

这篇文章适合谁看呢？如果你正在准备大厂暑期实习或秋招提前批的在线笔试，尤其是算法基础一般、想短时间找回手感的人，这篇文章可以帮你省掉不少摸索时间。我尽量把选题思路、代码套路、现场心态都讲透，也加入一些当时我自己整理的练习方向。

1. 看懂这场机试：考的是什么，筛的是什么

很多人把机试理解成“刷题比赛”，这个理解不能说错，但容易跑偏。从2021届这批题目来看，出题方的目的更接近“用最低成本筛出能干活的人”，所以题目并不会刻意刁难你，反而很看重基本功和工程习惯。

1.1 题量与时长：不是题难，是时间紧

当时我做的是三道题，总时长好像120分钟，但不同批次可能有差异。常见分配是：第一题简单，大概二十分钟能写完；第二题中等，需要想清楚数据结构和边界；第三题偏难，可能涉及图论或者动态规划，很多人到了这里只剩半小时。我认识的一位同学就是第二题死磕太久，第三题只来得及写个暴力版本，最后总分被拉开。

这里给个关键建议：机试不是每道题都要求满分。如果你的目标是过筛，而不是跟人拼排行榜，那就先把能拿的分全拿到。第一题求稳，第二题尽力，第三题哪怕只能暴力过部分样例，也比交白卷强。

1.2 题型分布：高频考点其实很集中

我复盘了一下自己和身边同学的题单，发现2021届实习机试的高频题型大致有以下几类：

这类题目基本不会超出大二大三《数据结构》和《算法设计与分析》课程范围，所以哪怕你平时没专门刷过题，把基础算法补上，也是有希望的。

1.3 判分规则：部分通过也是分

很多在线测评系统不是只有0和100，而是按测试用例给分。我当时提交的第三题，暴力解法大概只能过30%的用例，但就是这30%帮我拉高了总分。所以不要因为发现“最优解”难写就放弃，可以先提交一版能跑出结果的代码，再回头优化。

提示：机试开始后先看全部三道题的题面，花三分钟判断难度，然后按“易→中→难”的顺序做题。顺序选错是最大的隐形失分点。

2. 高频算法拆解：拿到题先想哪几板斧

这一节我从“拿到题目之后怎么想”的角度，讲几个我自己总结的思维模板。不是完整的算法课，而是帮你在机试那种紧张状态下快速找到切入点。

2.1 字符串题：先想正则，再想状态机

字符串题看着简单，其实最容易在细节上翻车。比如日志解析类题目，经常出现“格式不统一”“大小写混用”“空字段”这种魔鬼细节。我的套路是先看能不能用正则或者字符串切分解决，如果不能，再考虑手写状态机。特别提醒，很多机试用的是老版本编程环境，不一定支持较新的正则语法，所以不要把宝全押在正则上。

状态机思路其实不难理解：把字符串当成一个字符流，每个字符触发状态转移。比如判断一个字符串是否是合法IP地址，就可以拆成“数字开始→数字中间→遇到点→新数字开始”几个状态。把状态图画清楚，代码就很好写了。

2.2 图论题：先建图，再套模板

图论的坑在于建图本身。举个例子，如果题目说“输入n个节点和m条边”，很多人以为邻接矩阵就行，但如果n上万，邻接矩阵就直接爆内存了。你需要在读题阶段就判断该用邻接表还是邻接矩阵，以及是否需要考虑重边和自环。

模板方面，最短路径直接套Dijkstra（无权图可以用BFS），拓扑排序入度为0的点进队列，连通分量用并查集或者DFS染色。这里有个小技巧：只要题目出现了“依赖关系”“先后顺序”“环检测”这些字眼，优先往拓扑排序上想。

2.3 动态规划：定义好状态，就赢了一半

DP题最怕的不是转移方程写不出来，而是状态定义一开始就错了。比如最长公共子序列，状态定义为dp[i][j]表示“前i个字符和前j个字符的最长公共子序列长度”，转移就非常清晰。一旦你把它定义成“以第i个字符结尾的最长公共子序列”，就会绕进死胡同。

机试的DP题大多不会超过二维状态，所以先把二维DP练熟。特别关注经典的背包问题、最长上升子序列和编辑距离这三类，它们出现的频率真的很高。

2.4 区间与排序：二分、区间合并、前缀和

区间类题目在笔试中也经常出现，比如合并区间、求重叠区间长度、区间和等。合并区间有个特别简单的套路：先把所有区间按左端点排序，然后遍历，如果当前区间和上一个重叠就合并，否则开新区间。这个套路只需要十几行代码，却能在很多题目里当子函数用。

前缀和是另一种百试不爽的技巧。它把“求区间和”的复杂度从O(n)降到O(1)，代价只是预处理一遍。我遇到跟数组和子数组相关的题目时，都会先问自己一句：这题能不能用前缀和？

3. 三道典型真题复盘：从读题到AC的完整思路

这一节我选了三道比较有代表性的模拟题，还原我当时的思考和踩坑过程。需要说明的是，题目是我按2021届风格自己整理的同类型题，不是原题，思路和写法可以直接参考。

3.1 真题复盘一：内容平台的敏感词过滤

题面大意：给定一个词库（若干敏感词）和一篇文章，需要把文章中出现词库里的词替换为对应长度的星号，输出过滤后的文章。词库大小不超过1000，文章长度不超过100万字。

看到“敏感词”三个字，我的第一反应是字典树（Trie）。用词库建一棵字典树，然后对文章做扫描，每个位置尝试匹配。匹配成功就标记一段替换区间，最后统一生成输出。这个方案的理论复杂度是O(文章长度 × 最长词长度)，但实际因为有字典树剪枝，跑得很快。

这里有个坑：如果只按“找到就替换”的逻辑处理，多个敏感词重叠时可能会出错。比如词库里有“AB”和“BC”，文章是“ABC”，如果先替换“AB”，剩余的“C”就不再有“BC”；如果先匹配“BC”，“AB”也少了前缀。更稳妥的方案是：先扫描出所有命中的区间，再对区间做合并或按起始位置排序，最后统一替换。这样就不会互相干扰。

class TrieNode: def __init__(self): self.children = {} self.is_end = False def filter_words(word_list, text): root = TrieNode() for w in word_list: cur = root for ch in w: if ch not in cur.children: cur.children[ch] = TrieNode() cur = cur.children[ch] cur.is_end = True n = len(text) replace = [False] * n for i in range(n): cur = root j = i while j < n and text[j] in cur.children: cur = cur.children[text[j]] j += 1 if cur.is_end: for k in range(i, j): replace[k] = True res = [] for i, ch in enumerate(text): if replace[i]: res.append('*') else: res.append(ch) return ''.join(res)

这段代码的时间复杂度是O(文章长度 × 平均匹配深度)，空间复杂度O(词库总字符数)。如果面试官让你进一步优化，可以考虑用AC自动机，把扫描复杂度压到O(n)。不过机试阶段，字典树已经足够拿分。

3.2 真题复盘二：社交平台的好友推荐

题面大意：一个社交网络，用户之间有关注关系（有向图）。给定一个用户A，系统需要推荐“A关注的人也在关注的人”，且不能是A已经关注的人。推荐结果按共同关注人数降序排序，人数相同时按用户ID升序。

这题是典型的“BFS + 聚合计数”组合。A的一跳关注集合记为followed，对followed里每个人，再遍历他们关注的人（二跳候选），用哈希表统计每个二跳用户的被关注次数。这里有个容易忽略的点：统计过程中必须把A自己排除，把已经在followed里的也排除，否则推荐结果会出现“自己”或“已关注的人”。

实现层面，图的存储我用邻接表。因为输入规模可能到几十万节点，邻接矩阵一定不行。计数结束后，对(count, user_id)做排序，Python里可以直接用sorted(candidates.items(), key=lambda x: (-x[1], x[0]))，一步到位。这种“负号取反”的方式在刷题里很实用，能少写一个cmp函数。

注意：做图论题时，第一时间确认节点编号范围是0到n-1还是1到n。这个细节看着小，但数组越界或者漏掉一个节点是机试里下场最惨的错误之一。

3.3 真题复盘三：任务调度系统

题面大意：有n个任务，每个任务有编号、执行时间和依赖列表（必须先完成的其它任务）。你需要输出一个合法的任务执行顺序，并且在满足依赖的前提下，让最先执行的任务编号尽可能小，其次第二个尽可能小，以此类推。换句话说，在拓扑排序的基础上加一个“字典序最小”的约束。

拓扑排序本身不复杂，关键是“字典序最小”。如果直接用普通队列，入度为0的任务是按自然顺序进去的，你无法控制输出的最小字典序。正确做法是把“队列”换成“最小堆”或优先队列。每次从堆顶取出当前编号最小的可执行任务，执行完释放它的后继依赖，再把新的入度为0的任务压进去。这样迭代得到的拓扑序就是最小字典序。

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<vector<int>> g(n); vector<int> indeg(n, 0); for (int i = 0; i < n; i++) { int id, time, dep, pre; cin >> id >> time >> dep; for (int j = 0; j < dep; j++) { cin >> pre; g[pre].push_back(id); indeg[id]++; } } priority_queue<int, vector<int>, greater<int>> pq; for (int i = 0; i < n; i++) if (indeg[i] == 0) pq.push(i); vector<int> order; while (!pq.empty()) { int cur = pq.top(); pq.pop(); order.push_back(cur); for (int nxt : g[cur]) { if (--indeg[nxt] == 0) pq.push(nxt); } } if (order.size() < n) { cout << "cycle" << endl; } else { for (int x : order) cout << x << " "; } return 0; }

这个模板在“有依赖的调度”“课程表”等题目里可以直接复用。另外提醒一下：order.size() < n说明图里有环，也就是存在循环依赖，此时不可能有合法顺序。这个判断一定要写，因为评测数据里大概率会有这种边界用例。

4. 机试现场的坑与排查手册

比起算法本身，真正能让很多人当场翻车的其实是那些平时不太在意的细节。这一节我把常见的问题整理成一份“速查手册”，就算你只记住这一节，也能少踩很多坑。

4.1 输入输出：被忽略的隐形杀手

大厂在线笔试的输入格式千奇百怪，最典型的有：“多组数据，以EOF结束”“每组数据第一行是T”“用逗号分隔”“可能带空格的一整行”。这些格式问题一旦没处理好，就是一连串测试用例全错。

我的习惯是先把输入样例手动模拟一遍，再决定用cin、getline还是readline。如果一个字符串里可能带空格，就不要用cin >> s这种按空白切分的方式，应该用getline(cin, s)。如果你在调试时发现“明明逻辑对，但第一个用例都过不了”，八成就是输入解析出了问题。

4.2 边界和溢出：最常见的隐性扣分点

写完代码之后，给自己三秒钟想几个边界：n=0、n=1、全是相同元素、最大值等于INT_MAX。很多题不是复杂算法，反而是在边界上挂了一大半测试点。我记得有个朋友在最大子序和的题里，用int存前缀和，结果数据一大直接溢出，白白丢分。

如果题目数值范围没有明确说明，宁可使用long long也不要省这点空间。数组访问同理，很多图论题节点编号从1开始，而数组长度只开到n，少了1个位置，运行时就可能数组越界。

4.3 超时与复杂度：不是AC就完事，得看时限

评测系统通常会限制单题运行时间，常见的是1秒到2秒。如果你的方案是O(n^2)，而n已经到10万，基本必超时。在机试里，能优化到O(n log n)就尽量优化，排序和二分是好帮手。

遇到复杂题，先写暴力拿部分分，再逐步优化。就算最后没有完全AC，靠部分通过也能保住下限。对很多人来说，一场机试的目标不是三题全A，而是总分过线。

4.4 快速自查清单

这个表格存下来，每次提交前对着过一遍，至少能救回10%的分数。

5. 备考时间线：从零开始怎么安排

最后聊聊大家最关心的备考节奏。如果你还有两三周就要机试，可以参考我当时的时间安排。坦白说，我不属于竞赛选手，只是把时间花在了刀刃上。

5.1 第一周：把基础数据结构过一遍

这周的优先级是：数组、链表、栈、队列、哈希表、二叉树、堆。不需要背定义，而是要把每种数据结构的常见操作写到“闭眼能出”的程度。比如链表的反转、二叉树的三种遍历、堆的上滤下滤，这些代码没有思考时间，必须肌肉记忆。

我当时的方法很简单：把每种结构做成一个模板笔记，每个模板配两三道基础题，把代码反复敲到不看笔记能写出来为止。这个过程很枯燥，但到机试时会非常受益。

5.2 第二周：按题型专项训练

第二周开始集中刷题，按“字符串模拟→排序贪心→图论→动态规划”的顺序推进。每天大概三到四道题，每道题不光要AC，还要看官方题解或者讨论区里的高赞做法。我自己的经验是：一道题做三遍，比自己闷头刷十道新题更有用。

专项训练时一定要计时。每道题给自己45分钟，到点没思路就看题解，搞懂思路后隔天再独立写一遍。这样做能逼你在压力下思考，模拟真实机试的节奏。

5.3 最后三天：全真模拟与坏境适应

考前最后三天不要再学新知识了。找一套往年的机试样题，按真实时长完整走一遍流程。重点不在分数，而在于确认三件事：环境能编译通过、输入输出没问题、时间分配别崩。

还有一个很容易被忽略的点：提前确认你的IDE和快捷键。有些人习惯本地调试完再粘代码，那就提前把本地环境和在线平台的一致性测一遍。有些人习惯直接在网页上写，那就提前适应一下没有自动补全的体验。

机试拼到最后一刻，拼的反而是这些看起来很笨的准备工作。你多花半小时熟悉系统和格式，现场就少浪费半小时在无关紧要的事情上。

如果让我说一句掏心窝的话：大厂实习机试真的不是竞赛，它考的是“你能否在一个下午的时间里，像个成熟工程师一样解决问题”。算法熟练度当然重要，但更重要的是一套稳定的思考顺序——先看数据范围，再想数据结构，然后定算法，最后查边界。

我今天讲的这些套路，都是我从一次次超时、一次次数组越界、一次次读不懂输入格式的教训里总结出来的。你在准备时不需要什么都知道，只要把最常考的那几个板斧练到极致，就已经赢过很多人了。最后一个小建议：平时写题时养成写注释的习惯，哪怕只有一行“这里是判断环的”，机试现场你也会更清楚自己的代码逻辑。祝大家顺利通过。