58同城2016研发笔试题解析：数据结构与算法核心考点

1. 为什么2016年的笔试题现在还能当磨刀石

先说个扎心的现实：我去年帮部门筛简历的时候，发现不少候选人刷题只盯着LeetCode热题榜，结果一碰到手动推导复杂度、分析极端case的题目就露馅。反而是一些经历过早期互联网公司笔试洗礼的同事，基本功扎实得让人羡慕。58同城2016年的这套研发工程师笔试题，就是很好的基本功试金石——它没有花哨的场景题，没有脑筋急转弯式的抖机灵，考的就是一个研发工程师每天都要用的核心知识：数据结构、算法思维、操作系统、网络基础、代码实现能力。

这套题放在今天看，价值一点不过时。原因很简单：它设置的考核点全部是“不变的东西”。不管互联网技术栈怎么翻新——从单体架构到微服务再到云原生——底层的排序、查找、链表操作、内存管理、TCP状态流转，依然是每天要面对的。面试官拿这套题来面人，看的不是你会不会背八股文，而是遇到一个具体问题时，能不能快速建立模型、分析边界、写出能跑的代码。这也是我为什么翻出这套题，带大家一道一道过一遍的原因。

谁适合看这份解析？两类人。第一类是准备校招或跳槽的研发工程师，尤其是目标对准BAT、TMD这类流量型互联网公司的，可以通过这套题检验自己在基础知识上的薄弱环节。第二类是工作了两三年、开始带新人的工程师，这套题里的很多考点，恰恰是新人最容易写错的代码细节，拿来做团队内部培训材料也不错。

我尽量按照当年笔试的真实场景来还原——先给出题目，再讲思路，接着给代码，最后说清楚面试官到底想通过这道题考察什么。有些题我会额外延展一下，因为2016年的考题到2024年的面试里，考察方式变了，但内核还是那个内核。

2. 试题结构与考察方向拆解

2.1 整体结构回顾：一张卷子考的是哪些能力

58同城2016研发工程师笔试题的题型，和其他一线互联网公司大同小异，总体分为客观题和主观题两大部分。客观题以单选题、多选题为主，覆盖数据结构、算法、操作系统、计算机网络、数据库基础、语言特性几个方向；主观题则是2到3道编程题，要求手写完整代码，个别题目还会附加上时空复杂度分析。

从题目分布来看，它没有单独设逻辑推理题部分，但会在算法选择题里混合一些需要数学推导的计数问题——这意味着你即使不会硬编码，也要有扎实的数学建模能力。另外，因为58同城本身是分类信息平台，业务中大量涉及地理区域、分类筛选、用户匹配，所以它的算法题偏好字符串处理、排序优化、海量数据场景，这是和纯金融、纯游戏公司笔试不一样的地方。

2.2 各模块权重分析：哪里分多，哪里分少

以我拿到的回忆版题目为样本，各方向大致占比是这样的：

从这个占比能看出来，数据结构和算法是绝对的大头。这和各互联网公司的研发岗位强调算法面试的倾向完全一致。不是说操作系统、网络不重要，而是这些概念性内容在笔试里更适合用选择题来快速筛选——会就是会，不会编不出来。而算法题能考察知识深度、代码规范和临场应变，所以分值高、区分度高。

2.3 面试官视角：这套题在筛选什么人

我在面试别人的时候，有个很深的体会：一道笔试题到底在考什么，其实比题目本身更重要。58这套题有明显的筛选意图。

第一，它筛选“基础概念清晰的人”。举个例子，如果考“进程和线程的区别”，它期望的答案不是“进程是资源分配的单位，线程是CPU调度的单位”这种一句话解释，而是能说出进程有独立的地址空间、线程共享进程资源、切换开销对比、通信方式差异等细节。

第二，它筛选“代码手感好的人”。编程题部分不是简单给出思路就行，而是要求完整的可运行代码。变量命名、边界条件、空指针判断、返回值设计，这些细节都会看。我遇到过不少候选人，思路说得头头是道，一写代码就忘了判空，这种就是缺练。

第三，它筛选“能扛业务压力的人”。58同城这类公司的业务特点是流量大、数据量大、并发高，所以算法题偏好时间复杂度敏感的方案。一个知道用HashMap把O(n^2)优化成O(n)的候选人，和一个只写双层循环的候选人，笔试成绩可能差不太多，但面试评价会完全不同。

3. 高频考点逐题拆解：数据结构与算法篇

3.1 链表相关：反转链表的迭代与递归

链表反转是2016年58同城笔试题中出现过的一道经典编程题，也是各大互联网公司面试中出现频率超高的基础题。它的原型很简单：给定一个单链表，反转后返回新链表头节点。

这道题考察的点非常集中：指针操作、边界处理和理解递归。迭代法的核心思路是维护三个指针——prev、current、next。每次循环先保存current后面的节点，然后把current的next指向prev，再整体向后移动。有一次我帮候选人模拟面试，他写出来的代码是这样的：

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev = NULL; ListNode* curr = head; while (curr != NULL) { ListNode* nextTemp = curr->next; curr->next = prev; prev = curr; curr = nextTemp; } return prev; }

这段代码的核心bug点在于：很多人会漏掉循环里先保存nextTemp这一步，导致指针丢失。你必须意识到，当执行curr->next = prev之后，原来cur的下一个节点就访问不到了，所以必须在修改之前先暂存一份。这个细节，就是面试官快速判断你写代码习惯好不好的关键。

递归版本的思路稍微绕一点：先递归到链表末尾，然后逐层反转指针。代码如下：

ListNode* reverseListRecursive(ListNode* head) { if (head == NULL || head->next == NULL) { return head; } ListNode* newHead = reverseListRecursive(head->next); head->next->next = head; head->next = NULL; return newHead; }

容易出错的地方在于递归基的判断条件。如果只写head == NULL，那么一个只有一个节点的链表也能正常反转，但写法不够严谨。加上head->next == NULL这个条件，语义更清楚：单节点链表不需要反转。另外，这段代码的递归深度等于链表长度，如果链表特别长（比如数万节点），存在栈溢出的风险，所以工程实践中更推荐迭代法。

我建议你两种方法都掌握，因为面试官经常会追加一个问题：“如果链表有环，反转会怎么办？”这是一个延伸考点。迭代法遇到环会死循环，所以正常生产环境写链表反转前，要先判断是否有环。但笔试一般默认无环链表，不需要画蛇添足。

3.2 排序与查找：快排的边界与二分查找变种

选择题部分，58这年出了好几道和排序相关的题目，比较典型的有：快速排序在最坏情况下的时间复杂度是多少？对一个几乎有序的数组，用什么排序算法最合适？

快速排序最坏情况O(n^2)这个知识点大家都会背，但要真正理解它什么时候发生——每次选基准元素都选中了当前区间最大或最小值，导致划分极度不均匀。这就是为什么现在工程实现里，快排的基准选取会用“三数取中”或者“随机选取”来避免最坏情况。

还有一道二分查找的变种题，很有代表性：在一个非递减数组中查找第一个大于等于目标值的位置。这不就是标准库里的lower_bound吗？但手写的时候，很多人会掉进区间的坑里：

int lowerBound(vector<int>& nums, int target) { int left = 0, right = nums.size(); // 注意right取size，而不是size-1 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; }

这里有个很微妙的点：为什么right要取nums.size()而不是nums.size()-1？因为这个写法下，答案可能落在“数组最后一个元素后面”的位置（即所有元素都小于target，答案就是size），所以右边界要取开区间。如果你写成right = nums.size()-1，当目标值大于所有元素时，就会返回错误结果。这种细节，就是2016年这套题想要筛选出的“思路严谨型”候选人。

3.3 二叉树重建：由前序和中序还原二叉树

58同城笔试题里有一道中等难度题：给定一棵二叉树的前序遍历序列和中序遍历序列，要求重建二叉树，并输出它的后序遍历序列。这道题考察的是对三种遍历顺序的深刻理解，以及对分治思想的灵活运用。

前序遍历的顺序是“根左右”，中序遍历的顺序是“左根右”。利用前序遍历的第一个节点确定根节点，在中序遍历中找到这个根节点的位置，就可以确定左子树有哪些节点、右子树有哪些节点。然后递归处理左右子树。

这个思路听一遍就懂，但写代码的时候需要细心维护索引边界。我以前写过一版老犯错的代码：

TreeNode* buildTree(vector<int>& preorder, int preLeft, int preRight, vector<int>& inorder, int inLeft, int inRight, unordered_map<int, int>& indexMap) { if (preLeft > preRight || inLeft > inRight) return nullptr; int rootVal = preorder[preLeft]; TreeNode* root = new TreeNode(rootVal); int rootIndexInorder = indexMap[rootVal]; int leftTreeSize = rootIndexInorder - inLeft; root->left = buildTree(preorder, preLeft + 1, preLeft + leftTreeSize, inorder, inLeft, rootIndexInorder - 1, indexMap); root->right = buildTree(preorder, preLeft + leftTreeSize + 1, preRight, inorder, rootIndexInorder + 1, inRight, indexMap); return root; }

关键点在于leftTreeSize = rootIndexInorder - inLeft，这是左子树的节点个数。用这个大小去切分前序遍历序列，才能保证左子树的边界是对的。很多初学者直接用preLeft + 1当作左子树的起始，但不知道左子树的终点在哪里，导致递归参数传错。建议你自己用纸笔画一次，比如前序序列[3,9,20,15,7]、中序序列[9,3,15,20,7]，一步一步推，印象会非常深刻。

这道题的工程意义也很明显——我当年做数据同步工具的时候，需要把数据库里的树形结构导出来再重建，就是用的这个思路。当然，实际工程里不会用二叉树这么简单的结构，但分治拆解的思路是完全通用的。

3.4 字符串处理：最长公共前缀与括号匹配

字符串题是58同城的偏爱。整张卷子里至少有两道纯字符串题目：一道是求一组字符串的最长公共前缀，另一道是判断括号字符串是否合法。

最长公共前缀的朴素解法是纵向扫描：从第一个字符开始，拿第一个字符串做基准，逐个字符去检查其他字符串的对应位置是否一致，不一致就返回当前积累的公共前缀。这个解法的时间复杂度是O(S)，S是所有字符串的字符总数。代码不复杂，但有一个边界条件值得注意：如果字符串数组为空，直接返回空字符串；如果第一个字符串本身是空串，也直接返回空串。

括号匹配则更考察栈的应用——遍历字符串，遇到左括号就入栈，遇到右括号就和栈顶元素匹配，匹配成功则弹出，失败则返回false。最后还要检查栈是否为空，防止出现((())这种左括号过多的情况。我在实际项目里用栈的场景也很多，比如校验JSON格式是否完整、解析表达式的括号嵌套等。笔试虽然在考一道简单题，但背后代表的“利用栈处理嵌套结构”这种通用能力，才是面试官真正想看到的。

3.5 海量数据与哈希：从实现到应用场景

2016年是移动互联网爆发期，58同城这种信息分类平台，每天产生的帖子和搜索日志都是海量级别的。所以笔试里有一道不太起眼但值得展开的题目：如何统计一个大文件中出现次数最多的IP地址。

这道题也是很多公司面试的高频题，考察的是哈希分治思想。假设一个文件有100GB，内存只有4GB，直接加载肯定不行。常规思路是分而治之：先对文件做哈希取模，把大文件切分成1000个小文件。对每个小文件分别统计每个IP出现次数（可以用HashMap），再找出每个小文件里出现最多的IP。最后在1000个候选IP中比较，得到全局出现次数最多的那个IP。

你可能会问，为什么哈希取模能保证同一个IP一定会分到同一个小文件？因为哈希函数是确定的，同一个输入一定得到同一个哈希值，取模结果也就相同。这道题在笔试中只会出成选择题或简答题，但在面试中很容易追问：如果要求不精确统计而是近似的TopK，应该怎么做？那么答案可以聊到Count-Min Sketch这类概率性数据结构，或者用Redis的Sorted Set加过期策略来做热词统计。我建议你沿着这个思路延伸准备，因为它和58同城的热门搜索、热门帖子场景高度相关。

4. 操作系统与网络：笔试里踩过的坑

4.1 进程与线程：不是背概念那么简单

58这套题里考了一个看起来基础但错误率奇高的点：进程和线程的区别，以及进程间的通信方式。

很多人第一反应是“进程是资源分配的最小单位，线程是CPU调度的最小单位”，这句话没错，但拿到写题场景里远远不够。有一道多选题列出了四种说法，让考生选出正确的选项。比较典型的陷阱是：“线程之间共享同一个地址空间，所以不同线程的局部变量之间可以直接通过地址访问。”这个说法是错的——线程确实共享进程的地址空间，但局部变量是存放在栈区的，不同线程拥有各自的栈，所以局部变量之间不能直接通过对方地址访问，除非显式传递指针。

进程间通信方式也是一个高频选择题考点：管道、消息队列、共享内存、信号量、Socket。笔试时容易把“信号”和“信号量”混淆。信号是异步事件通知机制，信号量是同步互斥工具，一个是给进程发通知，一个是控制多个进程对共享资源的访问，本质完全不同。

复习操作系统这块，我的建议是不要死记硬背，把你自己在用的电脑当成例子。比如你打开微信和浏览器，这是两个进程；微信里面同时聊多个群、加载多张图片，这是线程在做的事情。一个进程崩了，不会直接拖垮浏览器；但一个进程里的某个线程死锁卡住，整个进程可能就无响应了。这样理解之后，面试官怎么追问你都能接住。

4.2 TCP三次握手：为什么不是两次或者四次

TCP三次握手是网络基础里的必考题，58这套题也考了。但它不是简单问流程，而是问了一组变体：为什么需要三次而不是两次？如果第三次握手丢失了会发生什么？

三次握手的本质是“双方确认自己的发送能力和接收能力都正常”。第一次握手，客户端发送SYN，服务端知道了客户端的发送能力，但还不知道客户端的接收能力是否正常。第二次握手，服务端回复SYN+ACK，客户端确认了自己的发送、接收能力都正常，也确认了服务端的发送能力正常。第三次握手，客户端发送ACK，服务端确认客户端的接收能力正常，同时也确认了自己的接收、接收能力正常。所以三次才能保证双方都确认“你能发我能收、我能发你能收”。

如果第二次握手丢失，客户端会一直收不到SYN+ACK，触发超时重传SYN；如果第三次握手丢失，服务端收不到ACK，会认为自己的SYN+ACK没有送达，触发重传。这些细节笔试里可能出成选择题，面试里可能会让你画状态转换图。建议你把CLOSED、LISTEN、SYN_SENT、SYN_RCVD、ESTABLISHED这几个状态串一遍，理解为什么要设计这些状态和定时器。

4.3 HTTP状态码：通过场景来记忆

有一道网络题列了五个HTTP状态码，让选出表示“服务器内部错误”的那个。正确答案是500。大部分人都知道，但笔试容易在502和504之间犹豫。这里我分享一个自己的记忆方法：502 Bad Gateway表示网关收到了上游服务器的无效响应，可理解为“网关去问后面服务器要东西，结果拿回来的东西是坏的”；504 Gateway Timeout表示网关在等待上游服务器响应时超时了，理解为“网关等了太久，还没等到回复就放弃了”。两个场景完全不同，一个是响应内容不对，一个是根本没有响应。结合分类信息网站的场景来想：如果某次网关请求超时，用户刷新页面会看到504；如果后端程序抛出未捕获异常，用户会看到502或500。这样记忆会轻松很多。

还有一道题和Cookie、Session相关：HTTP是无状态协议，服务端如何识别一个已登录用户？这题在2016年很经典，现在也是必问。答案核心是用Session在服务端保存用户状态，通过Session ID关联客户端。而这个Session ID通常通过Cookie保存，或者放进URL里以便适配禁用Cookie的场景。笔试如果出选择题，容易挖的坑是“Session保存在客户端”这个错误选项——Session数据本质上保存在服务端内存或Redis里，客户端只保存一个标识符。

5. 数据库与SQL实战细节

5.1 索引为什么能加快查询：B+树的优势

数据库题在58这套卷子里占比不算特别高，但有一个知识点出现的概率极高：索引的数据结构为什么用B+树而不是二叉搜索树或哈希表？

原因主要有三点。第一，B+树的非叶子节点不存数据，只存索引键值，因此每个节点能容纳更多键，树的高度更低。在机械硬盘时代，每次节点访问对应一次磁盘I/O，树高约等于I/O次数。一棵存储千万级数据的B+树，高度通常只有3到4层，意味着查询最多3到4次磁盘I/O。如果用二叉搜索树，树高可能达到20多层，I/O次数不可接受。第二，B+树的叶子节点用链表串联，天然适合范围查询。比如我要查某个分类下的所有帖子，用B+树可以快速找到起始位置然后顺序遍历。第三，哈希索引虽然单点查询快，但不支持范围查询，所以综合来看B+树是关系型数据库的主流选择。

这里有个容易混淆的概念：聚簇索引和非聚簇索引。笔试选择题喜欢问：InnoDB的主键索引是聚簇索引还是非聚簇索引？答案自然是聚簇索引，因为InnoDB的表数据本身就是按主键顺序组织的，叶子节点直接存储完整的行数据。而MyISAM的索引是独立的，索引叶子节点存的是数据行指针，属于非聚簇索引。这个区别在实际工作中影响很大，主键查询快慢、插入时页分裂的行为都不一样。

5.2 SQL编写题：分组统计的经典陷阱

笔试的SQL大题比较典型：有两张表，一张是用户表，包含用户ID和注册时间；一张是订单表，包含订单ID、用户ID、下单时间。要求统计每个用户的下单次数，并筛选出下单次数大于等于3的用户。

新手容易写错的版本是这样的：

SELECT user_id, COUNT(*) AS cnt FROM orders WHERE cnt >= 3 GROUP BY user_id;

错误在于：WHERE子句中不能直接引用聚合函数的别名cnt，因为WHERE是在分组之前执行的，此时还没有计算出cnt。正确的写法是使用HAVING：

SELECT user_id, COUNT(*) AS cnt FROM orders GROUP BY user_id HAVING COUNT(*) >= 3;

如果你还想联合用户表，拿到用户昵称，就需要JOIN一下。这里还有个细节：JOIN的时机是先分组还是先JOIN？从执行顺序上讲，是先FROM，再JOIN，再WHERE，再GROUP BY，再HAVING，最后SELECT。所以如果先JOIN再分组，数据量过大时效率会很低。大数据量场景下，更推荐先对订单表分组过滤，再和用户表JOIN：

SELECT u.user_id, u.nickname, t.cnt FROM users u JOIN ( SELECT user_id, COUNT(*) AS cnt FROM orders GROUP BY user_id HAVING COUNT(*) >= 3 ) t ON u.user_id = t.user_id;

为什么要这么写？因为子查询可以提前缩小数据规模，减少JOIN时的计算量。这种优化思路，在58同城这种订单量巨大的业务场景里，效果非常明显。

5.3 事务四大特性：ACID的口诀与临界场景

事务隔离级别和ACID特性是另一道高频选择题。ACID四个字母分别代表原子性、一致性、隔离性、持久性。笔试喜欢问的是“脏读”“不可重复读”“幻读”分别对应什么隔离级别。

这里有一个容易混淆的地方：不可重复读和幻读的区别。不可重复读是同一行数据内容发生变化（比如同一条订单金额被修改）；幻读是查询结果集合发生变化（比如同一条件下多了一条新订单）。MySQL默认的隔离级别是Repeatable Read（可重复读），在InnoDB引擎下通过当前读和快照读的MVCC机制，基本解决了不可重复读，但幻读在特定场景下依然可能发生，需要加锁或者使用间隙锁来处理。2016年的笔试题目尚未涉及这么深的间隙锁机制，但现在面试如果聊到MySQL的事务隔离，很容易追问到这一层。

我建议你在复习这一块的时候，用实际SQL做一遍实验：开两个终端，窗口A开启事务修改一条记录但不提交，窗口B去查询看能否读到，然后分别调整隔离级别，观察结果变化。亲自做一遍，比你背十遍概念都管用。

6. 语言基础：C++和Java的高频陷阱

6.1 指针与引用：C++笔试的送命题

58的笔试对编程语言没有强制限定，但语言基础部分仍然出了C++相关题目。最典型的一道：以下哪个说法是正确的？

A. 引用一旦初始化后，可以重新绑定到另一个变量。 B. 指针可以指向空值，引用不可以。 C. 函数形参为指针时，传入数组名等同于传入第一个元素的地址，所以数组作为函数参数时会退化成指针。 D. 以上说法都不对。

答案是B和C。这道题考察两个概念：一是引用必须在定义时初始化，且之后不能重新绑定。这是C++语言的一个硬性规则，和指针完全不同。二是在函数传参时，数组名会退化为指向首元素的指针，这样函数内部就无法直接通过sizof(arr)得到数组长度，必须显式传长度参数。这个坑在笔试和实际开发中都非常常见，我记得刚工作时不理解为什么函数里传进来的数组算不出大小，后来才发现是指针退化的问题。

6.2 Java的String不可变性与内存区域

如果选Java做题，那语言基础部分很可能出现String相关问题。比如问：String a = "hello"; String b = new String("hello"); a和b是否相等？

答案是不相等。a指向字符串常量池里的对象，b指向堆内存里新建的对象，两者地址不同。但如果用a.equals(b)，返回的是true，因为String重写了equals方法，比较的是内容。

这个知识点背后是Java内存模型的重要组成部分：字符串常量池、堆、栈。笔试选择题常会挖一个坑：“String是基本类型吗？”答案明显是否定的，String是引用类型，由final修饰，不可继承。理解了String不可变性，还能延伸到StringBuffer和StringBuilder的区别——前者线程安全但性能略低，后者非线程安全但性能更高。在单线程字符串拼接场景下，StringBuilder是首选。

6.3 内存泄漏与垃圾回收：从概念到排查

语言基础部分还会有GC相关的概念题，Java方向尤为常见。典型的问题：什么情况下会发生内存泄漏？CMS和G1垃圾回收器的主要区别是什么？

内存泄漏的核心是“本该被回收的对象，因为被错误地持有引用而无法回收”。常见的场景包括：静态集合类持有短生命周期对象、未关闭的连接资源（数据库连接、IO流）、内部类持有外部类引用导致外部类无法回收等。58同城当年有不少Java后端服务，这类问题在实际业务里会导致老年代持续增长，最终触发Full GC，线上接口平均耗时飙升。这个问题笔试只考概念，但如果你能结合一个线上排查思路来回答，面试官印象分会大幅提升。排查手段主要靠监控：观察GC日志中Full GC频率、老年代内存占用曲线，配合堆转储文件分析。

7. 编程题实战演练与应用场景结合

7.1 手写一个线程安全的单例模式

编程题里有一道让我印象深刻的：要求手写一个线程安全的单例模式，并解释为什么这样写是安全的。这道题不算难，但它能考察的知识面非常广：设计模式、并发机制、Java/C++内存模型、指令重排序。

我在面试中经常见到两个极端。极端一：写一个双重检查锁（Double-Checked Locking）但不声明volatile，然后自信满满地说线程安全。懂行的面试官一看就摇头——不声明volatile，指令重排序可能导致一个线程拿到了未初始化完成的对象引用。极端二：直接写一个静态内部类Holder版本的实现，不仅线程安全，还做到了延迟加载。这种版本值得推荐：

public class Singleton { private Singleton() {} private static class Holder { private static final Singleton INSTANCE = new Singleton(); } public static Singleton getInstance() { return Holder.INSTANCE; } }

它利用了Java类加载机制：内部类不会被主动加载，只有调用getInstance时才会触发Holder加载并创建实例。这种方式既没有锁，也保证了线程安全，是面试官最愿意看到的写法之一。如果你熟悉枚举，也可以说用枚举实现单例——Effective Java里推荐的方案，还能防止反射攻击。多准备几种实现方式，面试时自由切换着讲，会显得你对并发有深入理解。

7.2 从字符串匹配到敏感词过滤

58同城这种UGC平台，用户发帖、发评论非常频繁，敏感词过滤就是一个非常实际的需求。笔试中有一道字符串匹配题，我记不清原题是什么了，但可以肯定的是这类题目和业务有强关联。假设你需要从一个长文本中找出所有包含敏感词的位置，最简单的办法是逐字符匹配，复杂度O(n*m)，n是文本长度，m是敏感词总长度。如果敏感词数量多、文本体量大，这个性能在线上是无法接受的。

更优方案有两个方向：一是用Trie树结构把所有敏感词建树，然后对文本做一次扫描；二是用Aho-Corasick自动机，它是在Trie树上加失败指针，使得文本匹配复杂度降为O(n)。AC自动机在手写题里难度偏高，但如果你在笔试或面试中能把这个方案讲清楚，会是很强的加分项。我在早年做内容审核系统时就用过AC自动机，配合DFA（确定性有限自动机）状态转移，几万条敏感词在多长的文本上扫都不卡顿。可惜2016年那套题没有让我们写AC自动机的完整实现，但它作为一种扩展知识点延伸出来，当年也帮了不少考生。

7.3 手写栈实现队列和队列实现栈

另一类高频手写题是“用两个栈实现队列”和“用两个队列实现栈”。58这套卷子里我印象中也出现了类似题，因为它考察了数据结构的灵活运用，且代码量适中，非常适合笔试。

用两个栈实现队列的核心技巧：“入队栈”专管push，“出队栈”专管pop。当出队栈为空时，把入队栈的所有元素逐个弹出并压入出队栈，这样元素的顺序就反转过来了。代码实现如下：

class MyQueue { private: stack<int> inStack; stack<int> outStack; public: void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } int val = outStack.top(); outStack.pop(); return val; } bool empty() { return inStack.empty() && outStack.empty(); } };

摊还分析下，每个元素最多被移动两次——从入队栈压入一次、再弹出压入出队栈一次、最后弹出一次，所以平均时间复杂度是O(1)。这个摊还分析的概念，也是面试官喜欢追问的点：为什么均摊是O(1)？因为每个元素最多经历两次栈操作，虽然单次pop可能触发大规模转移，但整体均摊下来是常数级别。如果能主动提到摊还分析，面试官会觉得你是真正理解了，而不是背了代码。

反过来的“两个队列实现栈”则有一个常见的误区：很多人觉得用队列模拟栈的“后进先出”很麻烦，因为队列只能从尾部进、头部出。标准做法是每次push新元素时，先把它加入另一个空队列，然后把原队列的所有元素依次转移过来，让新元素始终保持在队首，这样pop就能直接取队首了。想清楚这个“逆序维护”的思路，代码反而不难。

8. 逻辑与数学题：讲究技巧而不是硬算

8.1 排列组合与概率统计的经典模型

选择题中有一类题目，虽然叫做逻辑与数学，但实际上并不考高等数学，更偏向高中数学里的排列组合。比如经典的“从5个男生和5个女生中选出3人，要求至少包含1名女生，一共有多少种选法？”

这个题的坑在于“至少包含1名女生”的正向计算很容易漏情况。正向拆分的话，要分情况讨论：包含1个女生选2个男生、包含2个女生选1个男生、包含3个女生。三种情况分别计算再相加。但反向计算要快得多：总的选法C(10,3)=120种，减去全部选男生的C(5,3)=10种，答案就是110。这类题考察的核心是逆向思维，在算法题里也同样重要——遇到正着算很复杂的计数问题，先想想反面的情况是不是更简单。

概率题往往会结合“摸球”“抽样”等场景。比如：盒子A里有3个红球和2个蓝球，盒子B里有2个红球和5个蓝球，随机选一个盒子，再从中抽出一个球是红球的概率。这是一个典型的全概率公式题目。但更常见的笔试进阶版是问“已知抽出的是红球，它来自盒子A的概率是多少”，这就是贝叶斯公式的应用。建议把全概率公式、贝叶斯公式这两个基础模型搞透，笔试时遇到变体题也能快速套上。

8.2 逻辑推理：真假命题与信息熵思维

58这套卷子里有一道印象比较深的推理题：有三个盒子，其中一个盒子里面有奖品，每个盒子上写着一句话，三句话中只有一个是真的。问奖品在哪个盒子。

这种题型的通用解法是“假设排除法”。先假设奖品在盒子A，判断三句话真假数量是否满足条件；再假设在盒子B，重复判断；逐一代入，找到满足条件的情况。这类题不难，但容易因为想当然而犯错。我当时的体会是：宁可全部列出情况，不要凭直觉猜。这和写程序是一样的逻辑——把所有状态枚举出来，根据条件筛掉不合格的，剩下的就是答案。

如果你想把逻辑题准备得更全面，还可以了解下“信息熵”的思维模式。所谓信息熵，套用香农的定义，就是一个事件不确定性的期望量化。笔试里的找假币问题就是典型场景：N枚硬币里有一枚假币，重量不同，用天平最少称几次能找出假币并判定轻重。这类题不需要动用复杂的数学公式，核心就在于每次称重最多产生三种结果：左重、右重、平衡。所以n次称重最多能区分3^n种情况，反过来，要找出多少个可能结果，称重次数就是log3(情况数)向上取整。这个思路一旦建立，你再遇到任何“最少几次”的问题，都能快速给出数量级判断，而不是一头雾水。

9. 如何高效准备类似笔试与面试

9.1 建立以真题为核心的刷题方法

说了这么多具体的题，最后回到一个更实际的问题：面对58同城2016年这套题，或者说任何一家公司的笔试真题，到底应该怎么刷才能效率最高？

我的建议是，先别急着看答案。拿到一套真题，先给自己计时90分钟，像真实考试一样做一遍，做不出来也硬憋。为什么？因为笔试和练习的最大区别是时间压力。真实考场上，你需要面对大量题目，遇到卡壳的题只能在短时间内决策：继续死磕还是先跳过去。平时如果不模拟这种压力，光靠“慢慢琢磨”练出来的解题能力，考场上会严重缩水。等到模拟考结束后，再逐题分析错因，把它记录到错题本里，并归类到对应的知识点清单中。

刷完几套真题后，你会发现高频知识点是有限的：链表操作、二叉树遍历、排序与查找、动态规划、字符串处理、并发设计、SQL聚合查询。这些都是可以定向突击的。比如你发现自己二叉树重建总出错，就连续练10道二叉树相关的题，直到形成肌肉记忆，而不是东一榔头西一棒子。

9.2 时间分配的考试策略

真实笔试过程中，时间分配同样重要。一般来说，客观题部分控制在30分钟以内，给后面的编程题留出充足时间。客观题里如果遇到一个纠结超过2分钟的选择题，建议先凭第一感觉选一个，标记下来，回头有时间再检查。编程题不要拿到手就写代码，先花2到3分钟在草稿纸上列出思路、边界条件、测试用例，想清楚再动手。我之前参加线上笔试时，见过太多人拿到题就直接开写，写着写着发现思路有漏洞，又涂改重来，最后反而浪费时间。好代码一定是先想清楚再落笔的。

另外，所有编程题都要注意函数签名和输入输出格式。笔试环境里，系统会跑测试用例，如果你连函数的入口参数都写错了，即使思路正确也无法通过。尤其要留意一些平台自带的模板，有时候已经帮你把main函数写好了，你只需要补全核心逻辑，这时候不要画蛇添足。

9.3 建立自己的错题复盘体系

错题复盘不是简单地把正确答案抄一遍，而是要记录下面几个维度：

• 这道题考察的核心知识点是什么？
• 我当时是在哪一步卡住的？是思路方向错了，还是边界条件没考虑周全，还是代码实现有问题？
• 正确的思路应该从哪个角度切入？
• 这个知识点还能衍生出哪些变体题？

比如有一道“统计字符串中每个字符出现次数”的题，你如果只用双重循环暴力解，虽然能通过，但复盘时应该想到用哈希表一次扫描完成，时间复杂度从O(n^2)降到O(n)。把这个优化过程记录下来，下次遇到类似题目，你的第一反应就会是哈希表，而不是暴力循环。这个过程才是刷题真正提升能力的地方。

10. 结合58同城业务场景：这些题背后的真实工程问题

10.1 分类信息平台的算法应用

58同城做的是分类信息平台，这意味着它每天要处理海量的用户发帖、浏览、搜索、筛选和交易行为。用户发帖后，平台要做类目判断——这篇帖子的标题写的是“海淀两居室出租”，应该自动归类到房产租房类目，这是文本分类问题；用户搜索时，平台返回了上千条结果，怎么排序让最相关、最靠谱的信息排在前面，这是排序和相关性计算问题；用户在地铁站刷手机，输入“家政保洁”，平台要基于地理维度快速找到附近的供应商，这是LBS地理位置检索问题。

这样回头再看这套笔试题，就会明白为什么它偏爱考察排序、查找、字符串、哈希、海量数据这类知识点了。链表反转看着和业务关系不大，但它训练的指针操作思路，和处理复杂数据结构的能力是相通的；二分查找的边界条件，和在海量帖子中精确命中目标信息的能力密切关联；SQL分组的HAVING子句，在做用户标签统计、发帖排行榜时几乎天天要用。

10.2 从笔试看研发工程师的基本功要求

业内有一个共识：面试造火箭、工作拧螺丝。笔试题往往比实际工作内容更偏算法和理论基础，但它也传递了一个信号——这家公司希望候选人有扎实的基本功，而不只是会调用框架和API。58同城作为老牌互联网公司，后端服务以Java和C++为主，业务涉及搜索推荐、交易安全、反作弊等复杂方向，这些都对底层知识有较高要求。比如一个优惠券系统的发券接口，如果不理解数据库事务隔离级别，就可能在并发领取场景下出现超发；一个搜索结果页的接口，如果不了解索引原理，一个简单的模糊查询就可能把数据库打挂。

所以，2016年的这套笔试题目放到现在，依然有很强的参考价值。它考的不是某个框架的新特性，而是那些十年后依然在用的基础知识。不管技术栈怎么演进，我们对数据结构的理解、对并发的感知、对数据库本质的把握，始终是研发工程师的核心竞争力。这也是我愿意花时间把题目一一拆开、重新梳理的原因——有些东西永远不会过时，值得一遍又一遍地打磨。

11. 我的备考经验与一点心里话

最后说点个人体会。这套题我第一次做的时候，网络和数据库部分错得最多，尤其是TCP状态和SQL的HAVING，当时总觉得这些知识点太碎，背了又忘。后来我换了一种学习方式：不背题目，而是去想背后的应用场景。TCP三次握手，我会联想到一次HTTP请求的完整生命周期；SQL聚合查询，我会想想业务后台的报表功能是怎么实现的。当知识有了附着点，记忆就会自然牢固。

准备笔试是一个枯燥的过程，但这也是一个让人快速认清自己短板的过程。刷58这套题时，你可能发现自己链表题写得飞起，但一碰到操作系统选择题就懵——这是个好消息，说明你找到了明确的复习方向。拿着错题清单去补知识点，比漫无目的地看教程高效得多。等你能把一套题从头到尾讲解给别人听的时候，说明这套题你已经彻底吃透了。

接下来如果你想扩展，建议找几套同期的真题做交叉练习，看看百度的笔试题、腾讯的笔试题在相同知识点上的不同考法。再往后，就是动手实践了——把一个简单的论坛系统写出来，在真实代码里体会链表、哈希、索引和并发，这些曾经的考题就都活了起来。