每年三四月份大批同学开始投暑期实习简历其中通信和终端行业头部厂商的机试环节是很多计算机相关专业学生绕不开的一道坎。我当时参加的就是2021届的暑期实习机试整体感受是题量不大但时间紧表面考算法实际考的是你在有限时间内解决问题的能力。这篇文章把我当时踩过的坑、总结的套路和复盘思路完整写下来给后面准备类似大厂机试的同学做个参考。先说说这东西到底是什么。所谓机试就是在限定时间内通过在线评测系统完成若干道编程题。评测系统会给你输入样例你提交代码后系统自动跑测试用例对的题得分错的题零分部分通过也能拿部分分数。2021届那场机试给我的感觉是题型偏算法和数据结构的经典应用不考偏门知识更看重你的代码熟练度和边界处理能力。CMS代码提交系统只反馈通过率不告诉你挂了哪个用例这其实很考验人。这篇文章适合谁看呢如果你正在准备大厂暑期实习或秋招提前批的在线笔试尤其是算法基础一般、想短时间找回手感的人这篇文章可以帮你省掉不少摸索时间。我尽量把选题思路、代码套路、现场心态都讲透也加入一些当时我自己整理的练习方向。1. 看懂这场机试考的是什么筛的是什么很多人把机试理解成“刷题比赛”这个理解不能说错但容易跑偏。从2021届这批题目来看出题方的目的更接近“用最低成本筛出能干活的人”所以题目并不会刻意刁难你反而很看重基本功和工程习惯。1.1 题量与时长不是题难是时间紧当时我做的是三道题总时长好像120分钟但不同批次可能有差异。常见分配是第一题简单大概二十分钟能写完第二题中等需要想清楚数据结构和边界第三题偏难可能涉及图论或者动态规划很多人到了这里只剩半小时。我认识的一位同学就是第二题死磕太久第三题只来得及写个暴力版本最后总分被拉开。这里给个关键建议机试不是每道题都要求满分。如果你的目标是过筛而不是跟人拼排行榜那就先把能拿的分全拿到。第一题求稳第二题尽力第三题哪怕只能暴力过部分样例也比交白卷强。1.2 题型分布高频考点其实很集中我复盘了一下自己和身边同学的题单发现2021届实习机试的高频题型大致有以下几类类别典型题目核心数据结构出题频率字符串处理解析日志、敏感词过滤、格式转换字符串、哈希表高模拟题数组变换、矩阵旋转、匹配规则数组、模拟高图论最短路径、拓扑排序、连通分量邻接表、优先队列中动态规划背包、子序列、路径计数DP数组中贪心与二分区间调度、资源分配排序、二分查找中这类题目基本不会超出大二大三《数据结构》和《算法设计与分析》课程范围所以哪怕你平时没专门刷过题把基础算法补上也是有希望的。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(), keylambda 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; vectorvectorint g(n); vectorint 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_queueint, vectorint, greaterint pq; for (int i 0; i n; i) if (indeg[i] 0) pq.push(i); vectorint 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 边界和溢出最常见的隐性扣分点写完代码之后给自己三秒钟想几个边界n0、n1、全是相同元素、最大值等于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 快速自查清单检查项说明数据范围用int还是long long数组长度够吗编号起点节点从0还是1开始不要想当然空集合空数组、空字符串、n0有没有输出重复元素排序和去重是否考虑到了循环依赖拓扑排序是否有环输入格式有没有空格、逗号、EOF字典序题目要求的具体排序规则是什么这个表格存下来每次提交前对着过一遍至少能救回10%的分数。5. 备考时间线从零开始怎么安排最后聊聊大家最关心的备考节奏。如果你还有两三周就要机试可以参考我当时的时间安排。坦白说我不属于竞赛选手只是把时间花在了刀刃上。5.1 第一周把基础数据结构过一遍这周的优先级是数组、链表、栈、队列、哈希表、二叉树、堆。不需要背定义而是要把每种数据结构的常见操作写到“闭眼能出”的程度。比如链表的反转、二叉树的三种遍历、堆的上滤下滤这些代码没有思考时间必须肌肉记忆。我当时的方法很简单把每种结构做成一个模板笔记每个模板配两三道基础题把代码反复敲到不看笔记能写出来为止。这个过程很枯燥但到机试时会非常受益。5.2 第二周按题型专项训练第二周开始集中刷题按“字符串模拟→排序贪心→图论→动态规划”的顺序推进。每天大概三到四道题每道题不光要AC还要看官方题解或者讨论区里的高赞做法。我自己的经验是一道题做三遍比自己闷头刷十道新题更有用。专项训练时一定要计时。每道题给自己45分钟到点没思路就看题解搞懂思路后隔天再独立写一遍。这样做能逼你在压力下思考模拟真实机试的节奏。5.3 最后三天全真模拟与坏境适应考前最后三天不要再学新知识了。找一套往年的机试样题按真实时长完整走一遍流程。重点不在分数而在于确认三件事环境能编译通过、输入输出没问题、时间分配别崩。还有一个很容易被忽略的点提前确认你的IDE和快捷键。有些人习惯本地调试完再粘代码那就提前把本地环境和在线平台的一致性测一遍。有些人习惯直接在网页上写那就提前适应一下没有自动补全的体验。机试拼到最后一刻拼的反而是这些看起来很笨的准备工作。你多花半小时熟悉系统和格式现场就少浪费半小时在无关紧要的事情上。如果让我说一句掏心窝的话大厂实习机试真的不是竞赛它考的是“你能否在一个下午的时间里像个成熟工程师一样解决问题”。算法熟练度当然重要但更重要的是一套稳定的思考顺序——先看数据范围再想数据结构然后定算法最后查边界。我今天讲的这些套路都是我从一次次超时、一次次数组越界、一次次读不懂输入格式的教训里总结出来的。你在准备时不需要什么都知道只要把最常考的那几个板斧练到极致就已经赢过很多人了。最后一个小建议平时写题时养成写注释的习惯哪怕只有一行“这里是判断环的”机试现场你也会更清楚自己的代码逻辑。祝大家顺利通过。