2016年那阵子我正忙着准备校招刷得最多的就是百度研发工程师的笔试题。说实话百度笔试在当年互联网公司里算是很有代表性的题目不会故意刁难你但每道题都在检验你有没有把基础真正吃透。这套四我印象特别深因为它的题型组合很典型——一部分C/C细节题、一部分算法题还有一道系统设计题和一道思维题。考完出来跟同学对答案发现错的地方几乎全在平时没在意的细节上。这篇就把我当时对这套卷子的完整复盘过程写出来包括每道题我是怎么想的、错在哪、后来怎么补上的以及这类题目背后真正想考察的东西。适合正在准备校招的研发岗同学看也适合工作几年想回头检验基本功的在职工程师。整套卷子从我记忆里的结构看大致是8道选择题加2道编程题、1道系统设计题、1道附加思维题。下面我按考察方向重新组织把最有代表性的几道拉出来逐题拆解。1. 试卷全景这套题到底在考什么1.1 题型分布与考察层次先给一张我当时整理的题型分布表后面逐题讲的时候会反复提到这张表。题型数量考察方向典型考点C/C细节题3道内存布局、语法陷阱结构体对齐、sizeof、指针数据结构与算法4道经典算法、边界处理回文判断、数组右移、链表判环、哈希冲突操作系统题1道系统底层理解进程与线程、锁系统设计题1道工程架构思维短URL服务思维题1道逻辑推理与发散烧绳子计时看起来题目很杂但仔细看会发现三个层次非常清晰。第一层考基础语法和内存布局这决定你能不能写出不踩坑的代码第二层考数据结构和算法这决定你的代码效率第三层考系统设计和逻辑思维这决定你面对开放问题时有没有工程判断力。百度这套出题风格其实折射出研发岗的一个核心要求基础不牢后面全是空中楼阁。所以你会发现没有偏题怪题反而全是“你以为你会、其实未必对”的题。1.2 笔试设计的隐藏逻辑很多同学以为笔试就是刷题考完就完了。但站在出题人角度想一下会发现这套题的设计逻辑非常务实。第一选择题占比故意做得高。选择题不像编程题能靠调试救回来选错就是错而且往往设置两三个非常接近的干扰项。比如结构体对齐那道题四个选项分别是6、8、12、16你要是没真正理解对齐规则很容易凭感觉挑一个。这种题筛选的是“写过很多代码但没深究过底层”的人和“真正研究过内存布局”的人。第二编程题不给完整代码环境。当年笔试就是在线编辑器没有自动补全编译报错也只有简单的提示。这意味着你写代码必须一次写对靠调试器试错的路子在这里行不通。这很接近真实生产里写核心模块的感觉——你不能每次都靠跑起来再修。第三系统设计题分数占比高。短URL那道题我记得占了挺大分值如果你只写“用哈希生成短码”基本拿不到分。考官想看的是你能不能把存储、冲突、跳转、缓存、并发这些环节完整串起来。这和实际做项目的思维方式是打通的。2. 核心题目拆解从解题到读懂出题人2.1 C/C基础题结构体对齐是白给还是白给这题是整套卷子我印象最深的因为当年真的做错了。题目大致是struct A { char a; int b; short c; }; 求 sizeof(struct A)。我当时选了8正确答案是12。错因很简单我只把三个成员的大小加起来1427然后想当然地以为对齐到4就是8但我没把中间和尾部的padding都算上。实际内存布局是这样偏移01234567891011内容char a填充填充填充int bint bint bint bshort cshort c填充填充按默认4字节对齐规则char a占1字节之后为了int b的4字节对齐需要填充3字节int b占4字节然后short c占2字节最后结构体整体大小必须是最大对齐数4的整数倍所以尾部再补2字节总共12字节。这里核心在于理解为什么要对齐。CPU读取内存是按字长的如果int放在奇数地址一次读取可能要拆成两次访存操作。对齐是拿空间换时间的经典做法考的是你对“内存布局和性能关系”的理解。这类题的几个变形要一并掌握如果加了#pragma pack(1)sizeof会变成7因为取消了对齐按紧凑排列。如果成员顺序换成int a; char b; short c;占用的padding会少很多int 4 char 1 short 2 尾部1 8所以定义结构体时调整成员顺序能省内存。指针在32位系统占4字节64位系统占8字节别在这种地方翻车。补充一句实际经验刷题时这种题错了没关系但生产代码里结构体如果用于网络传输对齐规则不一致会导致协议解析错乱。所以这个知识点不只是笔试用线上踩坑也常见。2.2 字符串题回文判断的隐藏考点原题是判断一个字符串是否为回文但给了几个限制忽略空格和标点不区分大小写。比如A man, a plan, a canal: Panama应该返回true。第一反应是双指针一个从头走一个从尾走遇到非字母数字跳过比较时忽略大小写。这个思路没错但有几个细节特别容易漏。第一个细节是字符过滤条件。很多人只处理了空格没处理标点。原始字符串里可能包含逗号、冒号、句号你必须调用一个统一的判断函数比如C里的isalnum()或者自己写(accz) || (AccZ) || (0cc9)。第二个细节是大小写统一。两个字符相等比较时要么都转成小写要么都转成大写别一边大写一边小写直接比。C里tolower()就行但要注意它只对单个字符有效。第三个细节是边界条件。空字符串算不算回文单字符算不算这两个在题目里其实都应该算true但如果代码里没处理指针一开始就越界了。我当时就是漏了空串判断白丢了几分钟调试时间。给一版当时考场上写出来的解法C实现bool isPalindrome(string s) { int left 0, right s.size() - 1; while (left right) { while (left right !isalnum(s[left])) left; while (left right !isalnum(s[right])) right--; if (tolower(s[left]) ! tolower(s[right])) return false; left; right--; } return true; }时间复杂度和空间复杂度分别是O(n)和O(1)。这类题真正想检验的不是你会不会双指针而是你有没有把边界和字符处理想完整。面试的时候还有一追问如果字符串很长内存放不下怎么办可以改成流式读取加首尾比较或者分块处理。这一问就能看出你是背答案还是真理解。2.3 数组题循环右移K位的三种写法编程题里有一道给定数组nums长度为n把它循环右移k位要求时间复杂度O(n)空间复杂度O(1)。先说最容易踩的坑k不保证小于n。如果 n5, k7右移7位等价于右移2位。所以第一步永远是k % n我见过太多人在这里没有取模导致结果完全不对。接下来是三种实现思路的取舍。第一种暴力搬移。循环k次每次把最后一个元素移到开头其他元素后移。时间复杂度O(n*k)空间O(1)不符合O(n)要求直接淘汰。第二种额外数组。开一个新数组把每个元素放到(ik) % n的位置。时间O(n)空间O(n)不符合O(1)要求。第三种三次反转。这是最优解也是工程里最常用的技巧。以nums [1,2,3,4,5,6,7], k 3为例先反转整个数组[7,6,5,4,3,2,1]反转前k个元素[5,6,7,4,3,2,1]反转剩余元素[5,6,7,1,2,3,4]三次反转都是在原地做元素交换空间O(1)时间O(n)。这个思路的原理是右移k位本质是把数组后k个元素挪到前面且保持各自内部顺序。反转是整个反转加局部反转的组合操作利用反转的“可逆性”把元素顺序重新拼好。我当时在考场上的问题是反转边界写错了。第二段反转的范围是[0, k-1]第三段是[k, n-1]如果你把第三段写成[k-1, n-1]或者第一段范围没写对结果全错。所以写完反转函数后建议用k1和kn-1各跑一遍验证。C实现void reverse(vectorint nums, int l, int r) { while (l r) { swap(nums[l], nums[r]); l; r--; } } void rotate(vectorint nums, int k) { int n nums.size(); if (n 0) return; k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); }写完还要坚持自查四个边界n0、n1、k0、kn。这四个case如果不单独想很容易在某些写法里直接崩掉或者白白多跑一遍循环。2.4 链表题判断单链表是否有环并找到入口这道题在那套卷子里属于“看着简单但暗藏数学推导”的典型。题干分两问第一问判断单链表有没有环第二问如果有找到环的入口节点。第一问的标准做法是快慢指针slow每次走一步fast每次走两步。如果链表无环fast会先到达null如果有环两者必然在环里相遇。为什么slow走一步、fast走两步就一定能相遇可以这么想进入环之后fast每次比slow多走一步相当于fast在逐步追赶slow而且环是封闭的所以哪怕一开始相距很远也一定能追上。如果fast每次走三步反而可能跳过slow造成永远不相遇所以两步是最稳妥的。第二问找环入口需要一点数学推导。设链表头到环入口的距离为a环入口到第一次相遇点的距离为b环的周长为c。相遇时slow走了a bfast走了a b mcm为fast在环内多绕的圈数。因为fast走的距离是slow的两倍2(a b) a b mc a b mc a mc - b也就是说从相遇点继续走mc - b步能回到环入口。而从头节点到环入口正好是a步。所以做法是相遇后把一个指针放回头节点另一个留在相遇点然后两个指针每次都走一步再次相遇的位置就是环入口。C核心代码ListNode* detectCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) break; } if (!fast || !fast-next) return nullptr; slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }这段代码里有个小坑while (fast fast-next)这个条件必须同时判断fast和fast-next否则在无环链表上fast-next为空时访问fast-next-next会直接报错。另外第二段循环开始前要单独判断fast是否真的在环里遇到了slow不能直接默认有环。在笔试现场这类题如果能一步写对会给你后面做大题留出很多时间。我当时在这题上浪费了大概十分钟在推数学关系后来复盘时发现其实只要记住结论相遇点放一个指针、头节点放一个指针同步走相遇处就是入口完全够用了。2.5 哈希题冲突处理与负载因子的权衡选择题里有一道关于哈希表冲突处理的题具体选项涉及线性探测、二次探测、链地址法。题目本身不难但能看出出题人希望你分清楚各种处理方式在什么场景下更优。拉链法链地址法就是把哈希到同一位置的元素用链表串起来。它的优点是冲突再多也能工作删除元素方便适合不知道数据量上限的场景。缺点是链表节点需要额外存储指针对缓存不友好。开放寻址法线性探测、二次探测是在哈希表内部找空位。它的优点是不需要额外指针数据连续存放缓存命中率高。缺点是删除麻烦而且当表快满的时候性能急剧下降。这里有个关键概念叫负载因子公式是alpha 已存储元素数 / 哈希表长度。当alpha越接近1冲突概率越高插入和查找的代价会爆炸式上升。我记得一个比较直观的类比拉链法就像小区里的快递柜每个柜子下面挂了一个快递袋东西多了就挂成一个串开放寻址法就像停车场如果预约的车位满了你就在附近找下一个空位。停车场停得越满找位子越费劲这就是负载因子升高带来的性能劣化。做题时还遇到过一个手算题表长10哈希函数是key % 10按顺序插入 12、22、33、44用线性探测画最终存储位置。12放2号位22先看2号位被占看3号位空放3号位33放3号位被占看4号位44放4号位被占看5号位。这种题千万别靠背拿笔按规则一步一步推就行。对于工程实现更常见的经验值是负载因子超过0.75就该扩容。这个值在Java的HashMap里是默认阈值也是空间和时间权衡的常见选择。笔试如果问“为什么是0.75”可以答过小浪费空间过大冲突概率显著上升0.75是一个经验上的平衡点。2.6 操作系统题进程与线程的底层差异操作系统那道题问的是进程和线程的区别选项中混杂了“进程之间不能通信”“线程拥有独立地址空间”“线程是CPU调度的基本单位”这些说法。正确答案是线程是CPU调度的基本单位进程是资源分配的基本单位。这个知识点本身不难但有几个容易混淆的地方要理清楚。进程拥有独立的地址空间所以一个进程崩溃通常不会直接影响另一个进程。线程共享所属进程的地址空间和资源所以多线程写同一个全局变量必须加锁。每个线程有自己的栈、寄存器和程序计数器但堆和全局数据区是共享的。当时有个选项是“线程之间切换比进程切换开销小”这个正确。原因是进程切换需要切换地址空间、刷新TLB而线程切换只换栈和寄存器。但如果你答成“线程切换不需要内核参与”就错了——用户态线程切换确实可以不走内核但操作系统级线程切换还是要经过内核的。还有一个扩展点现场如果一个进程fork出一个子进程子进程和父进程共享代码段但数据段做写时复制。这个知识点也常和线程问题放在一起考。写时复制的意思是fork之后不会立刻复制整个地址空间只有某个进程真的去写某个页面时内核才为它单独复制一份。这是Linux性能优化的关键。我建议学习时别死背概念用场景去记开多个进程做并发好处是隔离性好、一个挂了不连累其他坏处是内存开销大、通信麻烦。开多个线程做并发好处是共享数据方便、创建快坏处是没隔离、一个线程写坏内存可能让整个进程崩溃。这就是为什么Chrome要开多进程而不是多线程的原因。2.7 系统设计题短URL服务的完整链路整套卷子分最高的题是一道系统设计题设计一个短URL服务用户输入一个长链接生成一个短链接访问短链接时能跳转到原链接。要求说明存储方案、短码生成方式、跳转状态码。这道题没有标准答案但你的回答必须覆盖一条完整链路。我从考场上总结出四个必答点。第一个必答点是短码的生成方式。常见方案是用一个发号器生成递增的数字ID然后把这个数字ID转成62进制字符串大小写字母加数字共62个字符6位短码容量大约有568亿足够用。比如ID12345Base62编码后就是dnh这样的短串。这个方案的好处是不会有哈希冲突因为ID本身是唯一的。第二个必答点是存储设计。短码到长URL的映射自然存在数据库里。为了高并发前面加一层Redis缓存。如果缓存没命中再查数据库然后回填缓存。这里要说明冷热数据策略最近生成的短链大概率会被频繁访问老数据可以逐步淘汰。第三个必答点是跳转状态码的选择。需要返回302还是301很多面试者会在这里丢分。301代表永久重定向浏览器会缓存跳转结果后续访问不再请求短URL服务好处是服务端压力小坏处是你无法统计真实点击量。302代表临时重定向每次访问都会先请求短URL服务再跳转能精确统计点击次数但压力更大。百度这种有统计诉求的服务通常用302。第四个必答点是高并发下的发号器优化。如果每次生成短链都访问一次数据库拿自增ID数据库会成为瓶颈。工程上常用号段模式发号器一次性从数据库取出一段ID比如1000到1999然后在内存里发完这段再取下一段。这样数据库请求量降低为原来的千分之一。这其实就是美团的Leaf号段思想2016年那会儿已经有很多公司这么用了。这道题让我意识到笔试里的设计题不是考你架构能力有多强而是考你有没有把一条链路上的关键环节都想清楚。哪怕方案朴素只要把生成、存储、缓存、跳转、计数讲完整分数就不会低。2.8 思维题烧绳子计时的反向操作附加题考了一道经典的思维题两根质地不均匀的绳子每根从一头点燃到烧完都正好需要60分钟问怎么用这两根绳子测出45分钟。先说结论第一根绳子点一头第二根绳子同时点两头。第二根绳子烧完时是30分钟此时立刻把第一根绳子的另一头点燃。第一根绳子烧完还需要15分钟所以从开始到第一根绳子烧完总共45分钟。原理解释每根绳子虽然不均匀但燃烧总时长是固定的。从两头同时点燃燃烧速度翻倍所以第二根绳子在30分钟时烧完。此时第一根绳子已经烧了30分钟剩下部分如果从两头同时烧就再花15分钟烧完。把两个时间拼接起来就是45分钟。这道题考的不是数学而是“同时利用多个约束条件组合出新的结论”。很多同学看到绳子就只想到“一根一根烧”没想到可以把两根绳子的燃烧过程并联起来。做这类题时你脑子里要有一个工具箱里面有“两头同时烧”和“多根绳子并联”这两种操作组合它们就能得出新方案。对于研发来说这种思维方式的映射是有时候一个软硬件功能没法直接实现但把两个已有的约束组合一下就能得到新的解。比如倒计时器的精度不够就用两个精度更差的计时器互相校准。3. 实战推演从读题到提交的完整思考流程3.1 一道二叉树编程题的现场复盘那套卷子的最后一道编程题是给定一棵二叉树和其中两个节点p和q找出它们的最近公共祖先LCA。我拿这道题作为例子完整复盘一遍我当时从读题到写代码的全流程。我的第一反应是递归。二叉树问题递归天然合适因为每个子树就是原问题的子问题。但难点在于递归函数返回什么什么时候能确定答案在纸上画了一棵示例树模拟了几分钟之后我确定了一个思路定义一个辅助函数f(root, p, q)它返回的不一定是LCA也可能是“找到了p或q”。具体规则是如果root为空返回null。如果root等于p或等于q返回root。递归查找左子树和右子树。如果左右子树都返回非空说明p和q分别位于root的两侧root就是LCA返回root。如果只有一侧返回非空说明两个节点都在同一边返回该非空结果。这个思路本质是一个后序遍历先搜索左右子树再处理当前节点。只有当左右子树都“报告”找到了目标节点时当前节点才能被确认为LCA。边界情况在写函数前就要想清楚p和q的父子关系如果p是q的祖先遍历到p时就应该直接返回pp或q不存在于树中这题题干通常保证都存在但生产代码里要单独处理空树。3.2 完整代码与自查清单下面是最终提交版本的代码TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root nullptr) return nullptr; if (root p || root q) return root; TreeNode* left lowestCommonAncestor(root-left, p, q); TreeNode* right lowestCommonAncestor(root-right, p, q); if (left right) return root; return left ? left : right; }写完代码后我按这个清单自查了一遍空树返回null没有崩溃风险。如果p或q不存在这个函数会返回另一个存在的节点或者null但这种场景在题干里是不存在的所以不扣分。如果p是q的祖先遍历到p时直接返回p不会误判。时间复杂度O(n)因为每个节点最多访问一次空间复杂度O(h)h为树高是递归调用栈消耗最坏情况hn。这道题还有几个面试追问值得提前想好。如果二叉树换成BST可以优化到O(h)根据p和q的值与root比较如果都比root小走左子树都比root大走右子树否则root就是LCA。如果节点里有父指针可以先把一个节点的所有祖先存到哈希集合然后从另一个节点往上走遇到集合里的第一个节点就是LCA。这几个变体在笔试复盘中一并准备性价比很高。3.3 这道题背后的工程映射做LCA这道题时我就在想现实中哪里会用得到后来做分布式系统时看到ZooKeeper选举、分布式事务协调、以及系统依赖分析都会涉及类似“在树状结构里找最近共同祖先”的问题。比如一次接口调用链路涉及多个服务这些服务分布在不同的调用树上要定位故障源头就需要找到它们共同依赖的那个服务节点。虽然不会有人拿二叉树代码直接上生产但“在树状结构里定位关键节点”的思维是通用的。所以别把笔试当考试它更像一个让你提前接触工程问题的窗口。做一道LCA顺带把BST优化、父指针优化、分布式调用链分析一起想明白比刷三遍题有用得多。4. 高频失分点与备考建议4.1 失分点速查表我复盘自己和身边同学的错误整理了一张高频失分表备考时按这个查漏补缺非常高效。题目类型典型失分点正确做法结构体对齐忘记中间和尾部padding按对齐数逐偏移画内存布局字符串处理漏掉空串、单字符边界双指针前先判空再处理过滤数组循环移动忘记k%n反转边界写错先用k1和kn-1手动验证链表判环未判断fast-next空指针while条件写成 fast fast-next哈希冲突只会背概念不会手算用具体序列在草稿纸上推一遍进程线程混淆“资源分配”与“调度”记“进程是资源线程是调度”短URL设计只说生成方式不说存储和跳转讲完整链路发号、存储、缓存、302二叉树LCA递归出口写错、p/q不存在未处理先列边界再写代码这张表的价值在于它把“我大概会”和“我能一次做对”区分开了。笔试的残酷之处就是只看结果平时练习时就要把这个表当成检查清单每一类都做到能直接默写。4.2 考前一个月的练习策略如果你离校招笔试还有一个月左右我建议按三周来规划。第一周用来过基础细节。C/C的sizeof、指针、内存对齐、位运算操作系统里的进程调度、死锁、虚拟内存网络的TCP握手、HTTP状态码。这些东西不需要刷题拿一本面试基础题集一天过两章把概念用自己的话讲清楚。第二周用来刷算法。每天手写两到三道题题目来源用LeetCode的hot 100就好。关键是手写不是看着题解敲一遍。我认识很多同学在IDE里写得飞起一上笔试平台就各种编译错误就是因为平时依赖自动补全和调试器。手写能逼你把语法和边界都刻在脑子里。第三周用来做整套模拟。找一套没做过的题严格按照笔试时长、在线编译器来走一遍。中间不查资料、不暂停、不调调试器。模拟时注意观察自己的时间分配哪类题卡壳超过20分钟果断跳过别让一道题毁掉整张卷子。4.3 临场做题节奏和心态临场发挥这件事说玄也玄说实在也实在。我的经验是拿到卷子先不急着动笔花两分钟把整张卷子扫一遍。标出哪些是“一眼会”哪些是“需要推一推”哪些是“完全没思路”。做题顺序按“一眼会”到“需要推一推”来完全没思路的放最后别一上来就死磕。每道题给自己设一个时间上限选择题不超过5分钟编程题不超过25分钟。超过上限先跳过等做完后面题目再回来看。笔试考的是总分不是单题完美时间分配才是决定总分的关键。遇到不会的题不要空着。选择题靠排除法也能提高正确率编程题就算写不出最优解能写一个暴力解法也能拿部分分数。系统设计题只要把链路讲清楚哪怕没说高可用也能拿到一大半分数。答题最忌讳的是留白。心态上记住一件事百度这类公司的笔试本质是筛选基础扎实的候选人不是筛选天才。它不要求你每道题都会但要求你会的基础题保证全对。大部分人的分数差距不是拉在最后那道难题上而是拉在结构体对齐、边界处理这些细节上这些恰恰是最容易通过复盘和训练补上的。我之前带过的学弟准备秋招把这类题从头到尾做了一遍复盘每次错题都记到表里考前一周只复习这张表最后笔试成绩比自己每天盲目刷题一个月要高不少。道理很简单盲目刷题的增量知识是散的复盘错题的增量知识是精准的。