百度研发岗笔试复盘：HashMap、TCP与算法设计题解析

2015年春招，我和一大群应届生一起坐在深圳的笔试教室里，面前是一张“百度研发工程师”的试卷。那会儿手机还不能拍照，草稿纸是发的一张白纸，答题时间两个半小时，题量不小，周围的翻卷声从第一页开始就没停过。考完出来，不少人在讨论“HashMap底层到底是数组还是链表”“TCP挥手为什么要等2MSL”“最后那道设计题到底要不要写代码”，可见这张卷子的覆盖面，基本上是“基础功底 + 算法思维 + 工程常识”三件套全考。作为过来人，我后来对照当年的记忆和网上能搜到的零散题目，把整套卷子的考点、答题思路和容易踩的坑重新梳理了一遍。如果你是准备大厂研发岗笔试的，这篇可以直接当复习提纲用。

1. 深圳站笔试卷的总体印象：六成基础、三成算法、一成陷阱

先说结论：百度的笔试风格和某些喜欢出“脑筋急转弯”的公司不一样，它更看重你是否具备扎实的计算机基础，以及能不能把基础概念用到真实场景里。2015年深圳站的卷子基本分为几块：操作系统、计算机网络、C++/Linux、数据结构与算法、还有一两道开放设计题。

1.1 试卷结构复盘（以当年考生记忆综合）

这个结构说明一件事：算法不是唯一的胜负手。基础的网络、OS和语言细节占了一半以上，而很多人恰恰在这些题上丢分。原因不是不会，而是答得太“教科书”。比如考“进程和线程的区别”，如果你只写“进程是资源分配的基本单位，线程是调度的基本单位”，可能只拿一半分。面试官想看到的是你对“为什么这样设计”的理解，以及能否结合百度真实业务（搜索引擎、广告系统、大规模分布式服务）去说明。

1.2 为什么面试官偏爱这类题

百度以搜索起家，后端的核心诉求是高并发、低延迟、海量数据。一套试卷里出现大量HashMap、TCP、Linux命令，不是随机拼凑，而是这些知识点直接对应后端研发的日常工作。

举个实际例子：搜索系统的每一条查询都要经过倒排索引、相关性计算、结果排序，每一步都涉及海量数据的存取和并发控制。如果你连HashMap扩容时为什么会卡顿、TCP连接为什么要维持、Linux下如何定位CPU飙高都说不清楚，入职后面对线上告警会非常吃力。所以这套卷子本质上不是“考你会背多少”，而是“考你遇到问题时的第一反应是不是工程化的”。

2. 高频必稳送分点：HashMap、进程线程、TCP挥手

这三类题几乎是那两年百度笔试的标配，2025年回头看，依然是所有大厂后端笔试的高频题。它们难吗？不难。但很多人拿不到满分，是因为只答了“是什么”，没有答“为什么”。

2.1 HashMap实现原理与扩容推导

2015年Java圈的HashMap还在1.7和1.8的过渡期，但笔试题里HashMap基本是必考。最常见的问法是：“HashMap底层数据结构是什么？如何解决哈希冲突？扩容过程是怎样的？”

标准答题结构应该是这样：

• 底层是数组加链表，Java 1.8之后在链表长度大于等于8且数组长度大于等于64时，链表会转成红黑树。
• 通过key.hashCode()计算哈希，再对数组长度取模或与运算确认桶位置。
• 当元素个数超过threshold = capacity * loadFactor时触发扩容，默认负载因子0.75，默认初始容量16。
• 扩容时新建一个容量为原来两倍的数组，然后把旧数据重新哈希迁移过去。

如果只答到这里，属于“及格”。想拿高分，需要补充一个推导：为什么负载因子是0.75？

这个0.75是时间开销和空间开销的折中。负载因子太高，比如1.0，意味着桶快塞满才扩容，哈希冲突会大幅增加，链表变长，查询从O(1)退化成O(n)；负载因子太低，比如0.5，空间浪费严重。0.75是大量测试下的经验值，也是泊松分布下链表长度达到8的概率极低的一个关键前提。

参考答案中的计算逻辑可以这样写：假设哈希函数足够均匀，当负载因子为0.75时，单个桶内链表长度达到8的概率约为千万分之六。这个概率是用泊松分布近似计算的，面试官看到这个数字，基本就知道你是真的理解HashMap，而不是背过八股。

2.2 进程与线程的区别，必须带场景说

这道题几乎每场笔试都有，但要答出区分度，不能只背定义。建议用一张对比表加一个场景把话说透。

笔答题可以先给定义，然后立刻落到场景。例如：“搜索引擎的索引更新服务，如果按进程隔离，不同索引分片可以独立升级和重启，故障域更小；而一个查询请求内部的多个处理阶段用线程池并发执行，能降低延迟，因为线程创建的代价远小于进程fork。”

不要小看最后这句话。它展示了你对“为什么需要线程”的工程理解，而不是只会默写概念。

2.3 TCP建立连接与挥手：画出状态迁移，讲清TIME_WAIT

网络题里，TCP三次握手和四次挥手是绝对重点。我的建议是：答题时一定要画状态图，不要只写文字描述。哪怕笔试是白纸手写，也要画出客户端/服务端的状态迁移。

握手部分要讲清楚：SYN、SYN+ACK、ACK，每一步确认了什么，SYN Flood攻击为什么会利用第一步不完整连接占资源。

挥手部分要重点讲TIME_WAIT。很多人知道主动关闭方要进入TIME_WAIT并等待2MSL，但说不清为什么。标准解释有两点：

• 保证最后一个ACK能到达对方。如果ACK丢了，对方会重发FIN，主动关闭方需要留在这个状态以便重发ACK。
• 让旧连接的报文段在网络中自然消失，避免新连接收到旧连接残留的数据包，造成数据错乱。

网上很多答案只写“等待2MSL”，如果你把这两点原因写全，这道题基本就稳了。

3. 算法题才是分水岭：从暴力到最优解的推导过程

深圳站的算法题不算变态，常见的有链表反转、字符串全排列、海量数据TopK、二分查找变体、数组去重等。但很多人栽在“一上来就闷头写代码”，忽略了题目里“时间复杂度尽可能低”“数据量很大”这类限制条件。

算法题阅卷最看重的是解题思路的推导过程，而不是跑出来的结果。所以我建议，每道算法题都要在正式写代码前，先在草稿纸上写出暴力解，再推导优化。

3.1 海量数据求Top K：堆排序与分治的取舍

题目通常是这样：“10亿个数中找出最大的100个，内存只有1GB，怎么办？”

暴力做法是全部排序，取前100个。但10亿个整数需要约4GB内存，直接排序不现实。正确思路要分几步讲：

1. 如果内存足够，可以用全排序或快速选择，时间复杂度O(n log n)或O(n)。
2. 内存不够时，用大小为K的最小堆。遍历数据时，如果当前元素比堆顶小，直接跳过；如果比堆顶大，弹出堆顶、插入新元素，堆内部调整复杂度O(log K)。
3. 整体时间复杂度O(n log K)，内存只需要O(K)。

这里还需要解释为什么是“最小堆”而不是“最大堆”——因为我们要的是最大的K个数，堆顶必须是当前K个数中的最小值，新元素才有资格和它比较。

如果题目再加一句“数据分布在不同机器上”，就要引出分治思想：每台机器先算本机TopK，再把各机器的TopK汇总，在汇总集合上再做一次堆排序。这个思路对应MapReduce中的局部聚合，面试官会很熟悉。

3.2 字符串全排列与去重：从递归到回溯

这道题当年出现频率很高。题目是“给定一个可能包含重复字符的字符串，输出所有不重复的全排列”。

最稳妥的写法是回溯法，用一个visited数组标记每层是否用过，避免重复选择。对于去重，最直观的做法是使用set或sort，稍微进阶一点是“同一层递归中跳过相同字符”。

这里给一个C++版本的参考答案，笔试时可以直接默写：

#include <string> #include <vector> #include <algorithm> using namespace std; void backtrack(string& s, vector<bool>& visited, string& cur, vector<string>& res) { if (cur.size() == s.size()) { res.push_back(cur); return; } for (int i = 0; i < s.size(); i++) { if (visited[i]) continue; // 去重：同一层递归中，如果当前字符和前一个相同，且前一个没有用过，则跳过 if (i > 0 && s[i] == s[i-1] && !visited[i-1]) continue; visited[i] = true; cur.push_back(s[i]); backtrack(s, visited, cur, res); cur.pop_back(); visited[i] = false; } } vector<string> permuteUnique(string s) { sort(s.begin(), s.end()); vector<string> res; string cur; vector<bool> visited(s.size(), false); backtrack(s, visited, cur, res); return res; }

注意排序是为了让相同字符相邻，这样去重条件才能生效。如果输入规模很小，用set临时去重也不是不行，但复杂度会多一个log因子。这套卷子对性能有要求，能写O(n!)就别写O(n!log n!)。

3.3 链表反转与快慢指针：写代码前先画三张图

链表题在笔试卷里出现率极高。反转链表常见，快慢指针找中间节点或者判断是否有环也常见。

我见过太多人在反转链表时指针指来指去把自己绕晕。建议先画三张图：初始状态、中间状态、结束状态，把prev、cur、next三个指针的位置画清楚，再动手。

迭代版参考代码：

struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }

快慢指针判断链表是否有环也很经典：

bool hasCycle(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; }

写完后，建议在代码末尾标注复杂度：时间复杂度O(n)，空间复杂度O(1)。这是一个很小的习惯，但阅卷时很加分，说明你有成本意识。

4. 最容易丢分的C++与Linux题目：这不是背题，是排查能力

百度后端早年以C++为主，所以C++和Linux相关的题目几乎是必出。别小看这20%的占比，如果算法题没写完，这部分才是拉分的关键。

4.1 宏定义、typedef与内联函数的本质差异

有一道经典题是：“#define和typedef有什么区别？”再进一步会问“内联函数和宏有什么区别？”

第一层答案很简单：

• #define是预处理阶段的文本替换，不做类型检查。
• typedef是给类型起别名，由编译器处理，有类型检查。

第二层答案要说出宏的隐患：

#define SQUARE(x) x * x int a = SQUARE(1 + 2); // 结果是 1 + 2 * 1 + 2 = 5

因为宏只是文本替换，不会自动加括号。而这种坑在笔试里被反复考，就是为了检验你是否真的写过C++，而不是只看过语法。

内联函数和宏的对比：

• 内联函数有类型检查，会进行参数求值，展开是在编译阶段。
• 宏是预处理替换，可能带来副作用，比如参数被多次求值时，++x会被执行多次。

举个例子：

#define MAX(a, b) ((a) > (b) ? (a) : (b)) int x = 1, y = 2; int z = MAX(++x, y); // 宏展开后，x可能被加两次

这种题不用背太多，核心答出“宏是文本替换，函数是类型安全”就够了。

4.2 内存泄漏的定位思路：valgrind与Address Sanitizer

笔试里可能会出现“线上服务内存持续增长，你怎么排查”这类题。这不是让你背工具名，而是考察你的定位思路。

我给一个可以落地的排查路径：

1. 先用top或free看进程内存趋势，确认是不是RSS在持续上涨。
2. 用valgrind --leak-check=full ./server跑一段时间，日志里会提示哪些内存块没有释放。
3. 如果进程已经是生产环境，没法直接挂valgrind，可以改用Address Sanitizer，编译时加-fsanitize=address，运行时报错会直接打印内存泄漏的调用栈。
4. 如果泄漏的是第三方库内部缓存，可能需要通过火焰图或gdb抓取malloc调用栈，定位到热点位置。

笔试时不用把每个工具的具体输出写出来，但要把“先看现象、再定位代码、最后验证”的逻辑讲清楚。面试官真正想看到的，是你遇到线上内存问题时能不能冷静地按链路排查，而不是上来就重启。

4.3 Linux排查命令组合拳：top、strace、gdb、netstat

Linux题目常见的是：“CPU使用率100%，你怎么定位？”我建议把系统性的排查命令写出来，不要只甩一个top。

我的常用组合是：

• top -Hp <pid>：查看进程内哪个线程占用CPU最高。
• perf top或perf record：采集热点函数，看是用户态还是内核态。
• strace -p <pid>：跟踪系统调用，确认是否卡在IO或锁等待。
• gdb attach <pid>：在怀疑卡住的位置看调用栈。

如果是网络异常，则用netstat -anp看连接状态，用ss -s看socket统计，再用tcpdump抓包确认是否丢包。

把命令写全不难，但若能在命令后面加一句“如果CPU占用集中在内核态，优先怀疑系统调用频繁或网络软中断；如果集中在用户态，再看火焰图定位到具体函数”，会显得你确实处理过线上问题。

5. 开放性设计题：答法比答案更重要

百度笔试卷的最后一题通常是一道系统设计或场景题。2015年深圳站出现过短网址服务设计、分布式缓存设计、高并发秒杀等题。这类题没有标准答案，考的是“你是不是一个有大局观的工程师”。

5.1 短网址服务设计：先讲容量，再画请求链路

题目大概是：“设计一个短网址服务，支持每日亿万级访问。”

不要一开始就写代码。应该先估算容量：

• 短网址用62进制编码（大小写字母加数字），6位可以表示62^6约568亿个网址，足够日常使用。
• 每日新增千万级短链，一年约36亿条，用数据库分表存储问题不大。
• 读请求远多于写请求，需要加缓存，比如将热点短链放到Redis。

接着画链路：用户输入长网址 -> 服务端生成唯一ID，转62进制 -> 返回短链；用户访问短链 -> 服务端解析ID -> 查数据库或缓存 -> 302重定向到长网址。

加分项：提到由ID生成算法（雪花算法）保证分布式环境不冲突，以及缓存淘汰使用LRU策略。这样整套设计的完整性立刻就上来了。

5.2 分布式缓存系统：命中率与一致性如何取舍

这道题不一定会和短网址一起出现，也可能会单独考。核心是“缓存与数据库的一致性问题”。

最稳妥的答法是用Cache Aside模式：

• 读请求先查缓存，命中直接返回。
• 缓存未命中，查数据库，然后回填缓存。
• 写请求先更新数据库，再删除缓存。

为什么不直接更新缓存？因为更新缓存的代价可能更高，而且并发写时容易把旧值写回缓存。删除缓存可以规避这个问题，让下一次读请求再回填最新数据。

还要提到缓存穿透、缓存击穿、缓存雪崩三个兄弟：

• 穿透：查询不存在的key，解决办法是布隆过滤器或缓存空值。
• 击穿：一个热点key过期，瞬间大量请求打到数据库，解决办法是互斥锁或逻辑过期。
• 雪崩：大量key同时过期，解决办法是过期时间加随机值。

这段答完，基本覆盖了大型缓存设计的主要考点。

5.3 高并发秒杀系统：限流与防超卖的核心

秒杀题在广东这边的大厂笔试里挺常见。考察点不是你会不会写秒杀页面，而是怎么保证库存不超卖、系统不被打挂。

核心思路：

• 提前把库存加载到Redis，用DECR原子操作扣减库存。DECR返回负数时说明已经没有库存，直接返回失败。
• 用消息队列削峰，把秒杀请求先写到队列，后端异步创建订单。
• 网关层做限流，比如令牌桶算法，控制进入秒杀接口的请求速率。
• 防止用户重复下单，可以用用户ID加商品ID做幂等判断。

如果笔试要求画图，就画“客户端 -> 网关限流 -> 秒杀服务 -> Redis扣库存 -> 消息队列 -> 订单服务”，并标注每条链路上怎么降级。

6. 针对这套卷子的实战复盘建议

这部分是我最想说的。当年我走出考场的最大感受是：题都不算偏，但时间很紧，而且很多题如果只看完题目就动笔，很容易写到一半发现思路错了，草稿纸上全是涂改痕迹。

6.1 时间分配：先拿基础分，再攻算法压轴

我的建议是按三个时间块划分：

不要在“HashMap扩容时链表树化阈值为什么是8”这种细节上纠结太久，写上“泊松分布下概率极低”这层意思就够了，答得太深反而浪费时间。

6.2 我的答题习惯：先写思路再写代码，复杂度标注在末尾

一个非常管用的习惯是：算法题先写两行“思路说明”，再写代码。比如：

思路：使用大小为 K 的最小堆遍历一遍数据。 时间复杂度 O(n log K)，空间复杂度 O(K)。

这样做有两个好处：一是阅卷人不用猜你代码背后的想法；二是如果代码有小bug，思路正确也能拿大部分分数。很多笔试不是机器判卷，而是人工阅，思路清晰非常加分。

6.3 简答题别写散文：用公式、状态图、命令说话

简答题最忌讳长篇大论。面试官一天要改几百份试卷，看到四五行没有要点的文字会很头疼。建议用列表、公式、状态图来组织答案。

比如问TCP挥手，就写：

客户端 FIN_WAIT_1 -> 服务端 CLOSE_WAIT 服务端 FIN_WAIT_2 -> 客户端 WAIT

再配上一句“TIME_WAIT作用：兜底重发ACK + 避免旧报文串扰新连接”。这样信息密度高，又像有经验的工程师在写故障复盘，而不是学生背笔记。

7. 写在后面：这套卷子放到今天还适用什么

距离2015年过去很多年，但这套卷子里的“内核”依然没有过时。HashMap、TCP、进程线程、算法优化、系统设计，今天的后端面试依然在考，只是问法变得更场景化、更深了。比如以前问“HashMap底层结构”，现在会问“如果key是可变对象，HashMap会出什么问题”；以前问“怎么定位CPU高”，现在会直接让你讲一次线上故障排查的完整经历。

我自己在后来带人的过程中，也会不自觉地把候选人和这套卷子的答题思路做对照。那些能拿高分的人，通常不是背题最熟的，而是答每道题时都带着“我为什么这么做”的思考。如果你正在准备类似的笔试，我的建议是：别只刷算法题，把操作系统、网络、Linux和设计题的基础功一起补上，平时写好代码后多问自己一句“这行代码在极端情况下会怎样”。这套卷子里藏着的，其实就是一个后端工程师日常最需要的那几种能力。