柠檬微趣 AI 开发实习笔试:四道 Medium 起步,ACM 模式先吃掉十几分钟
- 轮次
- 笔试
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 四道编程题,ACM 模式(自行读入、自行输出,不提供函数签名与测试用例)。
- 可参考的原题:LC 31 下一个排列(给定排列,原地改成字典序的下一个排列)。
- 可参考的原题:LC 148 排序链表(链表排序,要求 O(n log n) 时间)。
- 可参考的原题:LC 39 组合总和(候选数可重复选取,求和为 target 的所有组合)。
《参考解析》
ACM 模式与核心代码模式的差别才是这场笔试的第一道题:核心代码模式由平台准备好输入、只要求你填函数体,返回值由平台比对;ACM 模式要自己写 main,自己从标准输入解析数据,自己按题目要求格式打印结果。多组输入的题目通常要在 while 里读到 EOF,单组输入要先读 n 再读 n 个数;输出要求精确到空格、换行与大小写。帖主花了十几分钟在这上面,说明这不是知识问题而是熟练度问题——平时用核心代码模式刷题的人,第一次遇到 ACM 模式必然要现场摸索。准备方式很直接:按目标公司的笔试形式刷题,ACM 模式就固定用「读 n → 循环读入 → 求解 → 打印」的模板,把二维数组、字符串切分、多组数据这几种读法练到不用想。
LC 31 下一个排列:从右往左找第一个满足 a[i] < a[i+1] 的位置 i(此时 i 右侧是降序),再从右往左找第一个大于 a[i] 的 a[j],交换两者,然后把 i 之后的部分反转成升序。找不到 i 说明整个序列是降序,直接反转成最小的升序排列。关键点是「右侧是降序」这个不变量让第二步可以从右往左线性找,整体 O(n)、额外空间 O(1)。变体常见的问法是「下一个更大元素」「字典序第 k 个排列」,思路都是同一套。
LC 148 排序链表:面试里期望的是归并排序,因为链表不能随机访问,快排的划分代价高。自顶向下的写法用快慢指针找中点、递归排序两半再合并,空间 O(log n);自底向上的写法按步长 1、2、4、8 逐轮把相邻两段归并,空间 O(1),是这道题的最优解。实现时容易错的地方是链表断开的时机与哑节点的使用:找中点时让 slow 停在左半段的最后一个节点,再把它与右半段断开,否则递归不会终止。如果题目只要求「排序」而不限定空间,用自顶向下更快写对。
LC 39 组合总和:回溯。先对候选数组排序,递归时从当前位置 start 开始取,允许重复取当前元素,target 减到 0 时收集结果,减到小于 0 时剪枝返回。排序的作用是让「当前数已经大于剩余 target」时可以直接 break,因为后面的数更大。不许重复组合的关键是每次递归传入 i 而不是 0,这样同一层不会回头取更小的数。时间复杂度与结果数量相关,属于指数级,但剪枝后实际可接受。
超时通常出在这几处:递归没有剪枝导致搜索空间爆炸;在循环里做字符串拼接而不是用数组收集;每层重复计算同一个子问题却没有记忆化;输入用逐字符读取而不是一次读入。帖主提到「一直运行超时没时间排查」,笔试里的处理顺序应该是先确认算法复杂度对不对,再确认有没有多余的重复计算,最后才怀疑常数——时间不够时优先保住已经写对的题,不要在一道上耗到交卷。
这场笔试给出的准备清单:把 ACM 模式的输入输出练成肌肉记忆;按 Medium 难度刷原题并重点练「原题变体」——改输入形式、加多组数据、换输出要求;链表与排列这两类题在笔试里出现频率高,模板要能默写;限时训练,四道题按 100 分钟分配,先扫一遍挑出最有把握的两道。