1. 整体考情与设计思路为什么搜狗笔试总爱考这些搜狗2016研发工程师笔试题二放到今天回头看依旧很有嚼头。那几年移动互联网正值爆发期搜索、输入法、浏览器是搜狗的三驾马车研发岗位的笔试题目自然带着强烈的搜索引擎公司基因——看重基础、看重算法复杂度、看重候选人能不能用工程化思维解决海量数据问题。整套笔试题二的整体结构基本延续了那几年互联网公司校招笔试的经典模块划分选择题覆盖数据结构、操作系统、网络、语言基础主观题集中在算法设计与系统设计。如果你经历过那个年代的笔试应该会有印象——题量不小时间很紧很多选择题属于会就是会不会只能蒙的类型。和现在的笔试相比当年的题目更少出现偏门的新技术考点更多是在考察计算机基本功的扎实程度。搜狗笔试二的设计逻辑其实很典型用有限的时间筛出基础扎实、思路清晰、能写代码的候选人。搜索引擎业务对研发的要求很直接你要能在海量网页里快速检索你要能处理高并发查询你要能保证系统的稳定性和响应速度。所以笔试题里频繁出现的字符串处理、TopK问题、哈希设计、缓存淘汰策略本质上都是在模拟搜索引擎和输入法场景下最真实的工程问题。从岗位能力模型来看搜狗这套笔试题二重点考察三个维度的能力第一个是基础功底。数据结构、操作系统、网络协议这些计算机核心知识决定了这个候选人能不能在复杂的工程问题里快速定位根源。搜狗做搜索底层要处理的是大规模索引和实时检索这些全靠扎实的数据结构和系统知识撑着。第二个是算法思维。搜索引擎和输入法里到处是算法的影子排序、匹配、推荐、纠错。笔试题里那些看起来很竞赛的算法题其实都是业务场景抽象出来的最小模型。第三个是工程敏感度。题目里涉及的时间复杂度分析、空间换时间思想、系统设计题中的可扩展性问题都在考察候选人有没有生产环境意识——你写出来的代码不是在一台只有几万条数据的笔记本上跑通就行的。如果你现在准备大厂研发岗笔试这套旧题依然是很好的练手材料。因为不管技术栈怎么迭代核心考察点没有本质变化。2. 数据结构与算法笔试中的硬骨头2.1 字符串类题目的通用解法思路搜狗笔试二里字符串相关的题目出镜率很高。这并不意外——搜索的关键词匹配、输入法的拼音串处理、浏览器的URL解析全是字符串操作。这类题目的典型考法我总结为三种子串查找与匹配、字符串变换、字符串统计。子串查找往往不是让你直接写KMP而是给你一个特定的业务场景让你设计高效的匹配方案。比如给定一个长文本和一组敏感词要求找出所有匹配位置。这类题考的不是KMP本身能不能背出来而是你有没有意识到朴素匹配在数据量上来以后会爆炸。我的建议是笔试遇到字符串题先用三分钟想清楚这几件事数据规模有多大允许多少时间空间开销有没有可能用哈希预处理的思路把问题转化成能不能用字典树或者能不能用滑动窗口。搜索场景里字典树简直是万能答案——输入法纠错要字典树关键词提示要字典树词频统计的变体也常和字典树挂钩。字符串变换类题目常见的有反转、去重、压缩、按规则解析。这类题大部分是考你边界条件想得全不全。比如反转字符串但不反转单词内部顺序你就要想清楚空格的分隔规则比如删除字符串中重复字符你要考虑保留第一次出现的还是最后一次出现的。很多人在笔试里挂掉真不是不会做而是边界条件没写对。空串、单个字符、全是重复字符——这些用例一定要在草稿纸上先跑一遍。2.2 链表题为什么总考不腻链表在笔试里的地位可以用经典永流传来形容。搜狗笔试题二里链表题目几乎必考而且难度通常控制在中低档目的就是快速筛掉那些背题背答案的人。链表题的核心考点其实只有三个指针操作、遍历技巧、空间复杂度控制。反转链表、合并有序链表、找中间节点、判断是否有环本质上都是在考你对指针操作的熟练度。拿反转链表举例。迭代法的标准解法是三个指针prev、current、next每次循环做一次局部反转然后整体前进。很多人能背出来但笔试要求手写的时候还是会栽在什么时候更新prev循环终止条件是什么这种细节上。我建议链表题统一用画图推演的方法来复习。找一个简单的例子比如1-2-3-4-5把每一步的指针变化画出来多练几个变种按k个一组反转、反转区间、从后往前数第n个节点。画图推演练熟了现场手写就不容易慌。再说说链表题的一个进阶考法不借助额外空间完成操作。比如判断链表是否有环空间复杂度O(1)的标准解法是快慢指针比如判断两个链表是否相交可以先把两个链表长度求出来然后让长链表先走差值步。这类题目练习的时候一定要给自己加约束不允许开数组、不允许用哈希表。你平时练习越约束笔试现场越从容。2.3 从一道TopK题看复杂度优化思维搜狗笔试题二的选择题和编程题里TopK问题出现过不止一次。这也是搜索业务里非常真实的需求——热词排行榜、热门网页排序本质都是TopK。TopK的标准解法你必须熟练掌握的有三种第一种是全局排序适用于数据量小、能一次性装入内存的场景。时间复杂度O(n log n)代码简单直接。但笔试题目如果给了海量数据内存有限这样的关键词全局排序基本就是错误答案。第二种是堆排序法。维护一个大小为K的小顶堆遍历一遍数据碰到比堆顶大的就替换并调整堆。时间复杂度O(n log K)当K远小于n时性能非常可观。这个解法是TopK问题的默认答案笔试必须能秒写。第三种是快速选择算法。基于快速排序的partition思想平均时间复杂度O(n)。不过这个解法在工程上用得相对少因为最坏情况下会退化到O(n^2)而且本身是不稳定的部分排序在某些场景有限制。笔试中如果你对partition非常熟练可以写这个解法展示功力否则堆排序更稳妥。有意思的是搜狗笔试题二里的TopK很多时候不是直接问求前K大而是套一个业务壳。比如给定用户的查询日志统计最热门的10个搜索词。这里面其实考了两个层次第一层日志文件太大不能一次性读入内存怎么办——分治把大文件哈希到多个小文件里分别统计。第二层每个小文件里怎么统计词频——哈希表计数再对每个小文件取局部TopK最后合并。这类题目如果你的思路能走到分治哈希堆三层组合面试官基本能确认你是真的理解海量数据处理而不只是背过模板。3. 操作系统与网络笔试不能丢的分3.1 进程线程与内存管理高频考点操作系统这块搜狗笔试题二考察得比较收敛但很爱考那些看似简单实则暗藏陷阱的知识点。比如进程和线程的区别很多人的理解停留在进程是资源分配单位线程是CPU调度单位但题目一加深问你进程内多个线程共享什么不共享什么就有人开始迷糊了。线程共享进程的地址空间、打开的文件、信号处理函数等不共享的是栈、寄存器状态、线程局部存储。笔试选择题很喜欢在这个点上做文章把共享堆但不共享栈这种说法混在选项里。内存管理是操作系统题目里的重头戏。搜狗这类搜索引擎公司对内存管理敏感度要求很高因为搜索引擎的索引结构就是典型的内存换性能设计。笔试里最常见的是页面置换算法FIFO、LRU、LFU、Clock。LRU是必考的而且经常延伸到让你设计一个LRU缓存要求get和put都是O(1)时间复杂度这时候要用哈希表加双向链表来解。这道题建议所有投研发岗的人都练到肌肉记忆不管笔试还是面试出现频率都极高。死锁的条件也是选择题常客。互斥、持有并等待、不可剥夺、循环等待四个条件缺一不可。考法通常是给你一段描述让你判断是否会产生死锁或者问你破坏哪个条件能解决死锁。搜狗笔试题二里有一类典型的银行家算法安全性判断题目虽然是经典考题但说实话工程实践里很少手算笔试时不要浪费时间硬推先看选项能否用排除法。3.2 网络协议栈题目实战思路网络协议这块搜狗笔试题二的考点很集中TCP三次握手和四次挥手、TCP与UDP的区别、HTTP协议基础。这和公司业务是强相关的——搜索引擎要爬取海量网页抓取调度系统要维护大量TCP连接客户端要和服务端高效通信这些都跑在协议栈上面。三次握手是个必考点但比背状态码更重要的是理解为什么是三次而不是两次。原因在于TCP需要让双方确认彼此的收发能力都正常。两次握手的话服务端无法确认客户端的接收能力是否正常也无法防止客户端失效的连接请求突然到达服务端导致的资源浪费。四次挥手的考点会更细比如TIME_WAIT状态出现在哪一端、为什么会存在这个状态、主动关闭方为什么要等2MSL。搜狗笔试在这个点上做过文章答案是保证最后一个ACK能够到达对方以及让本连接内的所有报文在网络中消失避免干扰新连接。这个点能答清楚说明你真的理解TCP协议设计背后的意图而不只是背了个流程图。HTTP的考法在2016年前后开始变得灵活不再只考状态码含义还会结合场景问你输入URL到页面展示发生了什么。这其实是一道综合题涉及DNS解析、TCP连接、HTTP请求发送、服务端处理、响应返回、浏览器渲染。搜狗笔试题二的选择题里如果出现这个通常不会要你完整描述全链路而是在某个环节上挖细节比如DNS用的是TCP还是UDP——查询阶段用UDP区域传送用TCP。4. 编程语言与数据库细节决定成败4.1 C与Java必考易错点搜狗作为搜索引擎和客户端软件公司C和Java是笔试选择题的重灾区。C题目风格偏向基础但极爱考易错点Java题目则更偏向容器和并发。C里最常见的考点是指针和引用、const的各种用法、内存管理。指针和引用的区别基本每套笔试都有指针是变量存储地址可以重新赋值引用是别名必须在定义时初始化之后不能改变指向。很多人平时用着没感觉但选择题一旦考察函数参数传递方式对实参的影响就暴露了。const的考法更是层出不穷。const指针和指针const我教大家一个土办法看const和的先后关系const在左边修饰的是指向的对象const在*右边修饰的是指针本身。笔试时遇到这类题先把这个关系写下来再判断选项能省很多时间。内存管理考的是new/delete、malloc/free的区别以及内存泄漏的成因。搜狗笔试题二里出现过构造函数和析构函数中能不能调用虚函数这个经典问题——答案是能调用但不会发生多态行为因为派生类还没构造完成或已经析构。这个点几乎每个C笔试都爱考建议务必记住。Java这边集合类是重点。HashMap在2016年左右的笔试里还是个线程不安全但高效的考点考点集中在扩容机制、哈希冲突处理、和Hashtable的区别。现在很多题目开始考ConcurrentHashMap的分段锁机制和CAS操作但当年的搜狗笔试二整体还偏基础重点放在HashMap的底层原理上。String、StringBuilder、StringBuffer三者的区别也是高频考题。记住一个口诀String不可变StringBuilder线程不安全但快StringBuffer线程安全但慢。如果选择题里问字符串拼接大量数据用什么首选StringBuilder。4.2 数据库索引与SQL优化考察方式数据库在搜狗研发工程师笔试中一定有位置因为搜索业务背后全是数据存储和查询——网页库、用户画像、日志系统哪哪都是数据库。索引这块B树索引是标准答案。你不需要背一堆B树的性质但要理解几个关键点为什么用B树而不是B树或者红黑树因为B树非叶子节点不存数据单节点能容纳更多关键字树更矮磁盘IO次数更少因为叶子节点通过指针串成链表范围查询效率极高。笔试选择题里最常见的索引考法是给定一个SQL问走了哪个索引/能否命中索引。核心判断依据是联合索引遵守最左前缀原则。比如(a,b,c)联合索引查询条件里只有b没有a索引就用不上。这是搜狗这类笔试选择题的经典陷阱。另一个高频考点是聚簇索引和非聚簇索引的区别。聚簇索引的叶子节点存的是整行数据一张表只能有一个非聚簇索引的叶子节点存的是主键值查询时要回表。如果题目再深一步问覆盖索引是什么——就是查询的列都在索引里不需要回表。这个知识点在笔试选择题里出现一次你就赚了一次。SQL优化题在笔试里通常给一个慢SQL场景让你分析原因并给出优化方案。常见思路无非是先看是否全表扫描考虑加索引看是否存在隐式类型转换导致索引失效看是否用了select *能不能改成覆盖索引看是否在索引列上做了函数运算。笔试题不会给你真实的执行计划但你给出的优化方向要条理清晰能踩中关键点。搜狗笔试题二里的SQL题虽然占比不大但属于送分题基础扎实的考生很容易拿满。5. 系统设计与开放性题目的答题套路5.1 搜索引擎相关模块的设计思路搜狗笔试题二的主观题部分容易出现和搜索业务强相关的开放性题目。这类题目没有标准答案但也不是凭感觉乱写考察的是你能否用工程化思维拆解复杂系统。典型的考法比如设计一个搜索引擎的查询建议suggest系统或者设计一个短网址系统或者设计一个输入法的联想词库更新机制。我的经验是系统设计题要按固定套路答不管题目是什么都遵循需求分析→容量预估→模块划分→存储设计→核心流程→扩展性考虑这个框架。以查询建议系统为例。需求分析阶段你要明确这是当用户输入前缀时返回热门查询补全的功能核心指标是低延迟和准确性。容量预估阶段假设日活用户千万级搜索量上亿你需要估算QPS、存储量给出一个大概的数字范围不用精确但要有量级概念。模块划分阶段核心服务是查询补全服务。存储设计是重点——这里要用到字典树或者倒排索引的变体。为了追求速度热门前缀和对应的补全列表通常常驻内存可以做多级缓存最热门的直接放本地内存次热门的放分布式缓存冷数据才查全量索引。核心流程描述起来要清晰用户输入前缀→请求到达网关→查本地缓存→未命中查分布式缓存→再未命中查全量索引→结果合并排序→返回Top N。最后扩展到如果数据量翻十倍怎么办答案方向是水平扩展、分片存储、数据预计算、异步更新索引。你能把思路完整走一遍即使没有给出特别精细的方案面试官也会认可你具备系统设计的底层素养。5.2 海量数据处理题的一般性解题框架除了系统设计题搜狗笔试题二里还常出现海量数据处理类的问答题。比如给定一个100GB的文件每行一个整数如何找到出现次数最多的Top100这种题考察的思路和系统设计题高度重叠——分治哈希堆是万能钥匙。我总结了一套海量数据处理题的六步法分享给大家第一步判断数据规模和数据形态。100GB的整数文件显然不能一次性加载到内存所以第一步必须分治。第二步设计分片策略。哈希分片是最通用的一招对每个整数取hash再对分片数取模把大文件拆成多个小文件。这里有个细节就是尽量让数据均匀分布避免某个分片特别大否则单分片也处理不动。第三步对小文件用内存内方法处理。每个小文件用哈希表统计词频内存足够时间也就是O(n)。第四步从每个小文件中提取局部TopK。这时候用堆排序每个文件输出局部最热的K个词。第五步多路归并。把所有分片的局部TopK汇总到一起再一次排序得到全局TopK。第六步验证和兜底。如果题目还要求精确统计还是近似统计精确就按上面的流程做近似的话可以考虑Count-Min Sketch这类概率数据结构但笔试题一般不会要求到这一步。这套框架不仅适用于词频统计凡是超大文件找出TopK的题型都可以直接套用。你在笔试前把这几步练熟遇到同类题就能做到条件反射式作答。6. 常见问题与排查技巧实录6.1 笔试时间分配策略搜狗笔试题二这类试卷我印象里题量不小有些选择题特别耗时间。很多考生折戟不是不会做而是时间分配出了问题——花太多时间纠结一道难题导致后面的编程题没时间写。我建议的时间分配策略是这样的拿到试卷先花两三分钟快速浏览全部题目把题目分成秒杀题一看就知道答案、思考题需要计算或推理和放弃题完全没思路。秒杀题直接做不要反复检查越检查越容易改错。思考题每题给自己设定一个时间上限比如3到5分钟超过上限先标记跳过最后有时间再回头。放弃题坚决不纠结随便蒙一个选项走人——笔试选择题答错不扣分蒙一个还有概率对。编程题永远放在最前面做。原因很简单编程题分值高且阅卷是人工看的只要你的思路正确、代码基本能跑就算部分测试用例没过也能拿到大部分分数。选择题蒙对一道也就一分的差别但编程题差一个档次就是五到八分的差距。答题顺序我推荐编程题→思考题→秒杀题→放弃题但考前确认一下试卷规则如果选择题多且分值高也可以调整为秒杀题快速扫一遍→编程题集中做→思考题→放弃题。关键是不要被单个难题拦住脚步。6.2 读题偏差最常见的丢分方式我见过太多人笔试挂掉不是因为知识点不会而是因为读题不仔细答非所问。搜狗笔试题二里也有这类陷阱。典型场景一题目说写一个函数返回第K大的数。有人直接写了个排序然后返回对应位置看起来好像没错但如果题目要求的时间复杂度有约束或者明确说不能使用库函数排序那你的解法就是零分。读题的时候先把限制条件圈出来时间复杂度要求、空间复杂度要求、能否用库函数、输入是否有序、是否能修改原数组这些都要在动手前确认。典型场景二题目要求返回所有可能的结果你却只返回了一个。所有这个词一出现大概率是回溯算法或动态规划不是贪心也不是二分。看到所有就条件反射想到递归搜索这是笔试题读题的第一个直觉。典型场景三题目里给的变量范围暗示了解法思路。比如数组长度小于10那O(n!)的暴力搜索可能都能过比如数组长度达到10^6那O(n^2)的解法基本会超时。数据范围是笔试题给你的最诚实的提示一定要充分利用。还有一个小技巧编程题如果可以用多个函数拆分尽量拆出来写。一方面代码逻辑清晰另一方面万一某个函数写错了阅卷也能看出你的思路不至于整体全扣。6.3 笔试前一周的复盘与实战技巧最后分享一点笔试前一周的复习经验。我之前备战搜狗这类公司笔试时最后一周做的不是大量刷新题而是做三件事啃透错题、限时模拟、整理模板。限时模拟很重要。很多人的问题是会做但做不快限时模拟是唯一能模拟现场紧张感的方式。建议严格按考试时间来做整套卷子中间不能中断不能查资料写完再统一对答案。练两三套完整的卷子手感就出来了。平时做题一定要做总结不能做完就扔。我会用一个表格整理错题重点记录三列题目考点、我的错误点、正确思路。题目考点错误原因正确思路LRU缓存设计哈希双向链表用了数组模拟双向链表维护访问顺序字符串全排列回溯去重忘记去重排序后剪枝联合索引选择最左前缀原则判断反了缺左列则索引失效另一些笔试经验通常不会写进文档但我实际验证下来很有效。比如笔试现场如果有本地IDE 在线监控的模式不要试图用本地IDE的自动补全功能来弥补代码不熟练的问题——在线答题系统的代码格式、输入输出处理一定要提前熟悉否则会浪费大量时间在调试环境上。再比如说笔试时遇到原题不要高兴太早因为题目可能改了某个条件——我遇到过把升序改成降序、把数组改成链表的情况。越是觉得眼熟的题越要重新读一遍题干。用搜狗2016研发工程师笔试题二来练手你不需要把每一道题都做对——笔试题本身就是用来拉开差距的能拿到六成到七成的分数就已经很有竞争力了。我个人的体会是相比刷题量复盘质量才是笔试能力提升的关键。同一道题你做对了但能讲出为什么用这个解法而不是另一个和做对了但只会背答案差距会在后续的系统设计题和面试环节里彻底拉开。 搜狗2016研发工程师笔试题解析：核心考点与笔试备战指南
1. 整体考情与设计思路为什么搜狗笔试总爱考这些搜狗2016研发工程师笔试题二放到今天回头看依旧很有嚼头。那几年移动互联网正值爆发期搜索、输入法、浏览器是搜狗的三驾马车研发岗位的笔试题目自然带着强烈的搜索引擎公司基因——看重基础、看重算法复杂度、看重候选人能不能用工程化思维解决海量数据问题。整套笔试题二的整体结构基本延续了那几年互联网公司校招笔试的经典模块划分选择题覆盖数据结构、操作系统、网络、语言基础主观题集中在算法设计与系统设计。如果你经历过那个年代的笔试应该会有印象——题量不小时间很紧很多选择题属于会就是会不会只能蒙的类型。和现在的笔试相比当年的题目更少出现偏门的新技术考点更多是在考察计算机基本功的扎实程度。搜狗笔试二的设计逻辑其实很典型用有限的时间筛出基础扎实、思路清晰、能写代码的候选人。搜索引擎业务对研发的要求很直接你要能在海量网页里快速检索你要能处理高并发查询你要能保证系统的稳定性和响应速度。所以笔试题里频繁出现的字符串处理、TopK问题、哈希设计、缓存淘汰策略本质上都是在模拟搜索引擎和输入法场景下最真实的工程问题。从岗位能力模型来看搜狗这套笔试题二重点考察三个维度的能力第一个是基础功底。数据结构、操作系统、网络协议这些计算机核心知识决定了这个候选人能不能在复杂的工程问题里快速定位根源。搜狗做搜索底层要处理的是大规模索引和实时检索这些全靠扎实的数据结构和系统知识撑着。第二个是算法思维。搜索引擎和输入法里到处是算法的影子排序、匹配、推荐、纠错。笔试题里那些看起来很竞赛的算法题其实都是业务场景抽象出来的最小模型。第三个是工程敏感度。题目里涉及的时间复杂度分析、空间换时间思想、系统设计题中的可扩展性问题都在考察候选人有没有生产环境意识——你写出来的代码不是在一台只有几万条数据的笔记本上跑通就行的。如果你现在准备大厂研发岗笔试这套旧题依然是很好的练手材料。因为不管技术栈怎么迭代核心考察点没有本质变化。2. 数据结构与算法笔试中的硬骨头2.1 字符串类题目的通用解法思路搜狗笔试二里字符串相关的题目出镜率很高。这并不意外——搜索的关键词匹配、输入法的拼音串处理、浏览器的URL解析全是字符串操作。这类题目的典型考法我总结为三种子串查找与匹配、字符串变换、字符串统计。子串查找往往不是让你直接写KMP而是给你一个特定的业务场景让你设计高效的匹配方案。比如给定一个长文本和一组敏感词要求找出所有匹配位置。这类题考的不是KMP本身能不能背出来而是你有没有意识到朴素匹配在数据量上来以后会爆炸。我的建议是笔试遇到字符串题先用三分钟想清楚这几件事数据规模有多大允许多少时间空间开销有没有可能用哈希预处理的思路把问题转化成能不能用字典树或者能不能用滑动窗口。搜索场景里字典树简直是万能答案——输入法纠错要字典树关键词提示要字典树词频统计的变体也常和字典树挂钩。字符串变换类题目常见的有反转、去重、压缩、按规则解析。这类题大部分是考你边界条件想得全不全。比如反转字符串但不反转单词内部顺序你就要想清楚空格的分隔规则比如删除字符串中重复字符你要考虑保留第一次出现的还是最后一次出现的。很多人在笔试里挂掉真不是不会做而是边界条件没写对。空串、单个字符、全是重复字符——这些用例一定要在草稿纸上先跑一遍。2.2 链表题为什么总考不腻链表在笔试里的地位可以用经典永流传来形容。搜狗笔试题二里链表题目几乎必考而且难度通常控制在中低档目的就是快速筛掉那些背题背答案的人。链表题的核心考点其实只有三个指针操作、遍历技巧、空间复杂度控制。反转链表、合并有序链表、找中间节点、判断是否有环本质上都是在考你对指针操作的熟练度。拿反转链表举例。迭代法的标准解法是三个指针prev、current、next每次循环做一次局部反转然后整体前进。很多人能背出来但笔试要求手写的时候还是会栽在什么时候更新prev循环终止条件是什么这种细节上。我建议链表题统一用画图推演的方法来复习。找一个简单的例子比如1-2-3-4-5把每一步的指针变化画出来多练几个变种按k个一组反转、反转区间、从后往前数第n个节点。画图推演练熟了现场手写就不容易慌。再说说链表题的一个进阶考法不借助额外空间完成操作。比如判断链表是否有环空间复杂度O(1)的标准解法是快慢指针比如判断两个链表是否相交可以先把两个链表长度求出来然后让长链表先走差值步。这类题目练习的时候一定要给自己加约束不允许开数组、不允许用哈希表。你平时练习越约束笔试现场越从容。2.3 从一道TopK题看复杂度优化思维搜狗笔试题二的选择题和编程题里TopK问题出现过不止一次。这也是搜索业务里非常真实的需求——热词排行榜、热门网页排序本质都是TopK。TopK的标准解法你必须熟练掌握的有三种第一种是全局排序适用于数据量小、能一次性装入内存的场景。时间复杂度O(n log n)代码简单直接。但笔试题目如果给了海量数据内存有限这样的关键词全局排序基本就是错误答案。第二种是堆排序法。维护一个大小为K的小顶堆遍历一遍数据碰到比堆顶大的就替换并调整堆。时间复杂度O(n log K)当K远小于n时性能非常可观。这个解法是TopK问题的默认答案笔试必须能秒写。第三种是快速选择算法。基于快速排序的partition思想平均时间复杂度O(n)。不过这个解法在工程上用得相对少因为最坏情况下会退化到O(n^2)而且本身是不稳定的部分排序在某些场景有限制。笔试中如果你对partition非常熟练可以写这个解法展示功力否则堆排序更稳妥。有意思的是搜狗笔试题二里的TopK很多时候不是直接问求前K大而是套一个业务壳。比如给定用户的查询日志统计最热门的10个搜索词。这里面其实考了两个层次第一层日志文件太大不能一次性读入内存怎么办——分治把大文件哈希到多个小文件里分别统计。第二层每个小文件里怎么统计词频——哈希表计数再对每个小文件取局部TopK最后合并。这类题目如果你的思路能走到分治哈希堆三层组合面试官基本能确认你是真的理解海量数据处理而不只是背过模板。3. 操作系统与网络笔试不能丢的分3.1 进程线程与内存管理高频考点操作系统这块搜狗笔试题二考察得比较收敛但很爱考那些看似简单实则暗藏陷阱的知识点。比如进程和线程的区别很多人的理解停留在进程是资源分配单位线程是CPU调度单位但题目一加深问你进程内多个线程共享什么不共享什么就有人开始迷糊了。线程共享进程的地址空间、打开的文件、信号处理函数等不共享的是栈、寄存器状态、线程局部存储。笔试选择题很喜欢在这个点上做文章把共享堆但不共享栈这种说法混在选项里。内存管理是操作系统题目里的重头戏。搜狗这类搜索引擎公司对内存管理敏感度要求很高因为搜索引擎的索引结构就是典型的内存换性能设计。笔试里最常见的是页面置换算法FIFO、LRU、LFU、Clock。LRU是必考的而且经常延伸到让你设计一个LRU缓存要求get和put都是O(1)时间复杂度这时候要用哈希表加双向链表来解。这道题建议所有投研发岗的人都练到肌肉记忆不管笔试还是面试出现频率都极高。死锁的条件也是选择题常客。互斥、持有并等待、不可剥夺、循环等待四个条件缺一不可。考法通常是给你一段描述让你判断是否会产生死锁或者问你破坏哪个条件能解决死锁。搜狗笔试题二里有一类典型的银行家算法安全性判断题目虽然是经典考题但说实话工程实践里很少手算笔试时不要浪费时间硬推先看选项能否用排除法。3.2 网络协议栈题目实战思路网络协议这块搜狗笔试题二的考点很集中TCP三次握手和四次挥手、TCP与UDP的区别、HTTP协议基础。这和公司业务是强相关的——搜索引擎要爬取海量网页抓取调度系统要维护大量TCP连接客户端要和服务端高效通信这些都跑在协议栈上面。三次握手是个必考点但比背状态码更重要的是理解为什么是三次而不是两次。原因在于TCP需要让双方确认彼此的收发能力都正常。两次握手的话服务端无法确认客户端的接收能力是否正常也无法防止客户端失效的连接请求突然到达服务端导致的资源浪费。四次挥手的考点会更细比如TIME_WAIT状态出现在哪一端、为什么会存在这个状态、主动关闭方为什么要等2MSL。搜狗笔试在这个点上做过文章答案是保证最后一个ACK能够到达对方以及让本连接内的所有报文在网络中消失避免干扰新连接。这个点能答清楚说明你真的理解TCP协议设计背后的意图而不只是背了个流程图。HTTP的考法在2016年前后开始变得灵活不再只考状态码含义还会结合场景问你输入URL到页面展示发生了什么。这其实是一道综合题涉及DNS解析、TCP连接、HTTP请求发送、服务端处理、响应返回、浏览器渲染。搜狗笔试题二的选择题里如果出现这个通常不会要你完整描述全链路而是在某个环节上挖细节比如DNS用的是TCP还是UDP——查询阶段用UDP区域传送用TCP。4. 编程语言与数据库细节决定成败4.1 C与Java必考易错点搜狗作为搜索引擎和客户端软件公司C和Java是笔试选择题的重灾区。C题目风格偏向基础但极爱考易错点Java题目则更偏向容器和并发。C里最常见的考点是指针和引用、const的各种用法、内存管理。指针和引用的区别基本每套笔试都有指针是变量存储地址可以重新赋值引用是别名必须在定义时初始化之后不能改变指向。很多人平时用着没感觉但选择题一旦考察函数参数传递方式对实参的影响就暴露了。const的考法更是层出不穷。const指针和指针const我教大家一个土办法看const和的先后关系const在左边修饰的是指向的对象const在*右边修饰的是指针本身。笔试时遇到这类题先把这个关系写下来再判断选项能省很多时间。内存管理考的是new/delete、malloc/free的区别以及内存泄漏的成因。搜狗笔试题二里出现过构造函数和析构函数中能不能调用虚函数这个经典问题——答案是能调用但不会发生多态行为因为派生类还没构造完成或已经析构。这个点几乎每个C笔试都爱考建议务必记住。Java这边集合类是重点。HashMap在2016年左右的笔试里还是个线程不安全但高效的考点考点集中在扩容机制、哈希冲突处理、和Hashtable的区别。现在很多题目开始考ConcurrentHashMap的分段锁机制和CAS操作但当年的搜狗笔试二整体还偏基础重点放在HashMap的底层原理上。String、StringBuilder、StringBuffer三者的区别也是高频考题。记住一个口诀String不可变StringBuilder线程不安全但快StringBuffer线程安全但慢。如果选择题里问字符串拼接大量数据用什么首选StringBuilder。4.2 数据库索引与SQL优化考察方式数据库在搜狗研发工程师笔试中一定有位置因为搜索业务背后全是数据存储和查询——网页库、用户画像、日志系统哪哪都是数据库。索引这块B树索引是标准答案。你不需要背一堆B树的性质但要理解几个关键点为什么用B树而不是B树或者红黑树因为B树非叶子节点不存数据单节点能容纳更多关键字树更矮磁盘IO次数更少因为叶子节点通过指针串成链表范围查询效率极高。笔试选择题里最常见的索引考法是给定一个SQL问走了哪个索引/能否命中索引。核心判断依据是联合索引遵守最左前缀原则。比如(a,b,c)联合索引查询条件里只有b没有a索引就用不上。这是搜狗这类笔试选择题的经典陷阱。另一个高频考点是聚簇索引和非聚簇索引的区别。聚簇索引的叶子节点存的是整行数据一张表只能有一个非聚簇索引的叶子节点存的是主键值查询时要回表。如果题目再深一步问覆盖索引是什么——就是查询的列都在索引里不需要回表。这个知识点在笔试选择题里出现一次你就赚了一次。SQL优化题在笔试里通常给一个慢SQL场景让你分析原因并给出优化方案。常见思路无非是先看是否全表扫描考虑加索引看是否存在隐式类型转换导致索引失效看是否用了select *能不能改成覆盖索引看是否在索引列上做了函数运算。笔试题不会给你真实的执行计划但你给出的优化方向要条理清晰能踩中关键点。搜狗笔试题二里的SQL题虽然占比不大但属于送分题基础扎实的考生很容易拿满。5. 系统设计与开放性题目的答题套路5.1 搜索引擎相关模块的设计思路搜狗笔试题二的主观题部分容易出现和搜索业务强相关的开放性题目。这类题目没有标准答案但也不是凭感觉乱写考察的是你能否用工程化思维拆解复杂系统。典型的考法比如设计一个搜索引擎的查询建议suggest系统或者设计一个短网址系统或者设计一个输入法的联想词库更新机制。我的经验是系统设计题要按固定套路答不管题目是什么都遵循需求分析→容量预估→模块划分→存储设计→核心流程→扩展性考虑这个框架。以查询建议系统为例。需求分析阶段你要明确这是当用户输入前缀时返回热门查询补全的功能核心指标是低延迟和准确性。容量预估阶段假设日活用户千万级搜索量上亿你需要估算QPS、存储量给出一个大概的数字范围不用精确但要有量级概念。模块划分阶段核心服务是查询补全服务。存储设计是重点——这里要用到字典树或者倒排索引的变体。为了追求速度热门前缀和对应的补全列表通常常驻内存可以做多级缓存最热门的直接放本地内存次热门的放分布式缓存冷数据才查全量索引。核心流程描述起来要清晰用户输入前缀→请求到达网关→查本地缓存→未命中查分布式缓存→再未命中查全量索引→结果合并排序→返回Top N。最后扩展到如果数据量翻十倍怎么办答案方向是水平扩展、分片存储、数据预计算、异步更新索引。你能把思路完整走一遍即使没有给出特别精细的方案面试官也会认可你具备系统设计的底层素养。5.2 海量数据处理题的一般性解题框架除了系统设计题搜狗笔试题二里还常出现海量数据处理类的问答题。比如给定一个100GB的文件每行一个整数如何找到出现次数最多的Top100这种题考察的思路和系统设计题高度重叠——分治哈希堆是万能钥匙。我总结了一套海量数据处理题的六步法分享给大家第一步判断数据规模和数据形态。100GB的整数文件显然不能一次性加载到内存所以第一步必须分治。第二步设计分片策略。哈希分片是最通用的一招对每个整数取hash再对分片数取模把大文件拆成多个小文件。这里有个细节就是尽量让数据均匀分布避免某个分片特别大否则单分片也处理不动。第三步对小文件用内存内方法处理。每个小文件用哈希表统计词频内存足够时间也就是O(n)。第四步从每个小文件中提取局部TopK。这时候用堆排序每个文件输出局部最热的K个词。第五步多路归并。把所有分片的局部TopK汇总到一起再一次排序得到全局TopK。第六步验证和兜底。如果题目还要求精确统计还是近似统计精确就按上面的流程做近似的话可以考虑Count-Min Sketch这类概率数据结构但笔试题一般不会要求到这一步。这套框架不仅适用于词频统计凡是超大文件找出TopK的题型都可以直接套用。你在笔试前把这几步练熟遇到同类题就能做到条件反射式作答。6. 常见问题与排查技巧实录6.1 笔试时间分配策略搜狗笔试题二这类试卷我印象里题量不小有些选择题特别耗时间。很多考生折戟不是不会做而是时间分配出了问题——花太多时间纠结一道难题导致后面的编程题没时间写。我建议的时间分配策略是这样的拿到试卷先花两三分钟快速浏览全部题目把题目分成秒杀题一看就知道答案、思考题需要计算或推理和放弃题完全没思路。秒杀题直接做不要反复检查越检查越容易改错。思考题每题给自己设定一个时间上限比如3到5分钟超过上限先标记跳过最后有时间再回头。放弃题坚决不纠结随便蒙一个选项走人——笔试选择题答错不扣分蒙一个还有概率对。编程题永远放在最前面做。原因很简单编程题分值高且阅卷是人工看的只要你的思路正确、代码基本能跑就算部分测试用例没过也能拿到大部分分数。选择题蒙对一道也就一分的差别但编程题差一个档次就是五到八分的差距。答题顺序我推荐编程题→思考题→秒杀题→放弃题但考前确认一下试卷规则如果选择题多且分值高也可以调整为秒杀题快速扫一遍→编程题集中做→思考题→放弃题。关键是不要被单个难题拦住脚步。6.2 读题偏差最常见的丢分方式我见过太多人笔试挂掉不是因为知识点不会而是因为读题不仔细答非所问。搜狗笔试题二里也有这类陷阱。典型场景一题目说写一个函数返回第K大的数。有人直接写了个排序然后返回对应位置看起来好像没错但如果题目要求的时间复杂度有约束或者明确说不能使用库函数排序那你的解法就是零分。读题的时候先把限制条件圈出来时间复杂度要求、空间复杂度要求、能否用库函数、输入是否有序、是否能修改原数组这些都要在动手前确认。典型场景二题目要求返回所有可能的结果你却只返回了一个。所有这个词一出现大概率是回溯算法或动态规划不是贪心也不是二分。看到所有就条件反射想到递归搜索这是笔试题读题的第一个直觉。典型场景三题目里给的变量范围暗示了解法思路。比如数组长度小于10那O(n!)的暴力搜索可能都能过比如数组长度达到10^6那O(n^2)的解法基本会超时。数据范围是笔试题给你的最诚实的提示一定要充分利用。还有一个小技巧编程题如果可以用多个函数拆分尽量拆出来写。一方面代码逻辑清晰另一方面万一某个函数写错了阅卷也能看出你的思路不至于整体全扣。6.3 笔试前一周的复盘与实战技巧最后分享一点笔试前一周的复习经验。我之前备战搜狗这类公司笔试时最后一周做的不是大量刷新题而是做三件事啃透错题、限时模拟、整理模板。限时模拟很重要。很多人的问题是会做但做不快限时模拟是唯一能模拟现场紧张感的方式。建议严格按考试时间来做整套卷子中间不能中断不能查资料写完再统一对答案。练两三套完整的卷子手感就出来了。平时做题一定要做总结不能做完就扔。我会用一个表格整理错题重点记录三列题目考点、我的错误点、正确思路。题目考点错误原因正确思路LRU缓存设计哈希双向链表用了数组模拟双向链表维护访问顺序字符串全排列回溯去重忘记去重排序后剪枝联合索引选择最左前缀原则判断反了缺左列则索引失效另一些笔试经验通常不会写进文档但我实际验证下来很有效。比如笔试现场如果有本地IDE 在线监控的模式不要试图用本地IDE的自动补全功能来弥补代码不熟练的问题——在线答题系统的代码格式、输入输出处理一定要提前熟悉否则会浪费大量时间在调试环境上。再比如说笔试时遇到原题不要高兴太早因为题目可能改了某个条件——我遇到过把升序改成降序、把数组改成链表的情况。越是觉得眼熟的题越要重新读一遍题干。用搜狗2016研发工程师笔试题二来练手你不需要把每一道题都做对——笔试题本身就是用来拉开差距的能拿到六成到七成的分数就已经很有竞争力了。我个人的体会是相比刷题量复盘质量才是笔试能力提升的关键。同一道题你做对了但能讲出为什么用这个解法而不是另一个和做对了但只会背答案差距会在后续的系统设计题和面试环节里彻底拉开。