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

2015年春招我和一大群应届生一起坐在深圳的笔试教室里面前是一张“百度研发工程师”的试卷。那会儿手机还不能拍照草稿纸是发的一张白纸答题时间两个半小时题量不小周围的翻卷声从第一页开始就没停过。考完出来不少人在讨论“HashMap底层到底是数组还是链表”“TCP挥手为什么要等2MSL”“最后那道设计题到底要不要写代码”可见这张卷子的覆盖面基本上是“基础功底 算法思维 工程常识”三件套全考。作为过来人我后来对照当年的记忆和网上能搜到的零散题目把整套卷子的考点、答题思路和容易踩的坑重新梳理了一遍。如果你是准备大厂研发岗笔试的这篇可以直接当复习提纲用。1. 深圳站笔试卷的总体印象六成基础、三成算法、一成陷阱先说结论百度的笔试风格和某些喜欢出“脑筋急转弯”的公司不一样它更看重你是否具备扎实的计算机基础以及能不能把基础概念用到真实场景里。2015年深圳站的卷子基本分为几块操作系统、计算机网络、C/Linux、数据结构与算法、还有一两道开放设计题。1.1 试卷结构复盘以当年考生记忆综合模块常见题型大致占比我建议的答题优先级操作系统进程线程、内存管理、死锁20%先做计算机网络TCP/UDP、HTTP、DNS、握手挥手20%先做C/Linux宏定义、内存泄漏、gdb/命令20%次之数据结构与算法链表、字符串、海量数据TopK、排序30%留足时间系统设计短网址、缓存、秒杀10%最后这个结构说明一件事算法不是唯一的胜负手。基础的网络、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 进程与线程的区别必须带场景说这道题几乎每场笔试都有但要答出区分度不能只背定义。建议用一张对比表加一个场景把话说透。维度进程线程资源有独立的地址空间、文件描述符、信号处理器共享进程的地址空间和大部分资源调度进程是资源分配单位线程是CPU调度单位同一进程内线程切换开销更小崩溃影响一个进程崩溃一般不影响其他进程一个线程崩溃可能导致整个进程退出通信进程间通信需要借助管道、消息队列、共享内存等线程间通过共享内存通信更简单但需要同步笔答题可以先给定义然后立刻落到场景。例如“搜索引擎的索引更新服务如果按进程隔离不同索引分片可以独立升级和重启故障域更小而一个查询请求内部的多个处理阶段用线程池并发执行能降低延迟因为线程创建的代价远小于进程fork。”不要小看最后这句话。它展示了你对“为什么需要线程”的工程理解而不是只会默写概念。2.3 TCP建立连接与挥手画出状态迁移讲清TIME_WAIT网络题里TCP三次握手和四次挥手是绝对重点。我的建议是答题时一定要画状态图不要只写文字描述。哪怕笔试是白纸手写也要画出客户端/服务端的状态迁移。握手部分要讲清楚SYN、SYNACK、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内存直接排序不现实。正确思路要分几步讲如果内存足够可以用全排序或快速选择时间复杂度O(n log n)或O(n)。内存不够时用大小为K的最小堆。遍历数据时如果当前元素比堆顶小直接跳过如果比堆顶大弹出堆顶、插入新元素堆内部调整复杂度O(log K)。整体时间复杂度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, vectorbool visited, string cur, vectorstring 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; } } vectorstring permuteUnique(string s) { sort(s.begin(), s.end()); vectorstring res; string cur; vectorbool 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笔试里可能会出现“线上服务内存持续增长你怎么排查”这类题。这不是让你背工具名而是考察你的定位思路。我给一个可以落地的排查路径先用top或free看进程内存趋势确认是不是RSS在持续上涨。用valgrind --leak-checkfull ./server跑一段时间日志里会提示哪些内存块没有释放。如果进程已经是生产环境没法直接挂valgrind可以改用Address Sanitizer编译时加-fsanitizeaddress运行时报错会直接打印内存泄漏的调用栈。如果泄漏的是第三方库内部缓存可能需要通过火焰图或gdb抓取malloc调用栈定位到热点位置。笔试时不用把每个工具的具体输出写出来但要把“先看现象、再定位代码、最后验证”的逻辑讲清楚。面试官真正想看到的是你遇到线上内存问题时能不能冷静地按链路排查而不是上来就重启。4.3 Linux排查命令组合拳top、strace、gdb、netstatLinux题目常见的是“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 时间分配先拿基础分再攻算法压轴我的建议是按三个时间块划分时间段目标建议动作前45分钟完成基础题和简答题快速过OS/网络/C凡是能直接答出的先写中间45分钟算法题写出核心逻辑先给暴力解再优化保证有代码产出最后30分钟设计题与检查画出链路、写出关键组件检查答题纸上有没有漏题不要在“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和设计题的基础功一起补上平时写好代码后多问自己一句“这行代码在极端情况下会怎样”。这套卷子里藏着的其实就是一个后端工程师日常最需要的那几种能力。