复盘人人网2015研发笔试卷：算法、操作系统与数据库考点

前几天整理旧资料，翻出一份PDF，文件名写着《人人网2015研发笔试卷E》。说实话看到这个名字的时候愣了几秒——那会儿人人网还是很多应届生眼里的热门去处，从校内网改名之后，社交产品做得风生水起，研发笔试也出了好几套题，E卷就是其中之一。十年过去，产品起起落落，但这张卷子里的知识点，拿出来今天再看一遍，依然有价值。

很多读者可能会问：一份2015年的笔试卷，放到现在还有什么用？我的看法是，笔试这关考的东西，和互联网业务的风口是两回事。无论产品怎么变，研发岗笔试的筛选逻辑几乎没变过——用一套标准化题目快速过滤候选人，考察数据结构、算法、操作系统、计算机网络、数据库、语言基础，再配几道逻辑题。这套框架到今天仍然是主流。所以这个复盘不是贩卖情怀，而是帮你看清这类笔试的出题节奏，顺便验证一下自己的基础功到底扎不扎实。

1. 十年后重看：这张卷子为什么还有复盘价值

1.1 当年人人网研发笔试的基本盘

先说清楚大背景。2015年移动互联网还在高速增长期，人人网虽然不再是当年校园社交的绝对霸主，但体量依然不小，校招笔试的题目质量也一直在线。研发岗的笔试基本是线下统一考试，一张卷子两个小时，题型以问答和编程题为主。E卷是同一套笔试题的平行版本之一，和A到D卷的结构类似，难度也不会差太多，主要目的是防止相邻考生互相抄。

我当时按同批次题目和出题风格做了一份分布梳理，大致是这样：

这个分布不是我瞎编的，你去看2015年前后各家互联网公司的研发笔试题，基本上都是这个配方。算法和数据结构一定是大头，操作系统和网络必有一席之地，语言基础用来卡细节，数据库考察实际写SQL的能力，最后用逻辑题看看你遇到陌生问题时能不能拆解。

1.2 笔试过关的本质是把基础知识连成闭环

做过笔试题的人都有这种感受：很多题单独拿出来都见过，但放到一张卷子里，两个小时做完就手忙脚乱。根本原因在于基础知识是零散的，没有形成闭环。

所谓闭环，就是每看到一个考点，你能立刻反应出它和哪些知识点有关系。比如卷子里考到TCP三次握手，如果你只记了“三次握手”四个字，那道题大概率只能拿一两分；如果你能把握手的过程、为什么是三次不是两次、SYN洪泛攻击、初始序列号的作用、与四次挥手的关系全部串起来，那道题闭着眼睛也能拿全分。

这正是当年人人网笔试卷E这类老题目的价值所在。它考的从来不是“偏、难、怪”，而是看你把大学四年最重要的几门课吃透了多少。这个逻辑放在今天的笔试上依然成立。

2. 算法题复盘：字符串、链表和Top K的考察逻辑

算法题是整张卷子的核心，按我的回忆和同类试卷对比，E卷里算法题至少占了三道以上。下面这几类题，都是那个年代研发笔试的高频代表，现在互联网公司笔试也还经常出现。

2.1 字符串压缩：边界条件比主逻辑更值钱

这类题在当年的卷子里很典型，原题大致是：给定一个字符串，把连续出现的字符按“字符+出现次数”的方式压缩，比如aabcccccaaa变为a2b1c5a3。如果压缩后的字符串长度不小于原字符串，则返回原字符串。

看起来很简单的字符串处理题，但能在一张限时卷子里拿满分的同学并不多。我把一个可用的解法写出来：

#include <string> using namespace std; string compressString(const string& s) { if (s.empty()) return s; string result; int count = 1; for (int i = 1; i < s.size(); ++i) { if (s[i] == s[i - 1]) { ++count; } else { result.push_back(s[i - 1]); result += to_string(count); count = 1; } } result.push_back(s.back()); result += to_string(count); return result.size() < s.size() ? result : s; }

这题的考察点不止一个。第一，循环终止条件怎么设计，能不能处理字符串末尾的字符段；第二，压缩后字符串没变短时，要返回原字符串，这个分支很容易被漏掉；第三，字符计数超过一位数的时候，转字符串是否正确。

我当年见过不少人主逻辑写得很顺，结果就是在边界条件上翻车。比如字符串是"a"时，压缩结果是a1，长度反而变长，应该返回原串。又比如空字符串，很多人没判断就直接段错误。面试官出这种题，想看的不是你能不能写出 for 循环，而是你写代码有没有边界意识。

2.2 单链表反转：两种写法的对比

链表反转几乎是必考题。2015年是这样，现在依然是这样。这个题有两个主流方向：迭代法和递归法，两种都要能手写出来。

迭代版本的思路是维护三个指针：当前节点、前驱节点、下一个节点。每次把当前节点的 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* nextNode = cur->next; cur->next = prev; prev = cur; cur = nextNode; } return prev; }

递归版本更短，但难度更高。递归的思考方式是从后往前反转：先递归反转后继节点，然后把当前节点的指针接到反转后的链表尾部。很多人在笔试时一紧张就绕进递归旋涡里，所以我建议笔试优先用迭代版本，它更直观、不容易写错。

这道题看似基础，实际是在考察两个能力：第一，你是否理解指针操作的时间顺序，第二，递归场景下你是否能跟踪调用栈的返回关系。如果打算面大厂，建议把迭代和递归都写在纸上练熟，每个版本三分钟写完是基本要求。

2.3 Top K：从排序到快速选择的思路演进

卷子里还有一类题我印象很深：“找出一个无序数组中第K大的数”。很多人上来就说排序，一排序就是O(n log n)，虽然不扣分，但也拿不到满分。出题人的深层意图是看你知不知道有更优解。

常规演进路径是这样：先想到排序，再想到用一个大小为K的小顶堆维护前K个最大元素，时间复杂度O(n log K)，最后如果能写出快速选择（quick select），平均时间复杂度能降到O(n)。

快速选择的核心是快排的partition过程。每次把数组分成左右两块，比较基准值的位置和K的关系，只往一边递归。我写一份返回第K大元素的版本：

#include <vector> using namespace std; int partition(vector<int>& arr, int left, int right) { int pivot = arr[right]; int i = left; for (int j = left; j < right; ++j) { if (arr[j] > pivot) { swap(arr[i], arr[j]); ++i; } } swap(arr[i], arr[right]); return i; } int quickSelect(vector<int>& arr, int left, int right, int k) { if (left == right) return arr[left]; int p = partition(arr, left, right); int count = p - left + 1; if (count == k) return arr[p]; if (count > k) return quickSelect(arr, left, p - 1, k); return quickSelect(arr, p + 1, right, k - count); }

注意我在 partition 里选了最右元素做基准值。笔试时这样写最不容易出错，但你的脑子里要清楚：当输入接近有序时，这种写法会退化到O(n²)。所以笔试答题时建议在题解里补一句“实际工程中会选择随机基准值以避免退化”，面试官看到这句话会认为你是真的理解，而不是只会背代码。

3. 操作系统与网络：死锁、握手和内存管理的出题套路

操作系统和网络是笔试的固定板块，也是很多人容易忽视的部分。算法题不会就是不会，但操作系统和网络这两门的细节极多，复习起来没有边界，于是很多人干脆战略性放弃。事实上这部分恰恰是最容易靠短时间背诵拿分的。

3.1 死锁四条件：送分题还是拉分题

“死锁产生的四个必要条件是什么”大概是2015年笔试里出现频率最高的操作系统问题，E卷几乎不可能放过这个考点。标准答案只有一句话：互斥、持有并等待、不可剥夺、循环等待。

但这道题真正的区分度在第二问：“如何破坏这四个条件？”很多同学只背了条件，不会应用。比如破坏“持有并等待”可以通过一次性申请所有资源；破坏“不可剥夺”可以在资源无法获得时主动释放已占有的资源；破坏“循环等待”可以对资源编号，按序申请。如果能再举一个具体的死锁例子，比如两个线程互相等待对方释放锁，这道题基本就拿稳了。

笔试答题有个技巧：简答题别只写关键词，要把“概念+条件+破坏方法+例子”四个层次写全。阅卷人不是只看你有没有写到点子上，还在看你的表达是否完整。

3.2 TCP三次握手为什么必须是三次

网络题绕不开TCP。2015年的E卷我印象中问了“为什么TCP建立连接需要三次握手，两次行不行”，这题到今天仍然是面试高频题，答得好不好直接暴露你到底是背了八股还是真的理解了协议设计。

三次握手要解决的核心问题有两个：一是让双方确认对方的收发能力正常，二是同步初始序列号。如果只有两次握手，服务端发出SYN+ACK之后就直接进入ESTABLISHED状态，但客户端可能因为网络延迟没有收到这个报文，它就会认为自己没连接上，不发送数据。服务端却一直等着，白白维护连接资源。

更严重的问题是，如果客户端发出的SYN因为网络原因滞留，在连接关闭后才到达服务端，服务端会误以为这是一次新连接请求，于是回复SYN+ACK并建立起一条已经过期的连接。有了第三次握手，客户端发现这条连接不是自己发起的，就不会再回应，服务端等不到第三次ACK就会释放连接。

所以答这道题的时候，别只背“三次握手是为了确认双方收发能力”这一句话，最好能画出状态变迁，把拥塞窗口、SYN洪泛这些扩展知识也带上一两句。这张卷子考的是理解深度，不是背诵广度。

3.3 虚拟内存与页面置换

操作系统还有一类题特别经典，就是给你一个页面访问序列，问在指定物理块数量下，FIFO和LRU两种置换算法各产生多少次缺页。这类题算起来很繁琐，但实际上是送分题，只要你按表格一步步填，稳拿。

我常用来练手的一个经典序列是：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1，物理块数设为3。我直接说结论：FIFO缺页15次，LRU缺页12次。这个例子特别适合用来理解两者的差异。

FIFO看的是调入内存的时间，谁先来谁先走。比如访问序列第4个元素2时，7是最早进来的，所以2替换7。LRU看的是最近一次被访问的时间，谁最长时间没被用到谁先走。在访问第6个元素3时，内存里是2、0、1，其中1最久没被访问，所以3替换1，而不是替换2。

这里要用一个常见的类比来理解：FIFO像食堂排队，先来的先打饭走人；LRU像宿舍衣柜，最近穿过的衣服放最外面，好久没穿的压箱底，要扔的时候优先扔它。区别在于访问序列中某个页面可能在很早就被再次使用，这时LRU的优势就体现出来了。

笔试中这种题一定要把过程表格画出来，不要心算。用表格列清楚访问次数、访问页面、内存状态、是否缺页，阅卷人看得清楚，你自己也不容易出错。

4. 语言与数据库：C++陷阱、索引和事务的笔试常见问法

4.1 内存对齐：一道考住很多人的小题

语言基础题里面，C++内存对齐是那个年代笔试的常客，现在偶尔也出现在面试题里。E卷里这类题我按当时的风格还原一道：

struct A { char a; int b; char c; }; struct B { char a; char c; int b; };

问这两个结构体分别占多少字节。很多人凭直觉觉得都是6字节，错。在默认4字节对齐的编译环境下，结构体A占12字节，结构体B占8字节。

原因是编译器在存储成员时会自动填充空白字节：每个成员的偏移量必须是其自身对齐数的整数倍。结构体A里，a占1字节后，b是int类型占4字节，所以需要填充3个字节让b对齐到偏移4的位置；c是1字节，放在偏移8处；最后整个结构体大小必须是最大对齐数4的整数倍，所以从9补齐到12。结构体B把两个char放在前面，a占偏移0，c占偏移1，b放到偏移4，总大小刚好8字节。

笔试遇到这道题，我的建议是快速找两个关键数：最大对齐数和成员偏移规则。按“偏移按成员对齐数整数倍放置，总大小按最大对齐数整数倍补齐”的规则算，30秒就能出来。此外你还可以顺带说一句“#pragma pack可以修改对齐方式”，这句话能让阅卷人感觉你不只是会背规则，而是真做过底层开发。

4.2 指针和引用的差异，以及C++对象的常见坑

C++的题还经常考指针和引用的区别。标准答案大概有这几条：引用在定义时必须初始化，指针不需要；引用不能更改绑定对象，指针可以；引用不能为空，指针可以为空；sizeof引用得到的是所引用对象的大小，sizeof指针在32位平台是4字节、64位平台是8字节。

这道题的区分度在于，很多同学能说出前两条，却忽略了引用在函数重载和拷贝构造里的一些细节。比如“拷贝构造函数为什么参数必须是引用类型”，正确的解释是：如果传值，调用拷贝构造函数就需要按值传参，而按值传参又需要调用拷贝构造函数，这会形成无限递归。这个点如果能在笔试卷子里写出来，分数会明显高一档。

语言题在整张卷子里占比不算最大，但它是最容易暴露出基础不扎实的地方。一道8分的C++陷阱题，懂的人拿满分，半懂的人拿2分，差距非常大。

4.3 SQL多表查询：从“会写”到“写得对”

数据库题基本必考SQL编写。当年的试卷场景很常见：学生表、课程表、选课表三张表，要求查询“选了数据库课程但没选网络课程的学生姓名”。

一个能用的SQL是这样：

SELECT s.name FROM Student s WHERE s.id IN ( SELECT sc.sid FROM SC sc JOIN Course c ON sc.cid = c.cid WHERE c.name = '数据库' ) AND s.id NOT IN ( SELECT sc.sid FROM SC sc JOIN Course c ON sc.cid = c.cid WHERE c.name = '网络' );

这个题考察的不只是会写JOIN，而是你能不能把业务逻辑转换成集合思维。IN表示“在集合内”，NOT IN表示“不在集合内”，整个查询本质是集合的交与差。

更进阶的写法是使用EXISTS，原理是关联子查询，逐行判断学生是否存在对应的选课记录。两种写法面试官都会认可，但如果你能在卷子里把两种都写出来，再说明IN适合子查询结果集小的情况、EXISTS在子查询表大时性能更好，数据库这关就基本无忧了。

4.4 索引结构为什么是B+树而不是红黑树

数据库常考的另一道题是“为什么InnoDB的索引结构用B+树”。一道题能答出三层深度，分数就完全不一样。

第一层是B+树矮胖，树高大概只有3到4层，磁盘IO次数少，查询效率稳定；第二层是非叶子节点不存数据，只存索引键和指针，一个节点能装更多条目，所以树更矮；第三层是叶子节点通过链表相连，支持范围查询和排序，这在SQL的WHERE和ORDER BY场景里非常重要。

对比红黑树，它虽然也是平衡树，但高度在log₂n级别，一个几百万行数据的表，红黑树高度可能有20多层，每次向下查找都是一次磁盘IO，代价太高。所以红黑树适合在内存中做关联容器，比如C++的map、set，而数据库索引这种需要大量磁盘交互的场景，B+树是更合适的选择。笔试试卷里能写到这个层面，已经不只是一道八股题了，而是在向面试官证明你真的理解存储引擎。

4.5 事务特性和隔离级别：一张表解决的事

数据库最后常考的是事务。ACID四个特性——原子性、一致性、隔离性、持久性，基本是送分题。但后面的问题就有点深度了：事务隔离级别有哪几种，分别解决什么问题。

用一张表可以讲清楚：

笔试里最好再举个具体例子。所谓脏读，就是事务A修改了数据还没提交，事务B就读到了这条修改；如果事务A回滚，事务B读到的就是脏数据。不可重复读是同一事务内两次读取同一行，结果不一致，因为其他事务在这期间提交了修改。幻读是同一个查询条件，两次查询返回的行数不同，因为其他事务插入了新行。

MySQL默认隔离级别是可重复读，而且InnoDB引擎在可重复读级别下通过间隙锁协议解决了大多数幻读情况。这个知识已经接近业务开发的实际场景了，写出来会让整份答卷的质量上一个台阶。

5. 那道传了十年的智力题，和它背后的思维能力

笔试卷最后通常会来一道逻辑题，人人网E卷里我印象很深的是“25匹马，5个赛道，最少比赛几次能找出最快的3匹”。这道题现在很多面试官还在用，值得认真讲一遍。

先说答案：7次。这个结论让很多人意外，你以为至少10次，但通过分治只需要7次。推理过程如下。

第一步：把25匹马分成5组，每组5匹，各跑一轮。共5次，得到每组内部的排名。

第二步：让每组第一名跑一轮。这是第6次。假设这次比赛的结果按快慢排序，五组分别是A、B、C、D、E，那么A组第一名就是全场总冠军，因为它跑赢了其他所有组的第一名。

第三步：剩下的候选马没有你想象中那么多。D组和E组的所有马都可以排除，因为它们组第一名都没进总前五，组内其他马更不可能进总前三。C组只能留下第一名，因为C组第一已经排在A组第一和B组第一后面，C组第二即使再快也不可能挤进前三。B组可以留下第一名和第二名。A组可以留下第二名和第三名，因为A组第一已经占了前三的一个名额。

所以最终需要跑第7次的三匹候选马是：A组第二、A组第三、B组第一、B组第二、C组第一。五匹马跑一轮，取前两名，再加上A组第一，就是全场最快的三匹马。

这道题的精髓不在于你智商高不高，而在于你有没有结构化思维。很多人一上来就想着把所有马都跑一遍，却没有意识到“排名信息”可以帮你排除大量无效候选。这道题放到研发笔试里的意图也在于此：不是考察你有没有见过这道题，而是看你在信息不完整的条件下，能不能通过推理缩小问题规模。

后来我在面试人时也喜欢问这个题，见过三种典型反应。一种是背过答案的，上来就说7次，但问为什么选那几匹就支支吾吾；一种是现场推出来但过程混乱，说明逻辑链条清晰度不够；还有一种能一边推导一边画出候选树，这种人即使在真实业务里遇到性能优化问题，也大概率知道如何缩小排查范围。

6. 备考启示：从这份卷子里能带走的笔试准备策略

6.1 把高频考点串成知识闭环

复盘完这份卷子，我想说点更实际的。很多准备笔试的人容易陷入盲目刷题，今天做几道链表，明天看两眼数据库，后天又去背网络，结果每个方向都是半桶水。2015年卷子给我的启示是：笔试考的不是单点，而是面。

我建议按模块做知识闭环。算法以数组、链表、字符串、二叉树和动态规划为主，每天一个类型，刷完一轮后再做混合题；操作系统把进程与线程、死锁、虚拟内存、页面置换做成一套笔记，边整理边做计算题；网络从TCP和UDP出发，把三次握手、四次挥手、流量控制和拥塞控制串起来画成状态图；数据库围绕索引、事务、SQL三块反复练。

有一个很有效的方法：每复习一个模块，就试着出一道和原题类似的题目，然后自己回答。比如复习完页面置换，就自己编一个访问序列，用FIFO和LRU各算一遍缺页次数。能自己出题、自己能讲到别人听懂，这个知识点就真正内化了。

6.2 笔试现场的节奏、取舍和边界检查

笔试现场最重要的是时间分配。一张两个小时的卷子，算法题往往要占掉一半时间，如果你在某道题上卡了十五分钟没有任何思路，先标记跳过去，把后面会的题做完再回头。宁可每一题都拿一部分分，也不要一道题磨到底。

做编程题时，我习惯先写注释，把整体思路列出来。比如链表反转这道题，先在纸上写“迭代：prev,cur,next三指针”，然后再开始写代码。这样即使最后代码没有跑通，阅卷人也看得到你的思路路径，能给思路分。

还有一条是老生常谈但极其重要的：边界检查。空数组、单个元素、字符串末尾、链表只有一个节点、K值等于1或等于数组长度，这些都是笔试题最爱埋的雷。写完代码之后，花一分钟用一个简单输入在脑子里走一遍，很多低级错误当场就能发现。

6.3 十年过去了，笔试变在哪儿，没变在哪儿

现在回头对比，笔试考察的底层能力其实没变。算法和数据结构仍然是第一关，操作系统和网络依然是基础中的基础，SQL写的熟不熟练依旧一眼见高下。这些知识就像程序员的地基，不管你后来做业务、做中间件、还是做算法工程，都需要靠它们兜底。

变化也很大。第一，技术栈更宽了，2015年那会儿很多公司默认应聘者用C++或Java，现在Go、Rust、Python、TypeScript都成了常见选项；第二，OJ在线评测成为主流，代码跑不过用例就直接判错，不像纸质卷子还能看思路给分；第三，算法题的难度整体上抬高了，hard题在现在的校招笔试里不算稀罕，这在当年是比较少见的；第四，面试环节对项目经历的权重增加了，笔试只是入场券，能不能拿到offer更多看技术面和HR面的综合表现。

所以我的建议是：不要迷信“刷完几百道题就能包过”这种话，但也不要轻视笔试，因为笔试就是那道最基础的门槛。把这份老卷子复盘清楚，本质上是在帮你确认自己对这些“不变的地基”掌握得怎么样。地基稳了，上面盖什么楼都行。