从百度2016研发笔试看大厂在线编程题的底层逻辑与备战策略

1. 备战百度研发岗在线笔试先搞清楚它到底在考什么每年这个时候都有不少朋友来问我“百度研发工程师的在线编程题到底怎么准备”“是不是刷完LeetCode就够了”作为一个参加过百度校招、也当过面试官的人我想先泼一盆冷水在线编程题和 LeetCode 刷题表面上看都是写代码实际上的考察逻辑完全不是一回事。2016年的百度研发工程师在线编程题放到今天的视角看依然很有代表性。那会儿的题目风格和现在相比变化其实不大核心就是三件事算法基本功、代码实现的稳健性、在限定时间内的工程决策能力。注意第三点才是真正的分水岭。很多人在牛客网或者赛码网上刷题往往有一种错觉题目能 AC 就万事大吉。但在百度这类公司的在线笔试里AC 只是及格线。你提交的代码会被放到一个相对严苛的评测环境里去跑内存限制、时间限制、极端输入、边界用例任何一环出问题都可能让你“编译通过但零分”。那百度 2016 研发工程师在线编程题的题目到底长什么样根据当年的笔试回忆和题库收录它涵盖的题型大致集中在这样几个方向字符串处理、数组与排序、贪心策略、动态规划、二叉树与图论基础。从难度梯度上看前 1-2 题属于“热身题”考察基本语法和简单逻辑中间题目开始上强度涉及常见算法的变形最后 1-2 题则是有区分度的压轴题往往需要你对某个特定场景有足够敏锐的建模能力。这篇文章我想结合当年备考和出题的经验把百度在线编程题最核心的考点、最容易踩的坑、以及真正有效的备战路径掰开揉碎讲清楚。不是为了让你背题而是让你知道这类“大厂在线编程题”的底层逻辑以后再遇到其他公司的笔试也能举一反三。2. 核心考点拆解百度这类题目背后真正想验证的能力很多人以为在线编程题就是考察“你会不会写代码”这个理解太浅了。我参与过校招笔试出题和阅卷站在出题人的角度一道在线编程题至少承担着三个层面的筛选任务。2.1 第一层基本语法和API熟练度不过关直接出局这听起来好像很低级但现实是每年都有相当比例的人在字符串转整数、输入输出的处理这种环节上栽跟头。2016年那会儿百度的题目还比较偏向 C/C/Java 这类语言数据读取用的还是最朴素的scanf/cin或者Scanner。举个例子题目要求输入一行以空格分隔的整数很多人直接写int n; cin n; int* arr new int[n]; for (int i 0; i n; i) cin arr[i];这个写法本身没问题但如果输入数据不是标准的 N 数组元素形式而是多行、每行数量不固定也没有明确告诉你第一行是 N很多人就懵了。更典型的情况是题目说“输入数据包含多组测试用例”你还按单组用例去写结果只能过样例后面全挂。这类问题的本质不是算法不会而是你对“标准输入输出流”的处理不够敏感。想解决这个问题平时练习时必须有意识地用“笔试环境”做题而不是在本地 IDE 里写好了再粘进去后者会掩盖很多处理输入的坏习惯。2.2 第二层算法复杂度估算能力决定你过不过得了大样例百度题库里大部分题目数据范围都是算好的。比如有的题 N 最大 10^5那就意味着 O(N^2) 的解法在超时边缘疯狂试探有的题 N 最大 10^3那 O(N^2) 反而是你能想到的最朴素正解。我见过太多人拿到题就闷头写写完一跑小样例过了一提交直接 Time Limit Exceeded。然后开始怀疑人生我解题思路明明对啊怎么超时了其实就是没有在动笔之前先算一笔复杂度账。一个很实际的经验拿到题目先把数据范围圈出来然后立刻估算可接受的时间复杂度上限。通常 1 秒的时限操作数应该控制在 10^7~10^8 以内C 也许能跑到 10^8 的边缘Java 和 Python 要更保守一些。比如 N 10^5你要么设计 O(N) 或 O(N log N) 的算法要么就得接受 O(sqrt(N) * N) 这种带优化剪枝的方案纯 O(N^2) 基本是死路。2.3 第三层边界条件与极端输入是拉开差距的地方百度系的算法题非常喜欢在边界条件上做文章。就拿“三个数最大乘积”这种题来说类似题很多人上来就排序取末尾三个正数相乘逻辑简洁又高效。但是如果数组里有负数呢负负得正的情况你考虑了吗题目如果只是问你“给定一个整数数组找出三个数的最大乘积”你需要考虑的无非就是两种情况最大的三个正数相乘最小的两个负数乘以最大的正数但百度 2016 年的题往往不会让你这么舒服。它可能给你的是“三个子数组”、“乘积最大子数组的变体”、或者“树上三个节点的最长路径”等等。这个时候你如果还停留在“背模板”的层面就会非常被动。边界的真正可怕之处在于它会让你在毫无防备的情况下丢分。样例数据永远是精心挑选的“正常情况”而评测数据里一定会有只有 1 个数、所有数相等、全部为负数、最大值和最小值同时出现这类极端场景。你要做的不是写完代码后感叹“我过了样例”而是把代码提交之前先自己在脑子里把这些边界场景全部过一遍。3. 经典题目实战从破题思路到完整代码推演光说理论没有用我挑两道具有代表性的题目风格带你完整走一遍破题、设计、编码、优化的全过程。这些题目不是我凭空杜撰的而是当年题库里反复出现的类型变体思路完全可以迁移。3.1 字符串重排判断类题目别掉进全排列的坑有一类题是这样的给定两个字符串判断其中一个能否通过重新排列变成另一个类似“有效字母异位词”。这个题本身很简单排序比一比或者用哈希表统计字符频次比一比。但百度 2016 年附近很喜欢考的是它的升级版。描述大致是给定一个字符串 s 和一个字符串 t判断 s 的某个排列是否是 t 的子串。如果你一看到“排列”二字就想生成全排列那这道题就凉了。正确的思考路径是所谓“s 的排列”本质是字符种类和每个种类的数量都相同只是顺序不同判断一个字符串是否是另一个的子串最经典的做法是滑动窗口将这两者结合用固定大小的滑动窗口去遍历字符串 t窗口内字符串的字符频率与 s 相同就说明 t 中存在 s 的某个排列。思路确定了代码就好写。用 Java 演示的话大概是public boolean checkInclusion(String s1, String s2) { if (s1.length() s2.length()) { return false; } int[] count new int[26]; int[] window new int[26]; for (int i 0; i s1.length(); i) { count[s1.charAt(i) - a]; window[s2.charAt(i) - a]; } for (int i s1.length(); i s2.length(); i) { if (Arrays.equals(count, window)) { return true; } window[s2.charAt(i) - a]; window[s2.charAt(i - s1.length()) - a]--; } return Arrays.equals(count, window); }这段代码的时间复杂度是 O(n)其中 n 是 s2 的长度。空间复杂度 O(1)因为两个数组长度恒定为 26。这类题的核心考点并不在于你知不知道滑动窗口而在于你能不能把“排列”这个条件转化成“频次完全相同”这个数学模型。做这类题目建议用实例来辅助思考。比如 s ab、t eidboaoo你手动滑动一下窗口就知道窗口在移动过程中要不断更新左右两侧的字符频次而不是每次重新计算窗口内所有字符的数量那样就退化成了 O(n * m) 的暴力解法。这里我还想强调一点在线编程题的评测样例里极大概率会有 s1 长度大于 s2 的情况即直接不可能匹配也极大概率会有 s1 或者 s2 为空的特殊情况。这种“一眼假”的边界条件必须在代码开头就处理掉否则后续逻辑再严谨也会因为数组越界或者逻辑漏洞导致运行时错误。3.2 数组区间合并类题目贪心策略的经典应用有一类题目也是百度题库的常客我把它称作“区间合并类”。普通版本很简单给一组区间把有重叠的区间合并。但百度 2016 年的在线编程题更喜欢在这个基础上加一层包装。比如给定一些区间和一个新插入的区间要求将新区间插入到已排序的区间列表中并合并重叠部分。这类题的核心考点是“贪心”和“分类讨论”。解题思路是先把所有区间按左端点排序遍历区间如果新区间与当前区间没有交集就直接添加如果有交集就更新新区间的左右端点让它不断扩张遍历结束把新区间插入。有人可能会问为什么不在原数组上做更新还要另外建一个列表原因很简单在线编程题的输入往往是通过参数传递的代码运行在评测机里随意修改入参会带来不可预知的风险。宁可多开一份 O(n) 的空间也要保证逻辑清晰。在实际编码中最容易被忽略的是处理新区间完全包含在某个老区间内部的情况。这时候新区间不需要做任何插入因为它已经被覆盖了。这个 case很多人都会写错过。我们来推演一下完整的实现思路public int[][] insert(int[][] intervals, int[] newInterval) { Listint[] result new ArrayList(); int i 0; int n intervals.length; // 左侧完全不重叠的部分 while (i n intervals[i][1] newInterval[0]) { result.add(intervals[i]); i; } // 重叠部分合并 while (i n intervals[i][0] newInterval[1]) { newInterval[0] Math.min(newInterval[0], intervals[i][0]); newInterval[1] Math.max(newInterval[1], intervals[i][1]); i; } result.add(newInterval); // 右侧完全不重叠的部分 while (i n) { result.add(intervals[i]); i; } return result.toArray(new int[result.size()][]); }这个实现的时间复杂度是 O(n)空间复杂度也是 O(n)用于存储结果。它把问题拆解成了三段左侧无关区间、重叠区间、右侧无关区间。这个思路一旦建立就不容易写错。这种题目在日常笔试中出现频率非常之高不是为了让大家背代码而是为了训练一种“区间思维”遇到区间先想到排序遇到合并先想到比较边界遇到数组、长度指定的场景先去思考是否为 null、是否为空数组这类边界。4. 百度笔试环境与评测机制不了解这些代码写得再好也可能零分我见过太多候选人在面试复盘时说“我本地跑得好好的怎么提交就零分”这里面的原因很多时候不是算法有问题而是对在线评测环境Online JudgeOJ的机制理解不够。4.1 评测机的输入输出处理和本地 IDE 完全不同本地 IDE 写代码你通常会定义好测试用例写在 main 函数里直接跑。但在线编程题不一样评测机会用几十组你根本看不到的数据去执行你的程序然后用标准输出逐一比对结果。这就非常考验一个基本功对输入数据的容错能力。以 C 为例推荐使用ios::sync_with_stdio(false); cin.tie(0);这两行来加速输入。这个操作在大数据量下能明显提升速度。原因在于默认情况下cin与scanf是同步的为了保证混用时的正确性会带来额外开销。你关闭同步之后cin的效率才能和scanf对齐。以 Java 为例不要用Scanner去读取大数据量输入效率很低。最稳妥的方式是用BufferedReaderStringTokenizer或者手动 split这在牛客、赛码网这类平台上尤其管用。4.2 内存限制比你想象中更严苛百度 2016 年的在线笔试用的评测环境通常有明确的内存限制比如 64MB 或 128MB。这个数字意味着什么呢如果你用 C 开了一个int a[10000][10000]的二维数组100 兆就没了直接内存超限。很多人在刷题软件上从不在意内存因为那些平台通常只测时间不测内存。但在大厂笔试里内存超限和运行超时一样都直接判零分。一个实际的建议是平时训练时就要养成估算内存的习惯。1 个 int 是 4 字节1 个 long 是 8 字节一个 10^6 的 int 数组大约占 4MB。当你设计到 10^7 级别的时候就要想想是否有必要设计到 10^8 级别几乎一定会崩。这时候就该思考能不能用滚动数组、状态压缩、或者干脆换一种算法。4.3 多组测试用例的坑你必须知道在线编程题最经典的陷阱之一就是“多组输入”的处理。题目描述里可能会写“输入数据包含多组测试用例每组占一行”或者“输入到文件尾结束”。比如一个经典的计算题给定两个整数 a 和 b计算 a b 的和。输入有多组数据每组占一行。很多第一次参加笔试的人写成int a, b; cin a b; cout a b endl;样例只给了一组数据本地跑出来也是对的但提交之后评测机给了多组数据程序只处理了一组就退出后面的全没输出。正确写法是int a, b; while (cin a b) { cout a b endl; }这个 while 写法本质上是利用了输入流在读到文件末尾时cin返回 false 的特性循环自然结束。Java 里对应的写法是Scanner sc new Scanner(System.in); while (sc.hasNextInt()) { int a sc.nextInt(); int b sc.nextInt(); System.out.println(a b); }如果你用BufferedReader就是while ((line reader.readLine()) ! null)。所以拿到题目第一件事就是要先判断题目要求的输入形式是单组还是多组是定长还是一行不定长这些信息全藏在题目的输入描述里。千万不要凭感觉猜。5. 高效备战的刷题路线与时间分配策略聊完了考点和评测机制最后必须要落到执行层到底应该怎么准备才算有效备战5.1 分阶段刷题法不要一上来就硬刚难题我建议把备战周期分成三个阶段每个阶段目标不同心态也不同。第一阶段第 1-2 周基础题型扫盲。集中刷字符串、数组、模拟、排序、二分查找、双指针这类“必考题型”。刷题目标不是追求难题而是保证自己在 10 分钟内能写出正确且简洁的代码。这一阶段每道题都要追求一次 AC不要反复调 bug。因为笔试现场是没有机会反复调试的。第二阶段第 3-4 周高频算法强化。重点刷贪心、动态规划、DFS/BFS、树和链表相关的题目。百度这类公司非常喜欢考树上问题比如最近公共祖先LCA、树的直径、二叉树遍历变体等。这一阶段的目标是见到题能快速反映到对应的算法模型上。第三阶段考前 1 周全真模拟。找两个固定的时间段严格按照笔试的时间长度和题量来做模拟卷。比如百度的在线笔试时长一般 1.5~2 小时题量大概 3~4 道你就用这个标准要求自己。这时候不要追求“我全做出来了”而是练习时间分配能力——哪些题必须拿满分哪些题做到一半要果断放弃哪些题可以用暴力解法拿部分分数。5.2 刻意练习“写注释”和“代码格式化”我知道有些人会觉得笔试时间紧张写注释是浪费时间。但我要分享一个反向经验在在线编程题的高压环境下写简洁的注释反而能帮你整理思路。每次写完一段逻辑用一行注释概括这段逻辑的用途比如// 左侧无交集部分直接添加。这样你一旦代码写错了回读的时候能迅速定位是哪一段逻辑出了问题。更重要的是很多大厂的面试官在笔试结束后真的会看候选人的代码质量。就算你的题没有完全通过但代码结构清晰、注释精准也能在面试环节给你加分。5.3 别迷信“题海战术”要注重复盘刷 300 道题不如精刷 100 道题并复盘三遍。这里说的复盘不是把代码再看一遍而是每道题 AC 之后主动去思考三个问题这道题还有没有更优的时间复杂度解法如果输入数据量扩大十倍我的解法还能过吗如果换一道题我该怎么套用这道题的思路在线编程题的核心竞争力从来不是碰到过原题而是当你遇到一道陌生的题目时能迅速拆解出它的数学模型找到可用的算法然后稳健地实现出来。这才是大厂真正看重的研发工程师潜质。6. 最后聊点实际的笔试现场的心态管理与应变技巧这一节的内容是我在面试复盘时最常跟候选人聊的。很多人代码能力没问题但一到在线编程题就跟换了一个人一样最后结果很不理想。你要知道笔试现场和平时刷题最大的不同是试错成本极高。平时你可以反复编译、调试、看错误信息但笔试环境通常只允许你有限次提交超过次数可能直接禁止提交或者本场成绩直接记零。所以动笔写代码之前多花两分钟在草稿纸上或者直接在代码注释里把思路理清楚是对你自己最大的保护。做题顺序上我的建议是先遍历一遍所有题目把题目难度按照“一眼有思路”“需要想一下”“完全没头绪”分成三类然后优先做完全有把握的题再花时间攻克“需要想一下”的最后如果还有时间才考虑“完全没头绪”的题用暴力解法或者特判样例的方式拿部分分。还有一个技巧是关于调试输出的。很多人喜欢在代码里加System.out.println()或者cout来打印中间结果这是非常正常的调试方式。但提交前一定要记得删掉。如果你忘了删那些调试信息会混入标准输出评测机在比对结果时直接判定 Wrong Answer。这个问题我只提醒一次但每年都有不少人因为这个原因挂掉本来能通过的题。最后回到开头那句话百度 2016 研发工程师在线编程题看似只是一场笔试其实是你在正式进入职场前一次综合能力的检验。算法功底、代码洁癖、边界意识、时间管理、临场应变这些素质恰恰就是日后作为研发工程师每天都要用到的。备战这类笔试的过程本身是对自己研发基本盘的一次系统性加固。如果你正在准备这类笔试或者正在纠结自己的代码能力到底行不行听我一句别想太多找一套题限时 2 小时模拟真实环境坐下来写。写得出来你就知道自己哪里行写不出来你更该庆幸还有时间补。