深入解析人人网2015研发笔试题D：基础与算法全攻略

说个暴露年纪的事这些年帮人改简历、做模拟面试偶尔还会翻出当年攒下的一沓校招笔试题。人人网2015年研发笔试卷D就是其中比较有代表性的一套。那时候社交产品还在拼功能迭代速度研发岗笔试不像现在这样动不动就整系统设计、分布式一致性反倒更看重基础功底的扎实程度和临场写代码的硬功夫。这份卷子如果放到今天看难度并不算夸张但它考察知识点的密度和角度放在当年的校招语境里非常典型。我当时做完这套题的最大感受是它不是想看你背了多少八股文而是想确认你有没有真正写过代码、调过bug、理解过数据在内存里到底怎么流转。这篇文章就围绕这套题拆一拆说说每类题背后的考察意图、解题思路以及当时踩过的坑——如果你正在准备研发岗笔试或者想复盘一下自己的基础功底应该能用得上。1. 试卷整体观感D卷到底在考什么这套D卷的题型分布大致是单选多选混搭的基础知识题占了三成简答和手写代码占了四成剩下三成是综合设计题和开放题。整体来看它考察的核心就三件事语言功底、算法思维、工程意识。先说语言功底。2015年前后社交类互联网公司的主站后端大量使用C和PHP移动端则集中在Objective-C和Java。这套卷子的语言题主要围绕C展开涉及内存管理、指针、STL容器底层实现等。这不是偶然——对当年的人人网来说后端服务要支撑千万级用户的同时在线C的性能优势没法替代所以招人时特别看重候选人对内存和底层机制的理解。再来看算法题。试卷里的算法题不是那种偏怪偏难的ACM竞赛题而是和业务场景能扯上关系的实际问题。比如字符串处理、链表操作、查找排序这些统统能在社交产品的功能逻辑里找到对应。这说明出题人想要的是能解决实际工程问题的人不是只会刷题的人。最后是工程意识。综合设计题会给你一个很具体的场景比如“设计一个好友推荐的数据结构”“怎么存储海量短消息”然后让你谈思路。这类题没有标准答案但特别能区分一个人的水平是真做过东西还是只停留在背概念。我后来自己参与过几次校招笔试命题才发现这类卷子的设计逻辑其实是一致的基础知识题筛掉没好好准备的手写代码题筛掉不会真写代码的设计题筛掉没有工程思维的。D卷的难度阶梯设计得挺合理三块层层递进每一块都在有意识地过滤人。2. 基础知识题背后的考察意图不只看你会不会写这套卷的电基础题部分现在回忆起来大致覆盖了计算机网络、操作系统、数据库、C语法几个方向。题目本身不算难但它会在一些容易混淆的知识点上“挖坑”目的就是考察你有没有真正深入理解而不是浮于表面的记忆。2.1 计算机网络题TCP三次握手为什么不是两次卷子里有一道很经典的选择题问的是TCP建立连接为什么需要三次握手而不是两次。很多人在这道题上翻车是因为背了“三次握手是为了确认双方收发能力正常”这个结论但真让他展开说就卡住了。实际上三次握手最核心的原因是为了防止已失效的连接请求报文段突然又传到了服务器端从而产生错误。想象这样一个场景客户端的第一个SYN报文段在网络中滞留了客户端迟迟没收到确认于是重传了一个新的SYN这次连接建立成功数据传输完毕连接关闭。结果第一个滞留的SYN这时候才到达服务器服务器以为客户端又要建立新连接于是返回SYNACK。如果只有两次握手这时候服务器就已经为这个“幽灵连接”分配了资源浪费了内存和文件描述符。有了第三次握手客户端发现这个连接自己根本没发起过于是发送RST报文段告诉服务器撤销这个连接。这个知识点到今天依然是高频考点因为它背后体现的“网络环境不可靠任何协议设计都要考虑异常场景”的思维方式正是工程开发中十分需要的。2.2 操作系统题进程和线程的区别考察的不是定义D卷里还有一道关于进程和线程的题问的是“多线程一定能提高程序性能吗”。选项里给的几个解释都有点道理但最准确的表述是“不一定线程切换也有开销并且多线程访问共享资源会引入锁竞争”。我当时在这道题上就纠结了一会儿。因为教材上写“线程是CPU调度的基本单位创建和切换开销比进程小”很容易推出“多线程肯定比单线程快”的结论。但实际工程里如果你的任务是CPU密集型的计算线程数超过CPU核心数之后性能反而会下降因为线程上下文切换要保存和恢复寄存器状态、程序计数器等这些都需要时间。更何况多线程共享数据还要加锁锁竞争一旦激烈起来性能损耗比单线程串行执行还要大。这道题想考察的本质是你能不能跳出纸面概念结合真实的计算机运行机制去思考问题。说白了出题人想看你有没有在实际开发中因为线程切换和锁竞争吃过亏。2.3 C内存题栈上的对象到底谁在管理C相关题目里有一道考察栈对象生命周期的题让我印象很深。题目大概是问在函数内部直接创建一个对象不是用new当函数返回时会发生什么。答案不复杂栈对象会在函数退出时自动调用析构函数完成清理。但选项里混进了两个迷惑项一个是“需要手动调用delete才能释放”另一个是“对象会一直存活到程序结束”。这两个选项分别对应两种典型误解把栈对象和堆对象搞混以及混淆了静态变量的生命周期。这道题其实在暗示一个很重要的工程习惯能用栈对象就不用堆对象让RAII机制帮你管理资源。我在后来的C开发里见过太多因为堆对象忘记delete导致的内存泄漏所以看到这道题时特别有共鸣。它考的不是语法而是你在写代码时有没有资源管理的意识。3. 两道压轴算法题的完整推演要说这套卷子里最有含金量的部分还是手写算法题。这里挑两道比较典型的说一说一道是链表相关的一道是字符串相关的。它们共同的特点是看起来不难但实现起来处处是细节稍不留神就会翻车。3.1 单链表判断是否有环从O(n)空间到O(1)空间的演进这道题的题目描述我记得很清楚给定一个单链表的头节点判断链表中是否有环要求空间复杂度尽可能低。进阶要求是如果链表有环找出环的入口节点。最简单的做法是拿一个哈希表遍历链表时把每个节点地址存进去。如果某个节点的地址已经在哈希表里出现过说明有环。这个做法的空间复杂度是O(n)时间复杂度是O(n)正确性没毛病。但题目专门强调空间复杂度要低就说明面试官想听你说出快慢指针的解法。快慢指针的实现逻辑是维护一个慢指针slow和一个快指针fast初始都指向头节点。slow每次走一步fast每次走两步。如果链表无环fast会先遇到null遍历结束如果链表有环快慢指针最终一定会在环内相遇。但要真正理解这个算法不能只背结论得想清楚数学原理。假设链表头到环入口的距离是a环的长度是b两个指针在环内相遇时慢指针走了s步快指针走了2s步。因为快指针比慢指针多走了若干个环的长度所以有2s - s nb即s nb快指针总步数2s a x n*bx是在环内走的距离。此时slow已经走了ax步联立推一下就能得出从相遇点继续走a步即可回到环入口。写代码的时候有几个坑需要注意。第一个是循环条件必须同时检查fast和fast-next是否为null否则访问fast-next-next会触发空指针异常。第二个是空链表和单节点链表的边界情况要单独处理。第三个是找环入口时要重新用一个指针从头节点开始走和相遇点的slow指针一起一步一步移动两者相遇的位置就是环的入口。3.2 字符串全排列去重递归思路和剪枝细节另一道算法题是输出一个字符串的全排列但要求去掉重复结果。比如输入aab输出应该是aab、aba、baa三种排列而不是6种包含重复的排列。经典的解法是递归回溯法把字符串看成一个个可以交换位置的字符固定第一个字符递归求解剩下字符串的全排列。去重的关键在于在固定某个位置的字符之前要检查这个字符在这个位置是否已经出现过。如果出现过就跳过这次递归避免生成重复排列。我当时写这道题时第一版代码没有去重导致输出一堆重复结果。后来改成用一个set记录当前位置已经交换过的字符才把问题解决。还有一种做法是先把字符串排序然后在递归中跳过和前一个相同且前一个未被使用的字符——但这种方法需要额外维护一个visited数组写起来稍微复杂一些。这道题表面上考的是回溯算法实际上还考察了两个容易被忽视的细节一个是对重复元素处理的理解——不重不漏比单纯递归难得多另一个是递归时通过交换实现状态回溯的效率如果每次递归都新建子串会浪费大量内存。3.3 手写代码的评分标准除了正确还要看这些后来我参加笔试阅卷时注意到手写代码题不是只看最终能不能跑通还会关注你代码的结构和表达。同样的功能有的人写得一目了然有的人写得像一团乱麻。阅卷老师通常会看三点。第一是变量命名使用有意义的命名比如slow、fast、visitedSet会让代码的可读性提高很多第二是边界条件处理链表题对null的判断、对空字符串的判断这些细节直接反映一个工程师的严谨程度第三是代码的简洁性能用一个临时变量完成交换就别定义三个能不引入冗余的中间变量就别引入。所以如果你现在准备笔试我建议别只刷题要把每道题都当成正式的代码评审来对待——写完以后读一遍自己写的代码问问自己别人能不能一眼看懂有没有多余的重复逻辑这样练出来的代码水平才是面试官真正想看到的。4. 研发岗笔试的时间分配与答题策略这套D卷的考试时长我记得是90分钟题量不算小。从实战角度看时间分配是决定成败的关键因素之一。我当初就吃过亏在选择题上纠结太久导致后面的大题时间不够写出来的代码质量远不如平时水平。4.1 选择题要有时间上限一套笔试里的选择题通常是25道左右我给自己定的规则是每道选择题最多2分钟超过时间就先标记最后再回头处理。这样选择题最多花50分钟剩下的40分钟留给代码题和设计题。但到了真实考试中我发现“2分钟上限”执行起来是有难度的。因为总会遇到一两道让人纠结的题——选项看起来都对或者选项看起来都不对。这时候千万不能恋战凭第一感觉先选一个标记下来。后边的代码题分值占比更高每一行代码都可能拉开差距为了2分的选择题丢掉20分的代码题太亏了。4.2 代码题从暴力解写起手写代码题的正确打开方式是先想清楚最笨的解法把它写出来再逐步优化。如果你一上来就开始想最优解很容易卡在某个细节上写到最后发现时间不够了连暴力解都没写出来。我当年做单链表那道题时第一反应就是哈希表法因为最直观、最不容易写错。写完这个版本后我才开始想快慢指针的优化方案。这样即使后面的优化代码没写完前面也保住了基础分。阅卷老师看到你有正确的解法哪怕不是最优的也会给出基础分但如果你交上来的代码是残缺的那就很难给分了。另外写代码之前先把思路写在旁边。我习惯先写两三行注释说明自己的算法思路然后再写实现。这样即使代码有bug阅卷老师也能看出你是有思路的只是在实现上出了问题。一份有注释的残篇得分往往比一份没有注释的完整代码低不了多少但比什么都没写强太多了。4.3 设计题靠结构化表达拿分综合设计题的答题方式也有讲究。这类题一般没有唯一答案但你有条理地展开论述显然比想到哪写到哪更容易拿到高分。举个例子如果题目让你“设计一个短消息存储方案”你可以先说明数据量级假设比如日增消息上亿条然后聊存储选型关系型数据库还是NoSQL、索引设计按用户ID分表还是按时间分表、缓存层怎么加、冷热数据怎么分离。每一步都给出理由比如“按用户ID分表是因为读多写少用户查询自己的消息列表时能快速定位到对应的表”。我见过很多考生在设计题上写得像散文——东一句西一句没有结构。但如果你用“场景分析-技术选型-方案对比-优化策略”这样的框架来组织回答会显得思考更系统。不用背什么标准答案只要逻辑清晰能自圆其说分数通常都不会低。5. 从这套题反推当年社交产品的技术关注点一套笔试卷不只是考察知识的工具某种意义上也是公司技术团队的一面镜子。从人人网2015年这份D卷里其实能反推出当年社交类产品研发团队的一些核心关注点。5.1 高并发读写场景下的资源管理试卷反复出现的内存管理、指针生命周期、进程线程主题背后对应的是高并发服务器开发中的真实挑战。2015年前后的社交产品一个热点事件就能让系统流量瞬间飙升几倍在内存管理上稍有不慎就可能出现内存泄漏、服务崩溃等严重问题。这也是为什么当时的笔试题那么强调C基础——因为后端的核心服务往往是用C写的。Java有垃圾回收机制帮你兜底但C没有你必须清楚每一个new对应的delete每一个栈对象的作用域。现在的多数开发者可能没有这种顾虑了但在那个年代这确实是吃饭的本事。5.2 Feed流和时间线背后的数据组织试卷里的设计题很多本质上都在考察feed流和时间线场景下的数据组织能力。比如如何快速获取一个用户的好友动态列表、如何高效存储和查询关系链、如何在海量消息里做分页查询。这些问题的核心是数据如何合理分片、如何通过索引加速查询、如何在读写之间做权衡。我当时答类似题目时有一个很深的体会面试官真正想听的不是你会不会背某种数据结构的定义而是你能不能根据实际场景做技术选型。比如好友推荐你要想到可以用共同好友数作为相似度度量可以用哈希表存储好友关系可以用小顶堆取top-N结果。这些组合在一起才是一个完整的设计思路。5.3 基础扎实比框架熟练更重要这套卷子还有一个隐藏信息2015年的社交互联网公司招人时更看重基础而非框架熟练度。因为框架更新迭代太快今天流行的东西明年可能就过时了但数据结构、算法、操作系统、计算机网络这些基础十年二十年都不会变。很多人问我准备校招笔试到底要不要跟风学最新架构、最新框架。我的答案一直很一致可以了解但别主次颠倒。一套笔试卷里基础知识的比重通常超过一半。与其花三个月学一个还没普及的新框架不如花三个月把《算法导论》的经典章节吃透把剑指offer上的题刷熟。6. 一些关于技术面试的衍生想法的碎片聊完了这套具体题目最后再说一些关于技术面试本身的想法。这件事没有标准答案但有些经验是通用的。6.1 笔试反映的是平时积累不是突击成果我刷题那阵子见过很多同学平时代码写得很顺一到笔试就发挥失常。原因其实很简单笔试考的是你在没有IDE提示、没有搜索引擎、没有同事可以讨论的情况下独立解决问题的能力。平时如果习惯了复制粘贴、反复调试、看报错找答案骤然之间要你在纸上手写代码自然会不适应。所以我建议准备笔试的读者平时练习就要有意识地模拟真实考试环境。用白纸或者纯文本编辑器写代码不编译不调试写完以后对着代码一行行检查逻辑。刚开始会很不习惯甚至会发现自己连for循环的边界条件都会写错但坚持一段时间以后大脑的严谨性会明显提升。6.2 技术面试的本质是沟通很多人把笔试和面试理解为“做题”但它本质上还是一次沟通。考官通过你的解答来理解你的思维方式你在解答过程中展现的思路和表达能力有时候比答案本身还重要。特别是那些开放性的设计题和综合题你完全可以在作答时把自己的思考过程写出来甚至可以对着题目多问几个“如果”。比如“如果数据量再大十倍该怎么处理”“如果这个接口的响应时间要求是100毫秒以内该怎么做”。这些追问在阅卷时不会被扣分反而会让考官觉得你考虑问题周全工程素养过关。我在面试候选人的时候也更喜欢那些不只会给答案、还会解释为什么的人。因为实际工作中我们面对的问题大多没有标准答案而是需要在各种约束条件之间做权衡。你思考得越深入给出的方案就越经得起推敲。