2016年秋天我在学校机房点开美丽联合的在线笔试链接。那年头“在线编程题”在校招里已经很常见但真正坐到屏幕前面对倒计时还是会紧张。美丽联合当时刚完成美丽说和蘑菇街的合并电商业务势头正猛技术团队在杭州互联网圈子里口碑不差。笔试分成选择和编程题两块编程题给了两个半小时。我记得自己花了四十分钟做选择然后按顺序处理三道编程题最后一道链表题差点没写完。当年那套题给我的整体感受是不偏不怪但细节极多。三道编程题分别考察了动态规划、哈希表加排序、单链表反转全是基础算法但恰恰是基础题最考验功底。这篇文章把当时的题目回顾、解题过程和踩坑点完整记录下来给准备校招的应届生以及想系统补算法基础的开发者做参考。我会把被判题系统扣分的点也写进去这些细节往往比“正确解法”本身更有参考价值。1. 2016年那场笔试的题目轮廓难度、风格与考场节奏1.1 那个年代在线编程题到底考什么2016年的校招笔试有一个鲜明的时代特征大多数公司都已经从纸质简历加现场手写代码过渡到在线笔试平台。牛客网、赛码网是主流美丽联合用的也是牛客网。那时候的题型一般是“选择题加编程题”的组合选择题覆盖计算机网络、操作系统、数据库、数据结构这些基础课编程题则是3到5道不等由判题系统自动运行并给出通过率。美丽联合这套题稳得有点出人意料。没有脑筋急转弯没有冷门算法三道编程题全部集中在基础数据结构和算法。第一道是动态规划经典题要求找最大连续子段和第二道是字符串处理要求按字符出现频率排序第三道是单链表反转。懂行的人一眼就能看出来这不是在考“你会不会奇技淫巧”而是在考“你有没有把基本功练扎实”。放在今天的校招里这个出题思路依然非常主流。对准备笔试的人来说这里有一个很核心的认知在线编程题不是作文题判题系统只看程序在给定输入下能否产出正确输出。代码风格、注释、设计模式这些考官基本看不到但边界条件、复杂度、内存占用会直接决定你的分数。想拿满分必须在这些地方较真。1.2 拿到试卷后我先干了什么我的习惯是先花五分钟把三题全部读一遍再决定做题顺序。当时我把题目在脑子里过了一遍判断是第一题动态规划思路明确但要注意全负数的边界第二题字符串解法清晰重点是比较器第三题链表反转迭代和递归都能做但需要画图理清指针关系。我的做题顺序是第二题、第一题、第三题。为什么这么排因为第二题的解题路径最短先拿下一题心态不慌第一题虽然动规不算难但边界处理需要仔细第三题链表反转工作量大放在最后也来得及。后来回想这个策略救了我一命——第三题因为递归写法绕来绕去最后转用迭代法写完时间刚刚够。屏幕前的读者可以记住这条经验在线编程题的时间分配不要按照题目顺序死磕而应该按你的把握程度排优先级。先把有把握的题拿满再回头攻难题这是经过实战验证的策略。2. 第一道题最大连续子段和一个初始化变量差点断送offer2.1 题目描述与第一版暴力解题目大概是这样的给定一个整数数组元素可能是负数要求找出数组中某个连续子数组的最大和输出这个最大值。输入格式是第一行一个整数n代表数组长度第二行是n个整数。输出一个整数就是最大连续子段和。我敢说所有刷过算法题的人对这道题都不陌生它通常作为动态规划的第一课出现。但请注意这道题看似简单失分率却一直很高原因就藏在边界条件里如果数组里所有数都是负数最大连续子段和应该是最大的那个负数而不是0。很多人在看到这道题的瞬间会写出双重循环枚举子数组的暴力解法外层枚举起点内层枚举终点不断累加并记录最大值。暴力解的时间复杂度是O(n^2)当n只有100左右的时候完全没问题但校招题的数据范围通常会给到10^5O(n^2)会直接超时。所以我在现场没有采用这个方案直接上了动态规划但动态规划也埋了一个雷后面细说。2.2 动态规划的推导过程最大连续子段和的标准解法是动态规划状态的定义是dp[i]表示以第i个元素结尾的连续子数组的最大和。注意这里强调的是“以第i个元素结尾”而不是“前i个元素中的最大和”这个区分是初学者最容易混淆的地方。转移方程很简单dp[i] max(dp[i-1] a[i], a[i])然后最终的答案是所有dp[i]中的最大值。为什么这个方程成立我习惯用打牌来类比假设你手头已经攥着一手牌牌面总和是dp[i-1]现在新来一张牌a[i]你只有两个选择——把新牌加进手里的牌继续攥着或者觉得手里的牌太差干脆丢掉从a[i]这张牌重新开始。不管怎么选你都要保证手心上的数字尽量大。“从a[i]重新开始”这个动作就是方程里的max在起作用。用题目给到的一个经典例子验证数组[-2,1,-3,4,-1,2,1,-5,4]人肉推导一遍dp[0] -2maxSoFar -2dp[1] max(-21, 1) 1maxSoFar 1dp[2] max(1-3, -3) -2maxSoFar 1dp[3] max(-24, 4) 4maxSoFar 4dp[4] max(4-1, -1) 3maxSoFar 4dp[5] max(32, 2) 5maxSoFar 5dp[6] max(51, 1) 6maxSoFar 6dp[7] max(6-5, -5) 1maxSoFar 6dp[8] max(14, 4) 5maxSoFar 6最终答案是6。这个例子跑完方程的正确性基本就能说服自己了。2.3 现场写的代码与一个隐蔽的边界bug我的现场代码是下面这个版本用C写的#include cstdio #include algorithm using namespace std; int main() { int n; while (scanf(%d, n) ! EOF) { if (n 0) { printf(0\n); continue; } int x, cur, ans; for (int i 0; i n; i) { scanf(%d, x); if (i 0) { cur x; ans x; } else { cur max(cur x, x); ans max(ans, cur); } } printf(%d\n, ans); } return 0; }这段代码的关键点在于ans的初始值。我当年的低级错误是习惯性地把ans初始化为0然后遇到全负数测试用例直接全错。我具体是怎么发现自己错的呢当时的OJ平台会列出测试点通过情况我看到那题的通过率不是100%有一两个case显示wrong answer。我先想到是不是动态规划写错了后来在本地把数组改成全负数跑了一遍才发现输出永远是0而不是数组中最大的负数。当时心里一凉但时间已经不够再改。这个错误放在业务代码里不算致命放在在线编程题里就是硬伤。这个坑值得单独强调凡是求最大值的题目初始值要么用第一个元素要么用int类型的极小值INT_MIN不要想当然用0。同样求最小值的时候不要初始化为0而应该用第一个元素或INT_MAX。3. 第二道题字符串按出现频次重排比较器写错不如不写3.1 题目描述与审题陷阱第二道题大概是输入一个只包含小写字母的字符串长度不超过100000要求按字符出现次数从高到低输出所有字符如果出现次数相同则按ASCII码升序排列。举个具体例子输入字符串abacca出现2次c出现2次b出现1次输出应该是aaccb。这个题有非常明显的审题陷阱第一是输出的是原字符串的全部字符而不是字符统计表第二是排序有两个维度先比频次频次相同再比ASCII码。很多人在第一眼看到“按出现次数从高到低”之后就只盯着频次把字典序这个次条件漏了结果全错。另外一个容易忽略的点是字符串长度可以达到100000所以你的解法至少得是O(n log n)级别O(n^2)级别的双层循环在数据量大时一定会超时。这题的考点可以拆成两块一是能不能想到用哈希表或数组统计频次二是能不能写出正确的自定义排序规则。3.2 哈希表加排序的两种实现先说统计频次。因为字符串只有小写字母最多26种字符最简单的做法是用一个长度为26的int数组做计数下标0到25分别对应a到z。这一步是O(n)在线性时间内完成。如果字符串包含更多种类的字符才需要换成unordered_map。统计完成后需要排序。我的第一版代码是这样#include cstdio #include cstring #include algorithm using namespace std; struct Node { char c; int cnt; }; bool cmp(const Node a, const Node b) { if (a.cnt ! b.cnt) return a.cnt b.cnt; return a.c b.c; } int main() { char s[100001]; while (scanf(%s, s) ! EOF) { int count[26] {0}; int len strlen(s); for (int i 0; i len; i) { count[s[i] - a]; } Node nodes[26]; int m 0; for (int i 0; i 26; i) { if (count[i] 0) { nodes[m].c a i; nodes[m].cnt count[i]; m; } } sort(nodes, nodes m, cmp); for (int i 0; i m; i) { for (int j 0; j nodes[i].cnt; j) { printf(%c, nodes[i].c); } } printf(\n); } return 0; }这套方案统计频次是O(n)排序的节点数最多26个排序时间复杂度几乎可以忽略整体是O(n)。后面输出的时候用两层循环把频次展开成字符输出总量正好是n也不会超时。其实还有一个更取巧的做法因为总共只有26个字母完全不需要sort函数直接从a到z遍历把频次不为0的字符收集到一个数组里再按频次手动排序。不过直接用sort加自定义比较器是最直观、最不容易写错的方法我在现场用的就是这个。核心考点在比较器上把它写对这道题基本就过了。3.3 关于Comparator的坑和性能自定义比较器是排序题里最容易翻车的地方。C的sort要求比较器必须满足严格弱序也就是说如果cmp(a, b)返回true那么cmp(b, a)必须返回falsea和a自己比较必须返回false。如果你在比较器里只写了按频次降序忘记处理频次相同时按ASCII升序那输出结果就完全不符合题意。如果你用Java写这道题还有另一个经典坑compareTo和compare的返回值和你的直觉相反。Java里Collections.sort默认升序如果想让某个字段降序可以在compare里返回o2.val - o1.val但这样写容易因为整数溢出出bug。更稳妥的做法是使用Integer.compare这类方法明确写出比较逻辑。性能方面要注意的是如果数据量很大一定要避免在Comparator里做重复计算。比如不要在比较时再去查表统计频次应该提前把每个字符及其频次存到node对象里比较时直接取字段。还有一点字符串的输入输出在数据量大时也值得注意C里用cin/cout在部分OJ上可能因为同步问题变慢。我当时习惯在代码开头加ios::sync_with_stdio(false)来关闭C和C输入输出流的同步或者直接用scanf和printf这个习惯在笔试中能省下不少时间。3.4 多组测试数据的输入输出处理这道题还藏着输入输出的坑OJ的测试数据经常是多组的你不知道有多少组所以要写到while (scanf(%s, s) ! EOF)这个级别程序直到文件结尾才停止读取。如果只读一组就return了后面的测试点全部拿不到分。类似地printf的输出要注意换行。在线编程题对空白字符的容忍度有差异——大多数OJ忽略行末空格但一定要求每个输出后有换行。不要为了“看起来整齐”在行末额外加空格那反而可能被判为格式错误。多组数据的另一个坑是变量初始化。有些同学会在循环外面定义数组然后每轮循环不重置count数组导致样例输出和预期不符。我的习惯是每个测试点需要用的统计数组在循环内部定义或者手动memset避免上一次计算结果残留。4. 第三道题单链表反转递归和迭代到底怎么选4.1 题目描述与迭代法三指针第三道题是单链表反转。题目大概是输入一个单链表的头节点要求输出反转后链表的头节点。节点定义类似下面这样struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} };链表反转是数据结构课上必讲的题目但也是面试和笔试中的常青树因为它在指针操作上足够考验人。写错的人通常不是不知道思路而是不知道在改变指向之前先保存下一个节点的指针。迭代法的标准写法是三指针ListNode* reverseList(ListNode* head) { ListNode* prev NULL; ListNode* cur head; while (cur ! NULL) { ListNode* next cur-next; cur-next prev; prev cur; cur next; } return prev; }我把这个过程的记忆方式拆给你看一开始prev是空cur指向head每轮循环先记录cur的下一个节点为next然后让cur掉头指向prev再各自向后挪一格。循环结束的条件是cur变成NULL此时prev恰好停在原链表的尾节点也就是新链表的头节点。关键动作是什么是在cur-next prev这行执行之前先把cur-next原来的值存到next变量里。这个顺序一旦反过来链表就从中间断裂后面所有节点都找不到了。很多初学者的错误就出在这一行。4.2 递归法为什么容易混递归写法也很经典代码如下ListNode* reverseList(ListNode* head) { if (head NULL || head-next NULL) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next NULL; return newHead; }递归的思考方式跟迭代完全不同。迭代是从前往后改指针递归是从后往前处理。想象你已经把head-next开始的子链表反转好了得到了这个子链表的新头newHead那么原来head-next这个节点现在变成了子链表的尾节点只需要把它指向head再让head指向空整个链表就反转完成。我当时在考场上一度绕进递归出不来原因是我试图在大脑里模拟每一层递归的调用栈只要链表一长栈帧一多人脑很快就乱。后来我总结出一个经验写递归只需要信任两层关系——递归函数做的事情是什么、当前这一层要做什么不用把后面每一层都模拟一遍。用反向思考子链表已经反转完毕这层只是把当前节点接到尾部而已。但如果你在考场上时间紧张、心态不稳我建议直接用迭代法。迭代的三指针循环逻辑直观不容易写错。递归虽然代码短但对递归的理解要求更高写错了调试也更费时间。4.3 边界条件与断链链表题最考验的就是对边界条件的敏感度。空链表、只有一个节点的链表、只有两个节点的链表都必须能正确处理。对于迭代法空链表和单节点的情况天然能被循环处理head为NULL时while循环根本不会执行直接返回prev也就是NULL单节点时循环执行一次cur-next改为NULL返回prev指向原节点。所以这两个边界不需要额外判断这是迭代法的优势。递归法的基本条件是if (head NULL || head-next NULL) return head这句话同时覆盖了空链表和单节点两种情况。还有一点容易忽略反转结束后原头节点的next一定要置为NULL也就是代码里的head-next NULL。如果漏掉这行最后的链表会形成环OJ上会直接报“运行时错误”或者内存超限。我记得当年的题有一个测试点专门考验这个很多人就是在那里翻车的。5. 在线编程平台的隐藏规则判题机制、输入输出与复杂度估算5.1 判题系统到底怎么运行在线编程题和我们平时在IDE里写代码不一样。OJ系统的大致流程是把你提交的代码放到服务器上编译然后用预先准备的多组输入数据作为标准输入运行你的程序再把程序的标准输出和标准答案做逐字节比对。只要有一组数据对不上这道题就不给过。这意味着两件事。第一你的主函数一定要能够处理多组输入别只处理一组就结束。第二程序运行时不能有任何多余输出printf调试信息之类的一定要删干净否则标准输出里混入了杂音比对直接失败。还有一个很实用的认知OJ判题时常用特殊判题Special Judge来忽略行末空格和多余换行但也有些题目是严格逐字节比对。最稳妥的做法是输出格式跟题目要求保持一致该换行换行不该加空格别加。5.2 时间复杂度的估算方法在线编程题的数据范围往往就写在题目里看到n的范围第一反应应该是估算复杂度决定用什么算法。这里给一个简单参考标准1秒大概能执行10^8次简单运算如果题目限时1秒那你的算法复杂度乘以数据规模不能超过这个量级。我整理了一张表数据规模O(n^2)O(n log n)O(n)1,00010^6可行约10^4可行10^3可行10,00010^8临界约10^5可行10^4可行100,00010^10超时约10^6可行10^5可行1,000,00010^12超时约10^7可行10^6可行所以当你看到n是10^5的时候写O(n^2)的暴力解法基本等于自杀。这个估算习惯要在平时刷题时就养成不要等到考场上才去硬算复杂度。另外空间复杂度也要注意特别是递归深度。递归如果深度达到10^6程序可能触发栈溢出。2016年那会儿OJ平台对递归栈的限制就更严能用迭代就不要用深度很大的递归。5.3 编译环境与语言特性在线编程平台的编译器版本通常比本地新版软件落后不少。2016年很多OJ平台默认的是GCC 4.8左右C11的一些特性已经支持但C14/17的特性就别指望了。我在现场写代码时格外注意不依赖auto、lambda这种语法糖尽量用最基础、最稳的写法因为目标不是展示语言特性而是让程序在评测环境下能编译、能运行。头文件也一样。本地IDE可能自动帮你include了 但OJ不会。你自己用了std::sort就必须include 用了std::string就必须include 。写完代码后最好在脑子里模拟一遍从空文件开始编译的过程确认每个用到的函数库都被引入。一句话总结在线编程题考验的是“在受限环境下写出能跑通的代码”的能力宁可代码朴素一点也不要因为花哨的写法导致编译失败。6. 从这场笔试提炼的复盘方法论边界条件、极端用例和刷题节奏6.1 我到底输在哪美丽联合这场笔试我最终拿到了面试机会但第一题因为ans初始化的低级错误扣了分这个教训我记到现在。复盘的时候我把失败原因归结为三点。第一刷题时对边界条件缺少系统性的敏感。我平时练习都拿常规测试用例跑很少刻意构造全负数、空数组、单元素数组这类极端用例导致一上考场就翻车。第二比较器这类自定义规则的细节掌握不牢。第二题我虽然写对了但中间确实反复确认过比较逻辑浪费了不少时间如果平时多练就不会这么犹豫。第三递归链表反转理解不深现场一度想用递归绕了几分钟才转回迭代时间被白白消耗。说白了不是不会算法是基本功不够扎实。在线编程题专门考这些东西就是为了筛选出基本功扎实的候选人。6.2 我后来形成的刷题框架这次笔试之后我调整了刷题方法核心是“分类专题加限时模拟加错题复盘”三件套。分类专题是指按数据结构或算法专题集中练习比如动态规划单独刷两周链表操作单独刷一周字符串处理单独刷一周。每个专题内部从模板题开始再做变体题直到看到同类题目能条件反射地想到常规解法。这个阶段不需要追求题量追求的是把每个专题的套路吃透。限时模拟是笔试前两周的冲刺方式找一套完整笔试题给自己定一个严格的时间模拟在线笔试的环境。这个练习的关键是逼自己适应考场节奏学会做时间分配。我后来发现很多人在考场上不是不会做而是压力下思路混乱。模拟考试就是为了提前适应这种压力。错题复盘是长期积累动作。每道错题都要记录三个东西错在哪一步、正确思路是什么、我的解法缺了什么条件。过一段时间重新做一遍错题检验自己是否真的掌握了。这个习惯坚持下来效果比盲目刷题强很多。6.3 给后来者的临场建议结合我自己踩过的坑给你几条临场经验。第一写代码之前先在草稿纸上构造一个最小测试用例手动跑一遍你的思路。比如链表反转就画三个节点的链表把prev、cur、next的变化过程一步步画出来。画完再写代码准确率会高很多。第二写完代码之后不要立刻提交自己构造三个极端用例空输入、单个元素、全负数或全相同元素在脑子里过一遍程序逻辑看输出是否符合预期。第三输出格式多看两遍尤其注意排序题里频次相同按字典序这样的条件漏掉一个条件等于这题白做。最后分享一个小技巧我习惯在每次笔试前把常见模板代码默写一遍。最大连续子段和的动态规划、链表反转的迭代写法、二分查找、快速排序这些高频代码都是默写不用现想。一旦考场上碰到直接套模板把思考时间留给真正难的地方。这套习惯从2016年一直沿用到现在对新人来说性价比非常高。