搜狗2016研发工程师笔试题全解析：覆盖校招笔试高频考点

每年校招季都会有不少同学翻出往年大厂的笔试真题来练手。搜狗2016年的这套研发工程师笔试题虽然已经过去多年但里面的考察点放到现在依然是面试高频区进程线程、TCP状态机、排序稳定性、二叉树遍历、动态规划、桶排序思想……几乎每道题都能在现在的笔试卷子里找到影子。这篇文章我会按当年的真题形式把常考的知识点逐一拆开讲清楚每道编程题都会给出完整的解题思路和可运行的代码顺带分享一些笔试时的时间分配和避坑经验。适合正在准备校招笔试、或者想系统补一补算法和计算机基础的研发岗同学参考。1. 这套笔试题在考什么题型结构与设计思路解析1.1 整体题型分布与考察维度搜狗2016研发工程师笔试题的大致结构和当时大多数互联网公司的研发岗笔试保持了一致前面是30道左右的选择题覆盖计算机基础四个大类——操作系统、计算机网络、数据结构与算法、编程语言与数据库后面是2到3道编程题按难度梯度排列第一题偏基础、后面逐步加难。选择题的分布比例很能说明问题。我当时统计过同类试卷操作系统和网络部分大概占到35%左右数据结构和算法约30%剩下的就是语言特性和数据库。这个配比不是随便定的它反映的是研发工程师日常工作中的知识消耗结构写业务代码时数据库和语言逃不掉排查线上问题时操作系统和网络的底层知识决定你能否快速定位而算法则是区分候选人思维水平的硬指标。有意思的是这套题的选择题部分有不少“陷阱题”比如排序算法的稳定性判断、TCP三次握手过程中状态名的变化、C虚函数的动态绑定机制。这类题目表面考记忆实际上考的是你有没有真正理解底层原理。我在后面会单独用一节来拆这些高频考点。1.2 为什么这样出题面试官到底想看什么笔试作为校招的第一道筛选关卡它的核心目的不是看你“会不会”而是看你在有限时间内“能做出什么”。出题人在设计这套题时本质上是在做三轮筛选。第一轮筛基础扎实度。选择题里的计算机网络和操作系统题目都是教科书级别的知识点但越基础的题目越能拉开差距。比如TCP三次握手为什么是三次而不是两次这种问题背过八股的人都能答上来但当它换个角度、放进一个具体的状态迁移场景里很多人就懵了。这就是在筛选真正理解原理的人而不是靠死记硬背的。第二轮筛代码实现能力。有两道左右编程题考察的不只是你会不会某个算法而是你能否在笔试环境中快速写出无bug的代码。很多同学平时在IDE里写代码很流畅一放到笔试的在线编辑器里就各种问题忘记处理输入输出、边界条件考虑不全、循环变量写错。笔试环境是有时间压力和心态干扰的能把代码一步写对本身就说明平时的代码功底是扎实的。第三轮筛思维深度。编程题里有一道比较典型的桶排序应用它在考察你对“时间复杂度”的理解是否到位。常规排序能做到O(nlogn)但题目要求O(n)这就要求你跳出排序的固有思路想到桶的思想。这种题考查的不是排序本身而是你能否根据题目限制反向设计算法这是研发岗位非常需要的一种能力。2. 核心知识点逐个击破选择题背后的高频考点2.1 操作系统与网络进程线程、TCP状态机先看操作系统。搜狗这套题里进程和线程的区别是必考的但出题角度往往很刁钻。比如给你四个选项分别描述进程和线程在地址空间、资源开销、调度方式、共享数据上的区别让你选出“错误”的一项。很多人会记混进程是资源分配的基本单位线程是CPU调度的基本单位进程拥有独立的地址空间同一进程的线程共享地址空间。这些核心点只要记住基本就能快速排除干扰项。还有一个高频考点是死锁产生的四个必要条件互斥、持有并等待、不可剥夺、循环等待。题目经常会给出一个场景比如“某系统中有5个进程和3类资源问是否可能发生死锁”这种题需要你结合资源分配图来判断。我当时复习的窍门是遇到死锁题先画出资源分配图如果存在循环等待链再检查前三个条件是否满足全部满足才可能死锁。网络部分TCP状态机是绕不开的。搜狗试题里有一道很经典的题TCP连接建立过程中客户端和服务器分别经历了哪些状态。客户端是SYN_SENT到ESTABLISHED服务器是LISTEN到SYN_RCVD再到ESTABLISHED。很多同学会把SYN_RCVD和SYN_SENT记反。与其硬背不如理解握手过程客户端先发SYN所以它进入SYN_SENT服务器收到SYN后回复SYNACK这时它处于SYN_RCVD表示“我收到了你的同步请求”客户端再回ACK双方进入ESTABLISHED。这样按流程推一遍状态名就记住了。2.2 数据结构与算法排序稳定性、二叉树遍历排序算法是选择题里的常客但很少直接问你“快排的时间复杂度是多少”而是问你“以下哪种排序算法是稳定的”。稳定的排序有插入排序、冒泡排序、归并排序和基数排序不稳定的有选择排序、希尔排序、快速排序和堆排序。如果只是背结论很容易混我建议从原理上去理解稳定性指的是相等元素的相对顺序在排序后保持不变。快排为什么不稳定因为分区的过程中pivot会和远处的元素交换位置可能把相等的元素换到彼此的另一侧。而归并排序在合并两个有序序列时只要遇到相等元素优先取左侧分区的元素就能保证稳定。二叉树遍历也是必考点。题目一般会给你一个前序遍历和中序遍历的结果让你推出后序遍历或者是让你判断某棵二叉树属于哪种类型。这种题没有捷径需要你对三种遍历方式的重建过程非常熟练。我自己的方法是“前序定根、中序分左右”前序遍历的第一个节点就是根节点拿着根节点去中序遍历里找位置左边是左子树、右边是右子树然后递归处理。这个方法用在选择题上几乎秒杀所有“已知两种遍历求第三种”的题。2.3 编程语言与数据库虚函数、索引原理搜狗当年主要用C所以C相关的考点集中在这几个地方虚函数的动态绑定机制、构造函数和析构函数的调用顺序、const的用法、指针和引用的区别。虚函数这题比较有代表性它会问你“在基类构造函数中调用虚函数会发生什么”很多人想当然认为会多态调用派生类的实现但实际上构造函数中虚函数不会触发动态绑定它只能调用当前类的版本。原因在于构造派生类对象时基类先构造此时派生类部分还没初始化虚函数表的指针指向的是基类的虚函数表。数据库方面索引的原理和优化是必考的。有一类题目是这样的给一个SQL查询语句问它在什么情况下用不上索引。常见的坑包括对索引列使用了函数运算、前导模糊查询、隐式类型转换、联合索引没遵循最左前缀原则。还有一个容易忽略的是“非等值查询导致索引失效”比如在索引列上用了!或者IS NOT NULL大多数数据库优化器可能选择全表扫描。遇到这类题我的经验是从B树的结构出发去推索引为什么高效因为它是有序的所以范围查询和等值查询都能快速定位一旦破坏了有序性比如加了函数运算B树就无能为力了只能走全表扫描。3. 编程题实战拆解完整思路与可跑通代码3.1 第一题基于“桶思想”的相邻最大差值问题先来看一道很有代表性的题它来自考生回忆版本题干大概是给定一个无序数组求排序之后相邻两个数的最大差值要求时间复杂度O(n)且不能用非比较排序。第一反应肯定是先排序再遍历但快排O(nlogn)不满足要求。题目这个限制条件其实是在暗示你不能全局排序必须另辟蹊径。这里就要引入“桶”的思想了。思路是这样数组有n个元素我准备n1个桶。先遍历一遍数组找到最大值max和最小值min。然后把这些数均匀地映射到n1个桶里每个桶的区间长度是(max-min)/(n1)。因为桶的数量比元素数量多1所以至少有一个桶是空的。这个空桶的存在保证了一个关键性质排序后相邻两数的最大差值一定不会出现在同一个桶内部而是出现在跨越空桶的两个桶之间。所以我们只需要记录每个桶的最大值和最小值然后依次扫描相邻的非空桶计算后一个桶的min减去前一个桶的max取最大值即可。#include vector #include iostream #include algorithm using namespace std; struct Bucket { bool used false; int minVal INT_MAX; int maxVal INT_MIN; }; int maxGap(vectorint nums) { int n nums.size(); if (n 2) return 0; int minNum *min_element(nums.begin(), nums.end()); int maxNum *max_element(nums.begin(), nums.end()); if (maxNum minNum) return 0; vectorBucket buckets(n 1); double interval (double)(maxNum - minNum) / n; for (int num : nums) { // 计算当前数属于哪个桶注意边界情况 int idx (int)((num - minNum) / interval); if (idx n 1) idx n; // 防止最大值越界 buckets[idx].used true; buckets[idx].minVal min(buckets[idx].minVal, num); buckets[idx].maxVal max(buckets[idx].maxVal, num); } int result 0; int prevMax buckets[0].maxVal; for (int i 1; i n 1; i) { if (buckets[i].used) { result max(result, buckets[i].minVal - prevMax); prevMax buckets[i].maxVal; } } return result; }这里有个细节要注意空桶可能连续出现多个所以扫描时要跳过所有空桶只比较相邻的非空桶。另外interval的求法用的是double如果直接用整数除法会丢失精度可能导致最大值落到错误的桶里。这两个坑我在面试别人的时候经常看到有人踩笔试时能一次避开说明代码素养不错。第一题考完第二个编程题通常是一道经典的动态规划题比如最长公共子串或最小编辑距离。这类题目万变不离其宗核心是状态定义和状态转移方程。以最长公共子串为例它要求子串在原字符串中是连续的所以dp[i][j]的定义是“以text1[i]和text2[j]结尾的最长公共子串长度”两个字符相等时dp[i][j] dp[i-1][j-1] 1不相等时直接归零因为连续性断了。这里和最长公共子序列的区别一定要搞清楚子序列允许跳过字符所以不相等时dp[i][j] max(dp[i-1][j], dp[i][j-1])而子串不相等时只能清零。3.2 第二题最长公共子串的动态规划套路这里直接写一个完整实现注释我写得比较详细方便直接照抄。#include vector #include string #include iostream using namespace std; string longestCommonSubstring(string a, string b) { int m a.size(), n b.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); int maxLen 0, endPos 0; for (int i 1; i m; i) { for (int j 1; j n; j) { if (a[i - 1] b[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; if (dp[i][j] maxLen) { maxLen dp[i][j]; endPos i - 1; // 记录最长子串的结束位置 } } // 不相等时dp[i][j]保持0表示以i,j结尾的公共子串不存在 } } return a.substr(endPos - maxLen 1, maxLen); }看到没有动态规划题其实写起来代码量不大难的是状态定义。这一题的时候要注意dp数组的宽度是n1多出来的一行一列是为了方便处理边界让i-1和j-1在i1或j1时不会越界。这个技巧在几乎所有二维DP题里都适用算是套路的默认配置。笔试里动态规划的题目通常不会只考一个裸的公共子串而是会加一点变形。比如要求输出最长公共子串本身而不是长度或者把字符串换成一个句子、按单词判断公共子序列。遇到变形别慌底层逻辑不变状态定义稍微调整一下就能套用。我见过一个同学在笔试时碰到变体就直接放弃了挺可惜的其实只要能把动态规划的核心思想掌握变体题大多数只是换了一件马甲。3.3 第三题二叉树的层序遍历与变体编程题的第三题往往会考二叉树相关的操作层序遍历是一个经典方向。给定一棵二叉树要求按层遍历并输出每一层的节点。常规做法是用队列出队一个节点就把它的左右子节点入队。这个思路大家都会但笔试的坑在于“按层输出”也就是需要你把每一层的节点单独放在一个数组里而不是简单打平输出。#include vector #include queue using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (!root) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); // 关键先记录当前层的节点数 vectorint level; for (int i 0; i levelSize; i) { TreeNode* cur q.front(); q.pop(); level.push_back(cur-val); if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } result.push_back(level); } return result; }这里的核心技巧是levelSize q.size()这一步。因为在遍历当前层的过程中队列会不断加入新的节点如果不提前记录一层的节点数量就没法判断什么时候该结束这一层。这个变量很多人写的时候容易漏漏掉的后果就是输出结果全部混在一起在笔试的在线评测系统里直接就WA了。层序遍历的变体也很常见比如“之字形遍历”也就是第一层从左到右、第二层从右到左交替输出。实现起来也不复杂加一个深度的奇偶判断偶数层正常从左到右奇数层把结果反转一下就行。还有一种变形是从底向上按层输出处理方式是把levelOrder的结果最后整体反转。掌握了基础版本这些变体基本是送分题。4. 笔试过程中的时间分配与答题节奏4.1 选择题限时训练与取舍策略整套卷子的时间一般是一个半小时到两个小时选择题虽然只占一部分分值但最好不要超过总时间的三分之一。我给自己定的规矩是30道选择题最多40分钟平均每题一分钟多一点。遇到拿不准的题先标记一下不要恋战立刻跳到下一题。笔试的时间分布往往是编程题用时更多选择题如果卡住了后面的编程题就会很被动。有一个比较实用的取舍策略选择题里计算量大或者需要画图推理的题先放一放比如资源分配图的死锁判断、复杂递归的调用栈分析这类题目一旦卡住就会耗掉好几分钟。先做简单的概念题把自己有把握的分拿到手再回来啃硬骨头。其实笔试的及格线通常不是满分甚至不是高分只要保证基础题的对率在85%以上把中档题做对一半编程题过两道基本就能稳进面试。我自己在准备阶段会做大量的限时训练用的就是历年真题规定自己在45分钟内完成整套选择题然后对答案。对完答案不是结束而是开始每一道错题都要写错因分析是概念混淆、计算失误、还是读题不仔细。把错因归类之后你会发现很多题目的错误原因是同一个集中补一下就能消除大部分失分点。4.2 编程题从读题到AC的标准流程编程题的做题节奏其实是固定的我总结了一个“四步走”流程实测在笔试环境下非常稳。第一步读题时拿笔圈出三个信息输入规模、输出格式、时间复杂度要求。输入规模决定了你能用什么复杂度的算法比如n在10万级别O(n²)的算法基本没有活路n在1000以内O(n²)可以放心用。输出格式决定了你怎么处理边界值比如输出字符串时要不要考虑空串。第二步先想暴力解再想优化解。笔试时如果一时间想不出最优解先把暴力解写出来保底然后在暴力解的基础上逐步优化不要空想着一步到位。比如前面说的相邻最大差值问题如果想不到桶排序可以先写一个排序遍历的版本拿部分分再考虑优化到O(n)。很多同学有一个误区就是觉得非最优解不配写代码其实笔试是按测试用例给分的部分正确的版本能拿到不少分总比空着强。第三步动手写代码前在注释里列出关键步骤。比如“先遍历数组找max和min”“然后分桶”“再扫描空桶”。这相当于给自己的思路搭了一个骨架写正文代码的时候不容易漏步骤边写边对照注释也能及时发现逻辑漏洞。第四步写完代码一定要自己构造测试用例来验证。白送的测试点要测边界条件更要测空数组、只有一个元素、元素全相等、最大值是INT_MAX、输入字符串长度相差很大等等。这一步能帮你拦住至少30%的隐藏错误。我还见过有人忘记处理输入里有多余空格的情况在线评测系统不会帮你擦屁股的输入格式错了就是错了。5. 常见错误与避坑指南5.1 边界条件和输入输出细节笔试最容易翻车的不是算法本身而是边界条件。我受过的教训太多了第一数组越界。用C写代码时经常会因为循环变量的起点或终点写错一位导致访问到nums[n]或者nums[-1]在在线评测环境里这会造成运行时错误直接判0分。第二空输入。题目虽然不一定会给空用例但好的代码习惯是函数入口先判断空的情况比如if (a.empty() || b.empty()) return 0;一行代码就能避免很多奇怪的错误。第三整形溢出。数组元素范围较大的时候(max - min)本身可能超出int的范围需要先用long long接住再做运算我见过不少人在这一步漏了类型转换导致计算结果变成奇怪的负数。输入输出的坑也值得单独提一下。笔试在线环境通常用标准输入输出如果题目涉及多行输入要特别注意读入方式。比如C里用cin读取字符串时遇到空格就会断开如果需要读取一行含空格的字符串要用getline(cin, s)。还有如果输入行前面有空白行cin会跳过它们但getline不会这会导致错位读取。建议拿到题目先看一眼输入格式是每行一个整数、还是逗号分隔、还是空格分隔再选对应的读取方式。5.2 复杂度超标的常见原因很多时候你写了一版“感觉没问题”的代码但提交后卡了超时这时候要回头审视自己的复杂度。最常见的超标原因是把O(n)的操作放进了O(n)循环里导致整体变成O(n²)而不自知。比如在循环体里使用vector的insert在头部插入元素这个操作本身是O(n)的放在循环里就变成O(n²)。换成push_back再加reverse整体就能降到O(n)。另一个隐藏很深的复杂度超标原因是重复计算。比如在计算前缀和时每次循环都重新累加一遍从0到i的所有元素而不是保存一个s[i] s[i-1] a[i]的递推值。这个问题在笔试中特别容易出现在“区间查询”类型的题目里如果你发现自己的代码有个地方重复扫描了一个数组就要警惕是否可以通过预处理来优化。还有一类超时问题出在C的输入输出上。如果题目数据量大cin和cout的同步开销是相当可观的。遇到大数据量输入在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);这个动作一般能提升不少输入效率。这不是什么高级技巧但在笔试环境下输入数据可能是几百万行这点优化有时候就是AC和TLE之间的差别。5.3 系统化备战建议有些人准备笔试喜欢刷“题海”一天刷二十道但效率其实很低。我更推荐按知识点分类刷题每天只攻一个方向比如今天是动态规划专题就只刷5道不同类型的DP题每道题做完都要写思路复盘。这样一周下来你就把主干知识点都过了一遍而且每个方向都有一定深度的积累。复盘的具体写法是这道题考的是什么算法状态定义是什么转移方程怎么写为什么这样定义我在哪一步卡住了能不能把这道题的思路迁移到另一道题上你如果每道题都能回答这五个问题说明这题是真的吃透了而不是单纯“会做”。另外一定要在笔试环境里做模拟。很多同学习惯在本地IDE里写代码写得行云流水但一上笔试系统就不行了。笔试系统没有自动补全、没有颜色高亮、不能随便调试这些都需要提前适应。我当时考前一周每天都用一个在线OJ做一场模拟笔试完全按照正式笔试的时间限制和节奏来最终在正式笔试时的状态明显比那些没模拟过的同学要好。根据我个人的经验校招笔试这套东西本质上是个熟练度游戏。你不需要是天才能手只要把高频考点和常见题型刷到“肌肉记忆”的程度在考场上看到题目就能条件反射地想到思路笔试这一关就能稳稳过去。最后再分享一个小技巧平时做题时给自己留一个“错误笔记”每道错题记录下来考前专门翻错题本比从头刷一遍题效率高得多。