1. 为什么2016年的笔试题现在还能当磨刀石先说个扎心的现实我去年帮部门筛简历的时候发现不少候选人刷题只盯着LeetCode热题榜结果一碰到手动推导复杂度、分析极端case的题目就露馅。反而是一些经历过早期互联网公司笔试洗礼的同事基本功扎实得让人羡慕。58同城2016年的这套研发工程师笔试题就是很好的基本功试金石——它没有花哨的场景题没有脑筋急转弯式的抖机灵考的就是一个研发工程师每天都要用的核心知识数据结构、算法思维、操作系统、网络基础、代码实现能力。这套题放在今天看价值一点不过时。原因很简单它设置的考核点全部是“不变的东西”。不管互联网技术栈怎么翻新——从单体架构到微服务再到云原生——底层的排序、查找、链表操作、内存管理、TCP状态流转依然是每天要面对的。面试官拿这套题来面人看的不是你会不会背八股文而是遇到一个具体问题时能不能快速建立模型、分析边界、写出能跑的代码。这也是我为什么翻出这套题带大家一道一道过一遍的原因。谁适合看这份解析两类人。第一类是准备校招或跳槽的研发工程师尤其是目标对准BAT、TMD这类流量型互联网公司的可以通过这套题检验自己在基础知识上的薄弱环节。第二类是工作了两三年、开始带新人的工程师这套题里的很多考点恰恰是新人最容易写错的代码细节拿来做团队内部培训材料也不错。我尽量按照当年笔试的真实场景来还原——先给出题目再讲思路接着给代码最后说清楚面试官到底想通过这道题考察什么。有些题我会额外延展一下因为2016年的考题到2024年的面试里考察方式变了但内核还是那个内核。2. 试题结构与考察方向拆解2.1 整体结构回顾一张卷子考的是哪些能力58同城2016研发工程师笔试题的题型和其他一线互联网公司大同小异总体分为客观题和主观题两大部分。客观题以单选题、多选题为主覆盖数据结构、算法、操作系统、计算机网络、数据库基础、语言特性几个方向主观题则是2到3道编程题要求手写完整代码个别题目还会附加上时空复杂度分析。从题目分布来看它没有单独设逻辑推理题部分但会在算法选择题里混合一些需要数学推导的计数问题——这意味着你即使不会硬编码也要有扎实的数学建模能力。另外因为58同城本身是分类信息平台业务中大量涉及地理区域、分类筛选、用户匹配所以它的算法题偏好字符串处理、排序优化、海量数据场景这是和纯金融、纯游戏公司笔试不一样的地方。2.2 各模块权重分析哪里分多哪里分少以我拿到的回忆版题目为样本各方向大致占比是这样的考察方向大致题量占比常见出题形式数据结构与算法40%链表操作、二叉树遍历、排序原理、复杂度推导操作系统15%进程线程区别、死锁、内存管理概念计算机网络15%TCP握手、HTTP状态码、DNS解析流程数据库10%SQL编写、索引使用、事务特性语言基础10%C/Java内存、指针/引用、关键字语义逻辑与数学10%排列组合、逻辑推理、概率初步从这个占比能看出来数据结构和算法是绝对的大头。这和各互联网公司的研发岗位强调算法面试的倾向完全一致。不是说操作系统、网络不重要而是这些概念性内容在笔试里更适合用选择题来快速筛选——会就是会不会编不出来。而算法题能考察知识深度、代码规范和临场应变所以分值高、区分度高。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(vectorint 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(vectorint preorder, int preLeft, int preRight, vectorint inorder, int inLeft, int inRight, unordered_mapint, 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服务端知道了客户端的发送能力但还不知道客户端的接收能力是否正常。第二次握手服务端回复SYNACK客户端确认了自己的发送、接收能力都正常也确认了服务端的发送能力正常。第三次握手客户端发送ACK服务端确认客户端的接收能力正常同时也确认了自己的接收、接收能力正常。所以三次才能保证双方都确认“你能发我能收、我能发你能收”。如果第二次握手丢失客户端会一直收不到SYNACK触发超时重传SYN如果第三次握手丢失服务端收不到ACK会认为自己的SYNACK没有送达触发重传。这些细节笔试里可能出成选择题面试里可能会让你画状态转换图。建议你把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。正确的写法是使用HAVINGSELECT 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再分组数据量过大时效率会很低。大数据量场景下更推荐先对订单表分组过滤再和用户表JOINSELECT 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: stackint inStack; stackint 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这套题时你可能发现自己链表题写得飞起但一碰到操作系统选择题就懵——这是个好消息说明你找到了明确的复习方向。拿着错题清单去补知识点比漫无目的地看教程高效得多。等你能把一套题从头到尾讲解给别人听的时候说明这套题你已经彻底吃透了。接下来如果你想扩展建议找几套同期的真题做交叉练习看看百度的笔试题、腾讯的笔试题在相同知识点上的不同考法。再往后就是动手实践了——把一个简单的论坛系统写出来在真实代码里体会链表、哈希、索引和并发这些曾经的考题就都活了起来。 58同城2016研发笔试题解析：数据结构与算法核心考点
1. 为什么2016年的笔试题现在还能当磨刀石先说个扎心的现实我去年帮部门筛简历的时候发现不少候选人刷题只盯着LeetCode热题榜结果一碰到手动推导复杂度、分析极端case的题目就露馅。反而是一些经历过早期互联网公司笔试洗礼的同事基本功扎实得让人羡慕。58同城2016年的这套研发工程师笔试题就是很好的基本功试金石——它没有花哨的场景题没有脑筋急转弯式的抖机灵考的就是一个研发工程师每天都要用的核心知识数据结构、算法思维、操作系统、网络基础、代码实现能力。这套题放在今天看价值一点不过时。原因很简单它设置的考核点全部是“不变的东西”。不管互联网技术栈怎么翻新——从单体架构到微服务再到云原生——底层的排序、查找、链表操作、内存管理、TCP状态流转依然是每天要面对的。面试官拿这套题来面人看的不是你会不会背八股文而是遇到一个具体问题时能不能快速建立模型、分析边界、写出能跑的代码。这也是我为什么翻出这套题带大家一道一道过一遍的原因。谁适合看这份解析两类人。第一类是准备校招或跳槽的研发工程师尤其是目标对准BAT、TMD这类流量型互联网公司的可以通过这套题检验自己在基础知识上的薄弱环节。第二类是工作了两三年、开始带新人的工程师这套题里的很多考点恰恰是新人最容易写错的代码细节拿来做团队内部培训材料也不错。我尽量按照当年笔试的真实场景来还原——先给出题目再讲思路接着给代码最后说清楚面试官到底想通过这道题考察什么。有些题我会额外延展一下因为2016年的考题到2024年的面试里考察方式变了但内核还是那个内核。2. 试题结构与考察方向拆解2.1 整体结构回顾一张卷子考的是哪些能力58同城2016研发工程师笔试题的题型和其他一线互联网公司大同小异总体分为客观题和主观题两大部分。客观题以单选题、多选题为主覆盖数据结构、算法、操作系统、计算机网络、数据库基础、语言特性几个方向主观题则是2到3道编程题要求手写完整代码个别题目还会附加上时空复杂度分析。从题目分布来看它没有单独设逻辑推理题部分但会在算法选择题里混合一些需要数学推导的计数问题——这意味着你即使不会硬编码也要有扎实的数学建模能力。另外因为58同城本身是分类信息平台业务中大量涉及地理区域、分类筛选、用户匹配所以它的算法题偏好字符串处理、排序优化、海量数据场景这是和纯金融、纯游戏公司笔试不一样的地方。2.2 各模块权重分析哪里分多哪里分少以我拿到的回忆版题目为样本各方向大致占比是这样的考察方向大致题量占比常见出题形式数据结构与算法40%链表操作、二叉树遍历、排序原理、复杂度推导操作系统15%进程线程区别、死锁、内存管理概念计算机网络15%TCP握手、HTTP状态码、DNS解析流程数据库10%SQL编写、索引使用、事务特性语言基础10%C/Java内存、指针/引用、关键字语义逻辑与数学10%排列组合、逻辑推理、概率初步从这个占比能看出来数据结构和算法是绝对的大头。这和各互联网公司的研发岗位强调算法面试的倾向完全一致。不是说操作系统、网络不重要而是这些概念性内容在笔试里更适合用选择题来快速筛选——会就是会不会编不出来。而算法题能考察知识深度、代码规范和临场应变所以分值高、区分度高。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(vectorint 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(vectorint preorder, int preLeft, int preRight, vectorint inorder, int inLeft, int inRight, unordered_mapint, 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服务端知道了客户端的发送能力但还不知道客户端的接收能力是否正常。第二次握手服务端回复SYNACK客户端确认了自己的发送、接收能力都正常也确认了服务端的发送能力正常。第三次握手客户端发送ACK服务端确认客户端的接收能力正常同时也确认了自己的接收、接收能力正常。所以三次才能保证双方都确认“你能发我能收、我能发你能收”。如果第二次握手丢失客户端会一直收不到SYNACK触发超时重传SYN如果第三次握手丢失服务端收不到ACK会认为自己的SYNACK没有送达触发重传。这些细节笔试里可能出成选择题面试里可能会让你画状态转换图。建议你把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。正确的写法是使用HAVINGSELECT 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再分组数据量过大时效率会很低。大数据量场景下更推荐先对订单表分组过滤再和用户表JOINSELECT 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: stackint inStack; stackint 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这套题时你可能发现自己链表题写得飞起但一碰到操作系统选择题就懵——这是个好消息说明你找到了明确的复习方向。拿着错题清单去补知识点比漫无目的地看教程高效得多。等你能把一套题从头到尾讲解给别人听的时候说明这套题你已经彻底吃透了。接下来如果你想扩展建议找几套同期的真题做交叉练习看看百度的笔试题、腾讯的笔试题在相同知识点上的不同考法。再往后就是动手实践了——把一个简单的论坛系统写出来在真实代码里体会链表、哈希、索引和并发这些曾经的考题就都活了起来。