搜狗研发笔试题精讲：从算法到C++与搜索技术的全面解析

搜狗2016研发工程师笔试题这份卷子我前两天翻出来重新过了一遍还是觉得挺有嚼头。当年在笔试现场做得手忙脚乱现在回头看其实很多题目的考点都是可以提前预判的。这套题覆盖了算法、C语言细节、操作系统、计算机网络还夹带了不少搜索业务相关的特色题目整体难度在互联网校招里算中上。对准备搜狗或是同类搜索公司研发岗位的同学来说这套题最有价值的不是题目本身而是它帮你划出了一张完整的能力地图哪些基本功必须扎实哪些地方最容易踩坑。我下面不打算按标准答案一条一条背而是把每类题背后的推理思路、常见错误、现场做题的时间估算一起讲清楚照着这个思路去准备会比机械刷题有效得多。下面按模块拆开说。1. 开考之前搜狗这套题到底在筛选什么样的人1.1 题目结构与考察定位先说整体结构。搜狗2016研发工程师笔试题大致分成四到五个板块算法与数据结构、C语言基础、操作系统与计算机网络、逻辑或数学题外加一小部分搜索和自然语言处理相关的业务题。和很多互联网公司不同搜狗这套题不是单纯堆算法难度而是把大量分数放在了语言细节和系统理解上这跟它的业务形态有直接关系。搜狗的核心产品是搜索引擎和输入法这两个业务都有非常高的性能和并发要求。搜索引擎要处理海量网页的抓取、分词、索引、排序输入法要做实时联想和用户词库管理这些场景都极度依赖对底层内存模型、进程通信、IO模型的理解。所以笔试题目很少出现“背一背八股文就能过”的情况更多是给你一个具体的代码片段或计算场景让你现场推导结果。这种出题思路带来的直接后果是靠刷题套路能拿到一部分分但不能覆盖全部。我见过不少同学在牛客网上刷了几百道LeetCode结果栽在C虚函数调用和内存对齐上也有算法能力一般但C底子很扎实的同学反而过了笔试。这不是巧合而是出题方有意在平衡筛选维度。1.2 现场做题的经验判断关于现场做题的顺序我个人的建议是先花五分钟把整张卷子扫一遍标注出哪些题能拿满分哪些题只能拿部分分哪些题直接放弃。然后按“先易后难、先代码后概念”的顺序做。算法题如果十分钟还没有完整思路就先跳过千万别卡死在上面因为后面C细节题基本都是读代码写输出的形式做起来很快属于性价比很高的分数。还有一个容易忽略的点是时间分配。整套卷子大约两小时题量在十到十五道之间平均每道题只有八到十二分钟。这意味着大部分题目并不要求你写出最优解而是要求你在限定时间内写出一个能正常工作的解并且把关键边界条件处理干净。笔试现场不是竞赛现场能稳定输出的才是赢家。提示准备这类笔试时一定要养成“限时做题”的习惯。很多人平时刷题能想出解法但一上考场就慌就是因为没有模拟过真实时间压力。2. 算法与数据结构四道高频题的正确打开方式2.1 链表带环检测快慢指针的边界控制这套题里的链表题目不算难但非常典型。例如判断单链表是否有环如果有环返回环的入口节点。核心解法是快慢指针快指针每次走两步慢指针每次走一步。如果链表有环快慢指针一定会在环内相遇。关于这个结论简单的理解是进入环之后快指针相对慢指针每次多走一步所以两者之间的距离会逐步缩短最终追上。这是数学上可以严格证明的现场答题时能说出这个推理过程会让阅卷人认为你真的理解而不是背了模板。找到相遇点之后找环入口的经典做法是将一个指针重新指向头节点另一个留在相遇点两者同步每次走一步再次相遇的位置就是环入口。这一步的原理可以通过数学推导得出但笔试现场不需要展开证明直接给出结论和代码就行。struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* detectCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; } } return nullptr; }这里有一个很容易踩的坑循环条件必须同时判断fast和fast-next非空否则访问空指针的next会直接崩溃。另外如果链表无环代码会正常返回nullptr不会进入死循环。笔试时如果时间充裕建议把无环、环入口在头节点、环在中间这三类情况在草稿纸上各画一遍确认代码没有逻辑漏洞。2.2 大数相乘竖式模拟背后的位映射大数相乘是搜狗这套题里的一个经典笔试题。题目一般是这样给定两个用字符串表示的非负整数返回它们的乘积结果也用字符串表示不能用编程语言自带的大数类型。这个问题的本质是模拟手工竖式乘法。思路不复杂num1的第i位从低位到高位编号和num2的第j位相乘结果会落在最终结果数组的i j位和i j 1位。具体规则是乘积的十位加到第i j位个位加到第i j 1位。这个位映射关系是整道题的灵魂理解了它代码就是一层循环套一层循环。string multiply(string num1, string num2) { int n1 num1.size(), n2 num2.size(); vectorint res(n1 n2, 0); for (int i n1 - 1; i 0; --i) { for (int j n2 - 1; j 0; --j) { int mul (num1[i] - 0) * (num2[j] - 0); int p1 i j; int p2 i j 1; int sum mul res[p2]; res[p2] sum % 10; res[p1] sum / 10; } } string ans; for (int v : res) { if (!(ans.empty() v 0)) { ans.push_back(v 0); } } return ans.empty() ? 0 : ans; }几个容易出错的地方。第一结果数组的长度是n1 n2不是n1 n2 - 1因为最高位可能产生额外进位。第二从低位开始遍历也就是从字符串末尾往前遍历这样才能保证进位方向正确。第三最后拼接字符串时要去掉前导零同时也得处理0 * 0这种特殊情况否则返回空串就错了。注意这道题在现场笔试时很多人会直接用stoi转换这在小数字用例下没问题但一旦数字超过int范围就直接翻车。看清题目要求别抢那几秒钟的偷懒时间。2.3 编辑距离动态规划的状态转移要这样想编辑距离是搜狗这类搜索公司十分偏爱的一道动态规划题。题目描述通常是给定两个字符串word1和word2每次可以对word1做三种操作——插入一个字符、删除一个字符、替换一个字符问最少需要多少次操作能把它变成word2。动态规划的状态定义是dp[i][j]表示word1的前i个字符转换为word2的前j个字符所需的最少操作数。状态转移从三个方向考虑插入word1前i个字符已经变成word2前j-1个字符再插入一个字符匹配word2[j]所以是dp[i][j-1] 1。删除word1前i-1个字符已经变成word2前j个字符把word1[i]删掉即可所以是dp[i-1][j] 1。替换word1前i-1个字符已经变成word2前j-1个字符再决定要不要替换当前字符。如果word1[i] word2[j]不需要操作否则加一次替换。int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; for (int i 1; i m; i) { for (int j 1; j n; j) { int insert dp[i][j - 1] 1; int remove dp[i - 1][j] 1; int replace dp[i - 1][j - 1] (word1[i - 1] word2[j - 1] ? 0 : 1); dp[i][j] min({insert, remove, replace}); } } return dp[m][n]; }以word1 horse、word2 ros为例最终输出结果是 3。整个 DP 表是二维的初始化时第一行和第一列必须分别赋值为 0 到行号或列号因为从空串变为任意字符串只能靠逐字符插入。笔试时建议大家把 DP 表亲手在草稿纸上填一遍这样能直观地看到状态转移的走向也能验证自己的边界条件是否正确。2.4 TopK问题海量数据场景下的搜索必备思维搜索公司笔试里几乎必考 TopK 问题搜狗这卷子也不例外。典型问法是有一百亿个查询词找出出现次数最多的前一百个。这个题在现场用手写代码实现完整的哈希统计不太现实但考官想听的就是一句话方案先哈希分桶统计频率再用大小为 K 的小顶堆维护 TopK。整体流程分两步。第一步用一个哈希表遍历所有数据统计每个元素的出现次数。第二步用一个大小为 100 的小顶堆扫描哈希表如果当前元素的频率比堆顶元素大就替换堆顶并调整堆。这样遍历完所有元素之后堆里剩下的就是出现次数最多的前 100 个。为什么一定要用小顶堆而不是大顶堆因为小顶堆保证堆顶是当前 TopK 中最小的元素只有比它大的才有资格进来。如果换成大顶堆堆顶是最大元素新元素很难进去维护不了 TopK。这个细节笔试时经常有人答反属于经典送分题。时间复杂度是O(N log K)空间复杂度是O(N)。如果数据量大到内存放不下可以先用哈希分片把大文件拆成多个小文件然后对每个小文件分别统计并取 TopK最后归并。归并时又能用到多路归并排序的思路。这些点能展开讲阅卷人会认为你有实战经验不是在背概念。3. C语言细节对象模型与内存管理里那些送分又送命的题3.1 虚函数与多态为什么基类指针调用的不是基类方法搜狗这套笔试题里C 部分最常见的出题形式是给你一段继承和虚函数的代码让你写出运行输出。这类题考察的不是语法记忆而是你是否真正理解虚函数表的机制。看一个经典例子class Base { public: virtual void f() { cout Base::f endl; } void g() { cout Base::g endl; } }; class Derived : public Base { public: void f() override { cout Derived::f endl; } void g() { cout Derived::g endl; } }; int main() { Base* p new Derived(); p-f(); p-g(); delete p; return 0; }输出结果是第一行Derived::f第二行Base::g。原因在于f是虚函数在编译时无法确定具体调用哪个版本运行时通过对象的虚函数表vtable查找所以基类指针指向派生类对象时会调用派生类的f而g是非虚函数编译器在编译期就根据指针的静态类型确定了调用Base::g不会发生动态绑定。更深一层每个含有虚函数的类对象内部都隐藏着一个虚函数表指针vptr在对象构造时被初始化指向所属类的虚函数表。这个机制是 C 实现多态的基石。笔试如果问“一个含有虚函数的类对象大小是多少”答案不是仅仅看成员变量还得加上一个 vptr在 64 位系统上是 8 字节。3.2 sizeof与内存对齐坑过无数人的结构体大小计算内存对齐这道题在搜狗笔试中出现过不止一次几乎每次都是给一个结构体让你算sizeof。题目本身不难但错误率极高主要原因是很多人没有掌握对齐规则。对齐规则有三条结构体的每个成员变量的偏移量必须是该成员对齐数的整数倍结构体的总大小必须是最大对齐数的整数倍每个成员的对齐数在默认情况下等于其自身大小也可以由编译器指令修改。看下面这个经典对比#include iostream using namespace std; struct A { char a; int b; char c; }; struct B { char a; char c; int b; }; int main() { cout sizeof(A) endl; // 12 cout sizeof(B) endl; // 8 return 0; }为什么同样的三个成员只是排列顺序不同sizeof(A)是 12 而sizeof(B)是 8因为struct A中char a占偏移 0int b必须从偏移 4 开始所以 a 后面浪费了 3 个字节char c占偏移 8整个结构体大小是 9还需补齐到最大对齐数 4 的倍数于是变成 12。而struct B中两个char连续占偏移 0 和 1int b从偏移 4 开始结构体总大小 8正好是 4 的倍数无需补齐。这个题在实战中的意义很大因为如果结构体被大量实例化浪费的内存会非常可观。搜索引擎里的索引项通常就是结构体数组一条记录多浪费几个字节乘以几亿条数据就是几个 GB 的内存差距。这也是为什么实际项目里经常会把结构体成员按大小从大到小排列。3.3 new与delete的匹配一条看不见的崩溃线C 题目里还有一个高频细节new[]必须用delete[]释放new必须用delete释放。别以为这只是在考语法实际工作中很多人在这上面栽过跟头。原因要从对象数组的内存布局说起。当你写new Derived[n]时编译器申请的内存块前面通常会额外记录对象个数n这样才能在delete[]时知道要调用多少次析构函数。如果你用delete去释放new[]出来的内存析构次数对不上轻则内存泄漏重则堆损坏、程序崩溃。反过来delete[]一个new出来的对象也是一样的危险。笔试时如果只给出代码而不运行判断标准很简单凡是用了[]的分配就要用[]的释放没有[]的分配就用普通的delete。如果类里没有析构函数错误匹配可能不会立刻崩溃但一旦有析构函数且类里有动态分配的资源系统就会在运行时给你颜色看。注意面试时如果被问到智能指针相关题可以顺带说明shared_ptr和unique_ptr能自动解决这种匹配问题。搜狗这类公司对现代 C 使用是有要求的能主动提出智能指针是加分项。4. 操作系统与计算机网络会背概念不等于会做题4.1 进程间通信方式一张表理清适用场景搜狗笔试的操作系统部分进程间通信是常客。题目一般给一个业务场景让你选合适的通信方式或者让你对比各种方式的优缺点。这类题光背概念不行得理解每种方式的底层机制和适用边界。下面是我在备考时整理的对比表可以直接拿来当索引通信方式底层机制优点缺点典型场景管道内核缓冲区实现简单、天然同步半双工、只能用于亲缘进程父子进程命令传参消息队列内核消息链表有消息边界、支持随机读取消息大小受限、需要拷贝服务间异步消息共享内存映射同一块物理内存传输速度最快、零拷贝需要自己处理同步互斥大规模数据交换信号量计数器等待队列解决进程同步和互斥不擅长传数据多进程共享资源保护Socket网络协议栈支持跨主机通信开销大、延迟高分布式系统跨机器调用笔试如果遇到“两个进程需要频繁交换大量数据怎么选”这样的题答案是共享内存但要补充一句“同时配合信号量做互斥”这样才能体现你考虑问题全面。搜狗的业务里搜索服务不同模块之间的通信经常就是共享内存加信号量的组合所以这种题并非纯理论是有真实业务背景的。4.2 页面置换算法LRU的手算推演操作系统部分有一类计算题很能拉分就是页面置换算法。给你一个页面走向序列给定内存块数要求计算缺页次数。以 LRU最近最久未使用为例页面走向是1 2 3 4 1 2 5 1 2 3 4 5内存块数为 3。缺页情况我直接列成表访问页内存状态按最近使用排序是否缺页1[1]是2[1, 2]是3[1, 2, 3]是4[2, 3, 4]是淘汰11[3, 4, 1]是淘汰22[4, 1, 2]是淘汰35[1, 2, 5]是淘汰41[2, 5, 1]命中2[5, 1, 2]命中3[1, 2, 3]是淘汰54[2, 3, 4]是淘汰15[3, 4, 5]是淘汰2最终缺页次数为 9 次。整个过程的关键是“内存状态按最近访问时间排序”每次淘汰最久没被访问的页面。这个手算过程在笔试时至少能帮你拿一半分数因为阅卷人能看到你理解了 LRU 的淘汰逻辑。4.3 TCP四次挥手与TIME_WAIT连接关闭不只是状态机计算机网络部分搜狗比较爱考的 TCP 连接关闭流程尤其关注 TIME_WAIT 状态。题目可能直接问主动关闭方在发送最后一个 ACK 之后为什么要等 2MSL 才进入 CLOSED 状态标准答案包含两层原因。一是保证最后这个 ACK 能到达被动关闭方如果 ACK 丢失被动关闭方会重发 FIN主动关闭方收到后还能再发 ACK二是防止本次连接中的旧数据包残留到新连接中因为 2MSL 之后所有旧数据包都已经在网络中消失。这个机制在搜索服务器里非常重要服务器作为主动关闭方时如果大量短连接快速建立又关闭会出现大量 TIME_WAIT 连接堆积占用本地端口和内存。我还记得有一道题是问“TIME_WAIT 过多怎么办”当时我答的是调整系统参数net.ipv4.tcp_tw_reuse和net.ipv4.tcp_tw_recycle但这需要谨慎使用因为复用 TIME_WAIT 连接可能导致旧数据串扰。更稳妥的方式是让客户端主动关闭连接或者用长连接池减少短连接数量。能答到这一层说明你不是只会背状态机的学生。5. 搜索特色题倒排索引、TF-IDF与中文分词实战5.1 倒排索引的构建与合并把流程讲清楚就赢了一半搜狗作为搜索引擎公司笔试里一定会出现搜索特色题。倒排索引是搜索中最基础的数据结构常见出题方式有两种一种是给你几篇文档让你写出最终的倒排表另一种是给两个已经排好序的倒排表让你写出归并过程。第一种题很简单。例如有三篇文档文档1搜狗输入法很好用文档2搜狗搜索很快文档3输入法搜索都很好经过分词后倒排索引就长这样词项倒排列表搜狗文档1, 文档2输入法文档1, 文档3搜索文档2, 文档3很好文档1, 文档3第二种题考察合并效率。两个倒排列表都是升序的用双指针归并每次比较两个指针指向的文档 ID相等则输出结果并同时右移不相等则移动较小的那个。这个思路和归并排序一模一样但很多人现场会忘记倒排列表已经排好序这个前提写成双重循环导致复杂度变成O(m*n)。在搜索引擎的海量文档集合里这个复杂度是完全不可接受的。5.2 TF-IDF计算为什么高频词不等于关键词相关性排序里TF-IDF 是必考概念。题目会给一个小的文档集合要求手算某个词的 TF-IDF 值然后说明它在排序中的作用。TF-IDF 的计算公式是词频乘以逆文档频率。逆文档频率的典型公式是IDF log(N / df)其中 N 是文档总数df 是包含该词的文档数。如果某个词在所有文档中都出现df 等于 NIDF 等于 0这个词对区分文档没有任何贡献反之如果一个词只在少数几篇文档里出现IDF 就高说明它更有区分度。举一个具体例子。假设有 4 篇文档“搜狗”在 4 篇都出现df4IDFlog(4/4)0所以即使“搜狗”在单篇文档里的词频很高它的 TF-IDF 仍然是 0。而“输入法”只出现 1 篇df1IDFlog(4/1)≈1.386如果这个词在文档里出现 2 次TF2那 TF-IDF≈2.77。这正好解释了为什么搜索引擎处理查询时会忽略“的”“了”这类停用词因为它们在全库文档中太常见IDF 无限接近零。笔试现场算这个题容易忽略的是对数的底数通常用自然对数 e 或 2 都行关键是公式的形态要写对。如果你能补充说“实际工业界还会做平滑处理防止除零”说明你不是只懂教科书。5.3 中文分词正向最大匹配的简单实现中文分词是搜索和输入法都要处理的问题搜狗笔试也考过。一个简单题目是给定一个词典和一句话用正向最大匹配算法进行分词。正向最大匹配的思路很朴素从句子开头取一个最大长度比如 4 个字符的候选词如果词典里有这个词就切出来如果没有就把候选词长度减 1 再查直到长度为 1 或者命中词典。def forward_max_match(text, dictionary, max_len4): result [] while text: length min(max_len, len(text)) word text[:length] while length 1 and word not in dictionary: length - 1 word text[:length] result.append(word) text text[length:] return result dictionary {搜狗, 输入法, 搜索, 很好, 好用, 很好用, 很, 快, 都} print(forward_max_match(搜狗输入法很好用, dictionary)) # 输出[搜狗, 输入法, 很好用]这道题其实很简单但有两个细节值得展开。第一词典里如果同时有“很好”和“很好用”最大匹配会优先切出更长的“很好用”这是符合人类阅读习惯的第二如果句子中有未登录词最大匹配最终会把单字也切出来这说明基于词典的分词无法解决新词问题。你在笔试时如果能顺带说明这个缺陷并提一句更高级的统计分词方法会显得更有深度。6. 交卷后的复盘从一套笔试题到一套知识体系6.1 我在笔试后总结的三条教训第一审题比做题更重要。我当年在编辑距离那道题上踩过一个坑题目允许的三种操作是插入、删除、替换但我一开始只看了一个“编辑距离”的标题就开始默写代码写的是只允许替换的版本。交卷之后才反应过来。搜索类公司的题目往往在题目描述里隐藏了关键限制条件比如“非负整数”“不包含空格”“内存足够放下所有数据”等这些条件直接决定解法。第二概念一定要能推导不能只背结论。比如 LRU 淘汰算法你不仅要会写代码还要能在草稿纸上徒手推演缺页次数。再比如死锁的四个必要条件我见过有人背得滚瓜烂熟但换个问法“系统中有多个同类型资源给出一种死锁的银行家算法判定过程”就完全不知道从哪里下手。搜狗这套题里很多概念题都会包装成代码判断或计算场景如果只背定义拿到题会非常被动。第三代码的边界条件必须形成肌肉记忆。空指针判断、字符串越界、数组长度是否为 0、整数溢出这些是笔试批改时最容易被扣分的地方。很多题目你能写出核心逻辑但因为没处理空串输入、没判断链表为空的场景直接被扣掉 20% 甚至一半的分数。我的做法是每次写完代码都强迫自己列出三组测试用例空输入、单元素输入、正常输入用这三组用例在脑子里快速走一遍代码。6.2 从这套题反推出来的备考路线如果你想以搜狗 2016 这套卷子的标准来检验自己我建议按下面的优先级去准备。算法部分重点刷链表、树、动态规划、字符串、TopK 这几类题。参考书可以看《剑指 Offer》和 LeetCode 前 100 道热门题关键是每道题都不止写一遍过两天要重新独立写出来这才能真正检验自己是否掌握。语言部分C 要重点看虚函数表机制、内存对齐、const和static的作用、new/delete与malloc/free的区别。想深入可以读《深入探索C对象模型》如果时间不够至少要把常见的类继承输出题做明白。系统与网络推荐读《深入理解计算机系统》的虚拟内存和异常控制流章节以及《计算机网络自顶向下方法》的传输层章节。这两块的笔试题目都比较模式化把概念和计算题练熟就能拿到大部分分数。搜索特色题主要理解倒排索引的构建过程、TF-IDF 的计算公式、中文分词的两种基本实现。不要只停留在概念自己在电脑上写一个小程序用一个简单的文档集合走一遍倒排索引的构建流程理解会比看十遍书都深。我自己在实际准备过程中的体会是这套题放在今天依然是衡量一个后端或搜索引擎方向研发工程师基本功的好题目。搜索和输入法这一类业务对底层知识的深度要求一直没变。你不需要把每道题的答案背下来而是要把每个考点背后的机制弄明白这样不管题目怎么变你都能找到切入点。最后再分享一个小技巧考前把你整理的知识点做成一份能自己默写出来的思维导图过一遍就上考场比临时翻题库有效得多。