校招在线编程题全攻略：高频题型与AC实战技巧

2016年那会儿美丽联合集团正值蘑菇街和美丽说合并后的关键阶段技术团队扩充力度很大研发工程师岗位的校招笔试基本都走在线编程题的形式给定题目描述和输入输出约定在限定时间内写完代码并提交系统自动跑测试用例判分。这种形式对候选人来说压力不小因为不只是“会不会写代码”的问题而是要在有限时间内快速建模、选对算法、写出能通过边界用例的代码同时还得适应OJ平台的输入输出规则。这篇文章把我当年整理和复盘这套在线编程题的经验完整写出来包括题型分布、高频考点的完整解法、笔试现场的输入输出处理和复杂度预判以及后来刷题过程中踩过的坑。写给正在准备校招研发岗位的同学也写给那些想系统补算法基础、对在线编程题还没有形成套路的人。内容全部基于常见校招真题风格做归纳题目不是某一场考试的原话复刻但解题思路和考查点是非常接近的完全可以直接参考。1. 2016年美丽联合研发岗在线笔试的考查逻辑1.1 电商业务场景下的笔试定位美丽联合的业务主体是电商平台用户量级大、商品数据多、大促流量陡增研发岗日常面对的核心问题基本都落在数据聚合、检索、排序、状态流转这些事上。在线编程题的设计也明显倾向于这类场景不会考特别偏门的算法而是选择能够映射到真实业务逻辑的基础题比如数组的合并与去重类似多数据源的商品聚合、子数组求和类似统计区间的销售贡献、版本号比较类似客户端版本升级判断。这意味着什么它考的不是你会不会背某个高级数据结构而是你能否把业务问题抽象成标准的算法模型。很多同学准备笔试时喜欢猛刷难题但实际这类电商公司的校招在线编程题更看重基础能力和代码正确性。三道题里有两道是“大家都会做”的题区别就在于谁能一次AC、谁的代码能扛住边界输入。能过笔试的人往往不是算法竞赛选手而是基础扎实、写码稳的人。1.2 在线编程题的题型分布与答题形式从题型分布上看研发岗在线笔试一般控制在三到四道编程题时间通常是一个半小时到两个小时。题目难度呈梯度分布第一题偏简单常见的数组、字符串处理考查基本功第二题中等开始涉及动态规划或双指针等经典套路第三题难度上探有时会有一道偏模拟或需要数据结构的题用来区分候选人上限。答题形式也很有特点。系统会在页面给出题目描述、输入格式、输出格式和样例候选人写完代码后点击提交OJ后台用多个测试用例包括大量边界用例对程序做评测按通过用例的比例给分。也就是说代码不是给人看的是给机器跑的。不少人在本地IDE里跑得很顺一提交就是0分问题往往不是算法错了而是输入输出格式没有严格按题目要求来。笔试里这叫“格式错误”但在判分系统里格式错误有时直接被当成答案错误处理。2. 高频考题解构三类典型题目与完整解法2.1 数组操作题合并两个有序数组的正解与边界处理第一类必考的题型是数组操作其中“合并两个有序数组”几乎是校招笔试的常青树。题目描述很直接给定两个升序排列的整数数组nums1和nums2要求把nums2合并到nums1中合并后仍然保持升序。nums1的长度足够容纳合并后的所有元素。这道题最直观的解法是从前往后合并但这样做有一个致命问题nums1前部的元素会被覆盖需要额外使用一个临时数组存储nums1的元素空间复杂度变成了O(m)。笔试现场很多同学就是这样写的虽然能通过但不是最优解。最佳解法是从后往前合并因为nums1的后半部分是空的不会产生覆盖问题。#include stdio.h void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int i m - 1; // nums1 有效元素的最后一个下标 int j n - 1; // nums2 的最后一个下标 int k m n - 1; // 合并后数组的最后一个位置 while (i 0 j 0) { if (nums1[i] nums2[j]) { nums1[k--] nums1[i--]; } else { nums1[k--] nums2[j--]; } } // 如果 nums2 还有剩余直接拷贝到 nums1 前面 while (j 0) { nums1[k--] nums2[j--]; } } int main() { int nums1[6] {1, 2, 3, 0, 0, 0}; int nums2[3] {2, 5, 6}; merge(nums1, 6, 3, nums2, 3, 3); for (int i 0; i 6; i) { printf(%d , nums1[i]); } return 0; }这里有几个关键点需要特别注意。第一i和j的初始值分别对应两个数组中最后一个有效元素而不是数组的物理长度因为nums1后面预留了空位。第二while循环结束后只需要处理nums2剩余的情况nums1剩余的部分已经在正确的位置上了。第三这段代码的时间复杂度是O(mn)空间复杂度是O(1)这是面试官想看到的版本。这道题对应的业务场景很清晰电商后台经常需要合并来自不同渠道的商品列表比如把搜索召回的商品和运营推荐的商品合并成一个有序列表再分页展示。多路归并的思想在很多地方都会用到这也是为什么这道题出现频率这么高的原因。笔试里我建议先把从后往前的合并逻辑写出来同时用注释标注边界条件阅卷系统和面试官都会满意。2.2 动态规划题最大连续子数组和的两种实现第二类高频题是动态规划入门级别的“最大连续子数组和”。题目问的是给定一个整数数组找出一个具有最大和的连续子数组返回其最大和。比如输入[-2,1,-3,4,-1,2,1,-5,4]最大连续子数组是[4,-1,2,1]和是6。这是动态规划里最经典的一道题核心思路是维护一个“以当前元素结尾的最大子数组和”。状态转移方程是dp[i] max(dp[i-1] nums[i], nums[i])。意思是要么把当前元素接在前面的子数组后面要么从当前元素重新开始一段子数组。理解这个转移方程是解题的关键。#include stdio.h int maxSubArray(int* nums, int numsSize) { if (numsSize 0) { return 0; } int maxSum nums[0]; int curSum nums[0]; for (int i 1; i numsSize; i) { if (curSum 0) { curSum nums[i]; } else { curSum nums[i]; } if (curSum maxSum) { maxSum curSum; } } return maxSum; } int main() { int nums[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}; int result maxSubArray(nums, 9); printf(%d\n, result); return 0; }注意这里做了一个空间优化不需要额外开dp数组因为递推时只需要前一个状态curSum用变量滚动更新就可以。这体现了在线编程题的一个重要考察点在正确的前提下是否具备优化意识。这道题的易错点有两个。一是连续子数组至少包含一个元素所以初始化时maxSum不能设为0而要设为nums[0]否则全负数数组会得到错误答案。二是很多人会下意识用双重循环枚举所有子数组复杂度O(n^2)在数组长度达到10^5级别时必然超时。动态规划的O(n)解法是笔试唯一能过的方案。这道题的变体很多比如返回最大子数组的起始位置、二维矩阵中的最大子矩阵和等备考时可以把这些变体一起刷了举一反三效率最高。2.3 模拟/字符串题版本号比较的完整思路第三类题是字符串处理其中版本号比较在2016年前后的笔试里出现频率很高。题目要求是比较两个字符串版本号version1和version2版本号由数字和点号组成比如1.0.1或0.9.9。规则是逐段比较数字大小如果版本号相同返回0version1新返回1version2新返回-1。这道题表面上不难但细节非常多。第一个坑是版本号长度可能不同比如1.0和1.0.0其实是相等的因为末尾缺省的部分可以视为0。第二个坑是每一段可能有前导零比如01和1是相等的。第三个坑是字符串可能包含多个连续的点号吗按照标准版本号语义不会出现这种情况但笔试题目有时会故意放宽输入约束代码要具备一定的容错能力。#include stdio.h #include string.h #include stdlib.h int compareVersion(char* version1, char* version2) { int len1 strlen(version1); int len2 strlen(version2); int i 0, j 0; while (i len1 || j len2) { int num1 0; int num2 0; while (i len1 version1[i] ! .) { num1 num1 * 10 (version1[i] - 0); i; } while (j len2 version2[j] ! .) { num2 num2 * 10 (version2[j] - 0); j; } if (num1 num2) { return 1; } if (num1 num2) { return -1; } i; // 跳过点号 j; } return 0; } int main() { printf(%d\n, compareVersion(1.0.1, 1.0.2)); printf(%d\n, compareVersion(1.0, 1.0.0)); printf(%d\n, compareVersion(0.9.9, 1.0.0)); return 0; }这段代码用两个内层while循环分别解析出点号之间的数字然后直接比较。有一个细节要注意i和j在循环结束后需要跳过点号但如果某个字符串已经遍历完了再执行i就可能越界。这里while循环的条件是i len1 || j len2当i到达len1后num1会保持为0j可能还在继续这种情况是安全的。如果两个字符串长度不同短的那一侧后续解析出来的数字都是0自然就和长版本号末尾的0对齐了。这道题对应的是客户端版本升级的判断逻辑是否提示用户更新、后台接口返回的新版本是否比当前版本新都需要做版本号比较。对于校招笔试来说这类题考查的是字符串解析和边界条件控制的细致程度属于“写对容易写全难”的题很适合用来区分基础是否扎实。3. 在线编程题现场输入输出、复杂度与答题节奏3.1 输入输出格式的处理一半以上的丢分点在线编程题和平时写业务代码最大的区别是你必须严格适配OJ平台的输入输出约定。很多候选人算法写对了却因为输入输出格式问题丢分这是最可惜的。常见的要求包括输入可能有多组测试数据需要用while(scanf(...) ! EOF)循环处理输入的数字之间用空格或换行隔开读取时用scanf天然处理输出不能带多余的文字提示比如“结果是”只要输出答案本身每行输出一个结果行末换行。我见过最多的错误是这几种。一是题目说输入第一行是数组长度第二行是数组元素有人直接写死成固定长度读取一旦测试用例换一个长度就崩了。二是输出结果时多打了空格。三是多组输入的场景下没有清空数据结构导致上一组测试数据残留。应对方法很简单拿到题目后先花30秒确认输入输出格式把读取和输出的代码框架先写好再填充核心算法逻辑。这样即使有bug至少输入输出是按约定走的。一个实用的技巧是本地调试时把样例输入复制到一个文本文件里用命令行的重定向来跑程序比如./program input.txt这样能模拟OJ的真实输入方式比手动敲数据高效得多。在线编程题的判分是按测试用例逐个跑的你的程序需要的是“可持续运行”的能力而不是“跑一次就算完”的能力。3.2 复杂度预判如何避免运行时超时在线编程题默认会有时间限制常见的是1秒到2秒。1秒内大约能完成10^8次左右的基本运算这是判断算法是否可行的经验值。拿到题目先看数据范围如果数组长度n是10^5使用O(n^2)的算法最坏情况下是10^10次运算必然超时如果n是1000O(n^2)完全没问题。所以拿到题目第一件事不是写代码而是根据数据范围倒推需要什么级别的复杂度。举几个常见场景。数组长度10^5到10^6只能接受O(n)或O(n log n)的算法排序、双指针、哈希表、动态规划都是首选。长度10^4O(n^2)勉强可过但要小心常数因子。长度100以内O(n^3)也可以接受暴力搜索、区间DP都可以尝试。递归深度方面如果n超过10^4而题目又需要递归就要注意是否可能爆栈必要时改成显式栈或迭代写法。另外要留意的还有内存限制常见的OJ内存限制是256MB。有些同学习惯开一个二维数组来dp如果n10^5开int二维数组[10^5][10^5]直接就内存溢出了。遇到大数组优先思考状态压缩比如最大子数组和那道题的滚动更新。这类优化放在代码层面就是多那么几行但对笔试判分来说影响是决定性的。3.3 从读题到提交的标准化答题流程在线笔试的时间有限必须有一套标准化的答题节奏。我给自己定的流程是这样的拿到一道题第一遍快速读题只做两件事——明确输入是什么、输出是什么判断属于哪类算法模型。第二遍精读圈出数据范围和特殊条件比如数组是否有序、是否包含负数、是否可能为空。这两步控制在3分钟以内。然后花5到8分钟设计算法和复杂度估算。这一步很多人会跳直接上手写代码结果写到一半发现思路有问题再推翻重来反而更慢。先在草稿纸上把状态转移方程或双指针的移动规则写清楚确认没有遗漏边界条件后再写代码。写代码时按功能分块读取输入、核心逻辑、输出结果。每写完一块简单检查一下是否有明显的语法错误和类型错误。所有题目完成后预留10分钟做自测。自测用例除了题目给的样例还要自己构造几个边界用例空数组、只有一个元素、全负数、最大数值溢出。比如用int存储数组和可能会超过2^31-1就必须改成long long。在线编程题经常在这样的小地方设陷阱把你的代码在本地跑一遍边界用例再提交能避免大量的反复提交扣分。4. 在线编程题的常见问题与排查技巧4.1 编译错误代码写完却跑不起来的常见原因在线笔试中编译错误是最让人心态崩掉的情况因为你不一定能看到详细的编译日志只能看到一个“编译失败”之类的提示。我自己遇到过的原因大致有几种头文件缺失比如用到memset但没有包含string.h用到malloc没有包含stdlib.h函数命名冲突有些OJ平台不允许main函数以外的函数叫write、read这类名字语法细节C语言里全局变量声明后直接初始化数组时用了变量长度。排查这些问题的办法是养成“本地可编译再提交”的习惯。平时练习时每道题都坚持在本地IDE编译运行不要说“大概没问题”就提交。在线笔试的平台一般会提供语言版本信息比如采用的是C99还是C11、是否支持C11提前确认这些可以避免使用编译器不支持的语法特性。我印象比较深的一次是使用C99的变长数组VLA本地GCC默认支持到了OJ的编译环境却不支持最后把代码改成动态内存分配才通过。平台差异是真实存在的用最基础的语法写代码是降低编译风险最有效的方式。4.2 答案错误逻辑看起来对为什么判错还有一类非常头疼的情况是“答案错误”但你觉得自己的逻辑没问题。这时候要做的就是排查边界条件。几乎每道题都有几个经典陷阱比如合并有序数组中nums1的有效长度m和物理长度的区别最大子数组和中全负数数组的初始化值版本号比较中长度不对齐的问题。如果你在这些点上做了处理却仍然出错还有一个排查方向是读取数据时对换行的处理。经典坑点是使用getchar或fgets读取字符串时字符串末尾可能带有换行符导致解析时出错。另一个是输入中包含多组数据时用gets读取一行后需要清空缓冲区但gets本身就不安全OJ环境有时也不支持。这类问题在本地测试时往往不会暴露因为手动输入的样例数据不会那么刁钻。批量跑测试用例时最容易出问题的都是这些输入输出细节。我的排查方法是把读入的数据先打印出来确认数据解析正确了再继续调核心逻辑。这个习惯能节省大量时间。4.3 超时的排查从算法和数据量反向找瓶颈“运行超时”比“答案错误”更让人焦虑因为题目逻辑可能是对的就是慢。排查超时的顺序是这样先看数据范围是否符合预期如果你的算法是O(n^2)而数据量是10^5这基本就是超时原因只能从算法层面优化如果算法复杂度在安全范围内还是超时检查代码里是否有意外的高开销操作。常见的隐藏性能杀手包括循环内频繁调用strlen计算字符串长度导致每轮都遍历整个字符串使用vector容器时频繁扩容而没提前reserve使用endl刷输出缓冲区C中导致大量IO耗时递归函数传参是值传递导致每层递归都拷贝大对象。这些细节在数据量小时完全看不出来数据量一大就原形毕露。在笔试现场可以用一个经验法则如果题目数据范围包含10^5级别任何可以提前算好的值都不要放在循环里重复计算任何不必要的对象拷贝都要尽量避免。5. 从这套在线编程题延伸出的备考路线5.1 按优先级排序的复习路线复盘完这套在线编程题后最值得做的一件事是反推出高效的备考路线。根据电商公司研发岗笔试的出题特点复习优先级可以这样排第一优先级是数组、链表、字符串、二叉树的增删改查和遍历这些是基本功几乎每场笔试都会涉及第二优先级是双指针、哈希表、排序算法手写快排和归并、二分查找它们能解决大量中等难度题第三优先级是动态规划的基础模型包括最大连续子数组和、最长递增子序列、背包问题、编辑距离等不求高深但求见到题目能识别出DP模型。每一类知识点都要配合在线编程题来练不能只看不写。刷题量不是重点重点是每道题都能独立从头写到AC。我自己的体会是做一道题后隔三天再重写一遍比一天连做五道新题效果更好。重复写同一道题会暴露你第一遍是“真会”还是“背会了”。校招笔试的题目难度通常不会特别高真正淘汰人的地方在于基础题的稳定性。5.2 每道题都要形成一题多解的意识在线编程题最有趣的地方在于同一道题往往有多个解法复杂度差别很大。备考时如果追求最高效率我建议每道题都尝试至少两种解法并对比分析。以合并两个有序数组为例除了从后往前合并的O(n)解法还可以用二分查找确定每个元素插入的位置再用memmove移动数据虽然代码更复杂但考察点完全不同再以最大连续子数组和为例除了动态规划还可以用分治法把数组分成左右两半最大子数组要么在左半边要么在右半边要么横跨中点复杂度是O(n log n)。这样做的好处是你能在笔试时快速切换思路。比如第一题的O(n)解法的代码没想清楚可以先写一个正确性明显的O(n log n)解法保底拿分时间充裕再优化。考场上最怕的是脑子里只有一种解法一旦卡住就无从下手。一题多解训练的是思维的灵活性。5.3 限时模拟和错题复盘是临考前的最后一步最后一个建议是考前两周进入限时模拟状态。找一套完整的在线编程题卡着真实考试的时间要求来做期间不允许看资料、不允许跳过难题。模拟的目的不是做对更多的题而是适应考试节奏什么题先放弃、什么题先写暴力分、什么时候开始自测。每次模拟结束后留出至少三十分钟做错题复盘。把没AC的题重新梳理一遍记录失分原因是算法选型错误、边界遗漏、还是输入输出问题。我发现很多人的错因是反复出现的比如总是忘了把sum初始化成第一个元素每次遇到全负数用例就错。把这类问题整理成一张自己的错题清单考前半小时只看清单提醒自己比考前再刷几套新题管用得多。笔试结束后不要急着丢掉草稿纸。如果你在代码里用了某个巧妙的优化写法趁热把它记录在笔记里。在线编程题是实战性很强的考试形式积累的每一道题、每一个错误都会在后续的面试和工作中产生回报。