百度2013校招笔试题精讲：TCP、B+树与一致性哈希

1. 先看清这套卷子到底考什么这份“百度2013研发工程师笔试卷B”我记得很清楚是我当年校招季刷到的一套印象很深的卷子。十多年过去题目本身说不上多新但回头看会发现百度这类老牌互联网公司的笔试卷出题思路和现在满屏的 LeetCode 题海完全不是一个路数——它更看重基础功、边界意识和工程思维。你刷三五十道“高频题”背来的结论在这张卷子上往往不好使因为它考的是你“有没有真正理解这几件事”。先说结论这套卷子适合三类人。一类是正在准备大厂校招的应届生拿来查漏补缺一类是工作两三年想回头补基础的后端/客户端开发尤其是 C/C 方向还有一类是面试官本人看看十年前大厂筛选人的标准对设计今天的笔试题也有参考价值。整套卷子的题型分布大致是基础简答题C/C、操作系统、网络、数据库、算法编程题、系统设计题。没有太多偏题怪题但每道题都能往深里挖。下面我按题型逐块拆把每道题的考点、答题思路和容易丢分的地方都讲一遍。1.1 卷面结构回顾我记得这套卷子的大题量不小要在两小时内写完时间其实挺紧的。基础题部分是若干道简答覆盖了 TCP 三次握手、进程与线程的区别、static 关键字的作用、指针与引用的区别这类老生常谈。算法题部分有字符串全排列、最大连续子序列和、链表判环这类典型题。设计题部分更偏向实际的系统设计比如缓存系统的设计、一致性哈希的实现思路。为什么这个结构今天看起来仍然值得刷因为它对应了一个研发工程师最核心的三种能力基础理解力、代码实现力、系统架构力。现在有些笔试卷过度偏向算法竞赛题反而把基础题压缩得很厉害导致招进来的人刷题很厉害但问他“static 修饰函数是什么意思”却答不清楚。2013年这套卷子没有走那个极端。1.2 出题逻辑为什么这些考点能成为经典我后来自己也参与过出题才慢慢理解这套卷子的出题逻辑。它其实是在用最低成本筛选“真正写过代码、真正读过书”的人。比如考 TCP 三次握手不是要你背状态名而是想通过“为什么是三次不是两次”这种追问筛掉只会背不会想的人。考 static是想知道你对 C/C 的存储期、作用域、链接属性有没有体系化认知。所以刷这套卷子不能只求“会做”要追问每一步背后的原理。这也是我这篇复盘最想强调的不要用背题的姿势刷这套题要用“给自己讲明白”的姿势刷。2. 基础题逐题精讲这些“送分题”其实全是深坑基础题看起来简单但恰恰是拉开差距的地方。因为大部分人都能写两句但很少有人能写到点子上更少有人能写出“面试官想听到的那个层次”。2.1 TCP 连接断开与进程线程别只背状态名TCP 三次握手和四次挥手几乎是必考题。三次握手的核心一句话说清楚客户端和服务端各自要确认“我能发、你能收你能发、我能收”。为什么不能是两次因为两次握手只能让客户端确认服务端收到自己的 SYN服务端却无法确认客户端收到了自己的 SYN-ACK。换句话说服务端无法确认客户端的接收能力。四次挥手为什么是四次因为 TCP 是全双工的每一方向的关闭都需要单独确认。主动关闭方发 FIN被动关闭方先回 ACK表示“我知道了”等自己数据发完再发 FIN主动方再回 ACK。很多初学者容易漏掉“被动关闭方可能要等数据发完才能发 FIN”这一步这就是 TIME_WAIT 出现的根本原因之一。当时这道题的追问经常是为什么主动关闭方要进入 TIME_WAIT 并等待 2MSL两个原因一是保证被动关闭方收到最后的 ACK如果 ACK 丢了被动方会重发 FIN主动方还能响应二是让本次连接中所有迟到的报文在网络中自然消失避免污染下一个使用相同四元组的连接。这个点你答出来这道题基本就是满分。进程和线程的对比也有固定答法进程是资源分配的基本单位线程是 CPU 调度的基本单位同一进程的线程共享地址空间、文件描述符等资源但进程之间地址空间互相隔离切换线程的开销小于切换进程因为不需要切换页表。但要注意面试官经常追问“线程切换具体省在哪”答案不只是“不用切页表”还包括缓存TLB不用失效、地址空间相关的数据结构不用切换。你能答到这一层说明真理解。2.2 指针、引用与 staticC/C 的基本功分水岭这套卷子对 C/C 的考察非常细。指针和引用的区别标准答案是引用是对象的别名必须在定义时初始化不能重新绑定指针是存放地址的变量可以重新赋值可以为空。但更关键的对比在底层引用在汇编层面通常也是用指针实现的所以“引用一定比指针快”是伪命题引用主要价值在语法层面的安全约束。static 这个关键字可以一条线串起来讲修饰局部变量时变量存储期从栈变为静态存储区只初始化一次生命周期持续到程序结束修饰全局变量/函数时限制其作用域只在当前编译单元内也就是外部链接变为内部链接修饰类成员变量时所有对象共享一份且必须在类外定义修饰类成员函数时成员函数不依赖具体对象没有 this 指针只能访问静态成员。我建议复习时自己画一张表把“变量类型 是否 static 存储位置 作用域 生命周期”列成矩阵比单纯背结论有用得多。当年我就是在这一题上丢过分因为只写了“static 变量只初始化一次”完全没提链接属性面试官后来在电话面里又追问我才补上。2.3 数据库索引与 B 树为什么不是哈希也不是二叉树数据库索引题也是这套卷子的重头戏。常见的考法是问“InnoDB 为什么用 B 树做索引”。标准答案分几层第一B 树是多路平衡查找树矮胖高度低。千万级数据量下三层 B 树就能放下所有索引和叶子节点意味着查询最多三次磁盘 I/O。二叉树高度太高每次查找都伴随多次磁盘寻道不行。第二B 树的非叶子节点只存键不存值每个磁盘页能容纳更多键进一步降低树高。相比之下B 树的非叶子节点也存数据扇出更小树更高。第三B 树的叶子节点通过链表相连天然支持范围查询和排序。对数据库来说SELECT 区间查询是高频操作哈希索引做不到范围查询B 树可以中序遍历叶子链表情轻松搞定。哈希索引的问题在于只支持等值查询而且无法利用索引排序。所以即便是内存型数据库如 Redis的字典结构也解决不了范围查询的痛点Redis 还得额外提供跳表。这道题想拿高分要把“磁盘 I/O 次数”“范围查询”“聚簇索引”三个关键词全部覆盖。3. 算法编程题从递归到海量数据的完整推演算法题是这套卷子的重头篇幅也最大。我挑三道最有代表性的题展开讲。3.1 字符串全排列递归、回溯与去重题目要求输入一个字符串打印出该字符串中字符的所有排列。例如输入 abc输出 abc、acb、bac、bca、cab、cba。这题经典的解法是递归 回溯。思路是固定第一个字符然后对剩余字符做全排列每次递归前交换当前字符到第一位递归完再交换回来。参考代码如下#include iostream #include string #include algorithm using namespace std; void permute(string s, int start, int end) { if (start end) { cout s endl; return; } for (int i start; i end; i) { // 同一个字符重复出现时跳过避免重复排列 bool duplicated false; for (int j start; j i; j) { if (s[j] s[i]) { duplicated true; break; } } if (duplicated) continue; swap(s[start], s[i]); permute(s, start 1, end); swap(s[start], s[i]); // 回溯 } } int main() { string s abc; permute(s, 0, s.length() - 1); return 0; }这里最容易错的点有两个。第一忘记回溯。如果没有第二次 swap字符串会在递归过程中被改乱后续排列全错。第二重复字符没有去重。如果输入是 aab不去重会输出 6 个排列其中 3 个是重复的。去重的技巧不是用哈希表去重整个结果集那样内存浪费大而是在每层递归中判断当前要交换的字符是否在当前范围内出现过如果出现过就跳过。上面代码里的内层 for 循环就是干这个的。复杂度上不重复字符的全排列数量是 n!每生成一个排列需要 O(n) 时间输出所以总复杂度 O(n * n!)。空间复杂度主要是递归栈深度 O(n)。这道题在当年是“必考热门”因为数学系出题人很喜欢这类组合数学题。后来我参加面试时还遇到过变种给一个字符串输出它的第 k 个排列或者输出所有排列中字典序排第几。本质都是全排列但需要引入康托展开之类的手段。建议刷题时把这几个变种一起看了。3.2 最大连续子序列和经典但必须掌握状态定义题目给定一个整数数组求所有连续子序列里和最大的那个输出最大和。例如 [-2, 1, -3, 4, -1, 2, 1, -5, 4]最大和的连续子序列是 [4, -1, 2, 1]和为 6。这题有两个层次。第一层次用动态规划核心是定义状态 dp[i] 表示以第 i 个元素结尾的最大连续子序列和。转移方程dp[i] max(nums[i], dp[i-1] nums[i])然后整个数组的最大和就是所有 dp[i] 里的最大值。空间上可以优化成 O(1)因为 dp[i] 只依赖 dp[i-1]int maxSubArray(vectorint nums) { int cur 0, best INT_MIN; for (int x : nums) { cur max(x, cur x); best max(best, cur); } return best; }第二层次也是面试官经常追问的——为什么这个状态定义是对的关键在于“以 i 结尾”这个限制。它强制子序列包含 nums[i]所以递推时要么把 nums[i] 接到前面的序列后面要么从 nums[i] 重新开始。这个约束让状态转移简单清晰不重不漏。这道题还有一个容易忽略的点如果数组里全是负数最大子序列应该是最大的那个负数而不是 0。所以初始化 best 为 INT_MIN不能初始化为 0。很多人在这个位置翻车因为只看示例全是正负数混合没考虑到全负的情况。3.3 链表判环与 Top K边界条件里的魔鬼链表判环这道题在笔试卷里出现频率很高。思路是快慢指针快指针每次走两步慢指针每次走一步如果存在环二者必然在环内相遇如果无环快指针会先走到 NULL。bool hasCycle(ListNode *head) { if (!head || !head-next) return false; ListNode *slow head, *fast head-next; while (slow ! fast) { if (!fast || !fast-next) return false; slow slow-next; fast fast-next-next; } return true; }实现里的坑几乎都在空指针上快指针一次走两步所以要保证 fast 和 fast-next 都不为空空链表和单节点链表要提前处理。这题代码量很小但每年都有大量人因为空指针异常被卡。Top K 问题当年也出现过变种考察“海量数据中取最大的 K 个数”。最优解是维护一个大小为 K 的小根堆遍历数据时如果当前元素比堆顶大就弹出堆顶并插入当前元素。这样堆里始终保留当前已遍历数据中最大的 K 个。复杂度 O(n log K)当 K 远小于 n 时比全排序的 O(n log n) 好得多。但要注意这道题在笔试里不能只写思路要能给出可运行的代码。堆可以用 priority_queue 实现C 默认是大根堆要取 K 个最大的数得用 greater 比较器。vectorint topK(vectorint nums, int k) { if (k 0) return {}; priority_queueint, vectorint, greaterint pq; for (int x : nums) { if (pq.size() k) { pq.push(x); } else if (x pq.top()) { pq.pop(); pq.push(x); } } vectorint res; while (!pq.empty()) { res.push_back(pq.top()); pq.pop(); } return res; }如果 K 非常大接近 n那堆方案反而未必最优直接用快速选择算法平均 O(n) 更好。但我个人建议面试时先讲堆方案再说“当 K 接近 n 时可以用快速选择”这样既覆盖一般场景又展示深度。4. 系统设计题考的是工程素养不是背架构图2013年的系统设计题比现在温和一些但思路已经成型。核心考两类缓存设计、短链/存储类系统设计。我挑两个最有代表性的详细讲。4.1 一致性哈希从取模到虚拟节点的演进题目通常是“设计一个分布式缓存系统如何选择存储节点”。最朴素的做法是哈希取模key 的哈希值对节点数取模选择节点。但问题很明显——节点增减时绝大多数 key 会映射到新节点缓存大面积失效对后端造成“缓存雪崩”。一致性哈希的经典思路是把哈希空间看成一个环0 到 2^32 - 1把每个服务器节点哈希后放到环上查询某个 key 时计算其哈希值沿环顺时针找到第一个服务器节点即为存储位置。节点增减只影响该节点附近一段区间内的 key不影响全局缓存。但一致性哈希有个均匀性问题节点少时哈希环上节点分布可能极不均匀导致部分服务器压力过大。解决方案是引入虚拟节点——每个物理节点对应环上多个虚拟节点让节点在环上分布更均匀。扩容时新节点的压力主要来自附近的少数节点整体影响小很多。虚拟节点的数量怎么定经验值一般是每个物理节点 100~200 个虚拟节点具体取决于总数据量和负载均衡要求。但不建议拍脑袋可以压测后用数据说话统计各物理节点的 key 数量的标准差标准差小说明均衡。我当时在卷子上写的是“一致性哈希 虚拟节点”方案并把每次增删节点影响多少个 key 的估算写清楚。面试官后来告诉我这道题拿高分的重点在于第一点破取模方案在动态扩缩容时的致命缺陷第二主动提到虚拟节点第三说出均匀性评估方式。4.2 短链接系统一次完整的设计推演这套卷子里的系统设计题我印象较深的是“设计一个短链接系统”。它的核心难点不是后端存储而是“如何把长链接转成短链接并且避免撞车”。短链接的生成可以用发号器Snowflake 风格生成一个自增 ID然后对 ID 进行 Base62 编码得到短链接中的标识符。比如 62 进制用 0-9、a-z、A-Z 这 62 个字符6 位字符串能表达 62^6 ≈ 568 亿个链接完全够用。用户访问短链接时根据标识符解码回 ID再查表取出长链接执行 302 跳转。这个方案比较符合实际工程因为用哈希算法生成的短串虽然短但会存在碰撞问题需要处理冲突而发号器天然自增不碰撞还方便做计数统计。要注意的点是发号器不能有单点故障通常用 Redis 的 INCR 命令或者数据库号段模式。设计题答得好不好往往不在架构多华丽而在有没有考虑到边缘场景短链接过期怎么办有人恶意刷接口怎么办跳转用 301 还是 302我当时答了“302 用于短链接更合适”因为 302 每次访问都会请求短链服务方便统计点击量而 301 会被浏览器和 CDN 缓存统计数据会严重偏少。这个细节让面试官明显眼前一亮。5. 备考踩坑总结复盘这套卷子时最容易被忽略的事最后这部分不是题目解析而是我反复刷这套卷子之后总结出的实战经验包括时间分配、边界条件和代码规范。5.1 时间分配基础题不要恋战算法题要留足这套卷子两小时我的建议是基础简答题控制在 40 分钟内因为每道题不需要写论文写清楚要点即可。算法编程题留 60 分钟两道大题每题 25 分钟剩下 5 分钟检查。最后系统设计题留 20 分钟。当年我自己犯过的错是基础题写太多生怕面试官看不出自己懂结果算法题最后草草收场。后来反思发现基础题答到“要点齐全 一个亮点”就够了比如 TCP 三次握手你只要主动补一句“两次无法让服务端确认客户端接收能力”这题已经满分多写反而挤压时间。5.2 边界条件全负数组、空链表、单节点、重复字符我整理了这套卷子里真正容易丢分的边界条件题目类型常被忽略的边界条件典型后果最大连续子序列和数组全为负数返回 0 而非最大负数链表判环空链表、单节点链表空指针异常字符串全排列输入含重复字符输出重复排列Top KK 大于数组长度越界或堆溢出一致性哈希只有一个物理节点所有 key 打到一个节点准备笔试时我建议每写完一道算法题先用这组边界条件过一遍。花不了两分钟但能救回不少分。现在的在线评测环境不会给你“部分正确”的机会只要一个用例不过整道题可能就判错。5.3 代码规范卷面分是真实存在的笔试代码虽然不需要编译运行但阅卷人是有主观判断的。我在实际工作中也帮公司筛过简历和笔试卷说实话看到变量名是 a、b、c 的卷子第一印象就差很多。哪怕算法思路再对出现明显语法错误也会很减分。几个我自己的习惯变量名用有意义的名字比如 curSum、bestSum、fast、slow循环里不要随便用 i、j 多层嵌套还不注释递归/回溯函数要给注释说明参数含义写完代码后在关键分支上补一行注释比如“// 回溯恢复现场”。这些细节不影响正确性但大大提升可读性而可读性在人工阅卷时就是隐形加分项。再有一个经验写完代码一定手动走一遍小例子。在线笔试环境可能没有编译器给你调试所以自己要在草稿纸上模拟几个用例尤其是自己代码里最容易出错的那一行。比如全排列里的回溯 swap你亲手走一遍 abc 的排列过程就永远不会漏掉第二次 swap。6. 这套卷子刷完我的体会这套 2013 年的笔试卷放在今天的招聘环境里依然不过时。它没有考任何花哨的框架、中间件、云计算考的恰恰是每个研发工程师天天要用、但越来越多人说不清楚的基本功。我后来在公司带新人时也偶尔会把这份卷子的题目拿出来做摸底测试——效果出奇地好几分钟就能看出一个人是“真懂”还是“背过”。如果你正在准备面试我的建议是不要只刷 LeetCode 高频题至少找一两套老牌公司的完整笔试卷计时、手写、完整复盘一遍。重点不是题目本身而是它逼着你把基础概念串起来。比如 static 这道题会串起编译原理、存储管理、面向对象三门课的知识。这样的题目才是真正有价值的面试题。