搜狗2020校招后端笔试复盘：编程题与系统设计全解析

搜狗2020校招后端笔试第一场是我秋招季里印象很深的一场。搜狗这个公司做搜索起家后来输入法、AI硬件都有布局所以它的后端笔试天然带着一股实用主义的味道——不搞偏题怪题但每一道题都能感觉到它是在为实际业务筛人。我当时是在牛客网的系统上完成的全程摄像头监考两个小时的题量从选择题到编程题再到设计题节奏非常紧凑。现在回过头看这套题的考点覆盖和难度梯度设计得很典型很适合准备大厂后端校招的同学拿来当模拟卷练手。这篇复盘我会把整套题的出题逻辑、每道编程题的完整解法、选择题涉及的知识点串讲以及系统设计题的解题思路全部拆开讲一遍。如果你是正在准备校招的应届生或者想跳槽大厂后端的社招朋友这套题值得认真过一遍。我尽量还原当时做题的真实场景和思考过程有代码的地方给出可直接运行的版本顺便把我踩过的坑也一并说了。1. 笔试整体概览与出题逻辑1.1 题型分布与考点拆解先说整体结构。搜狗2020校招后端笔试第一场题型分三块单选题、编程题、设计题。选择题大概二十道左右涉及数据结构、操作系统、计算机网络、数据库、C/Java语言基础这几个方向编程题三道由易到难最后一道设计题给一个场景让你写方案。总分100分编程题占比最大基本上是能不能进面试的分水岭。从考点分布可以明显看出搜狗的筛选逻辑基础不牢的选择题直接刷掉代码能力不行的编程题卡死有工程思维潜力的设计题拉开差距。这套组合拳其实和大厂后端校招的主流玩法完全一致并没有因为是搜索引擎公司就考什么冷门算法。唯一带点搜索业务色彩的是编程题里那道Top K高频词以及设计题里的短链服务——这两题背后都能隐隐看到搜索业务中海量数据、高并发、快速响应的影子。1.2 难度曲线与时间分配判断我的判断是这套题的整体难度在当年大厂校招里属于中等偏上。选择题部分有大概三分之二是基础题认真复习过408的同学都能拿分但中间会穿插一两道容易纠结的坑题比如考你TCP四次挥手中TIME_WAIT状态出现在哪一端这类细节。编程题第一题属于热身级别10分钟之内搞定第二题是经典链表题考快慢指针原理不难但容易在边界条件上翻车第三题就要动点脑子了表面是统计词频实际上考的是堆排序和Top K思想的灵活运用。设计题呢没有标准答案但必须写出完整的方案框架。时间上我建议这样切选择题控制在40分钟以内每道题读两遍还拿不准就先标记跳过别恋战。编程题留80分钟第一题15分钟第二题25分钟第三题30分钟剩10分钟验证边界和整理设计题提纲。设计题不用写代码写清楚架构、数据结构、流程和瓶颈分析就够了时间不宜超过20分钟。这套时间分配我后来复盘觉得是合理的实际考试时我是选择题花了35分钟编程题刚好踩线设计题写得有点赶如果一开始就能严格按这个节奏来设计题能写得更从容。2. 编程题逐题复盘从字符串到链表的实战拆解2.1 第一题最长不含重复字符的子串别小看滑动窗口题目大概是这样的给定一个字符串找出其中不含有重复字符的最长子串的长度。输入abcabcbb输出3因为abc是最长的无重复子串。输入bbbbb输出1。这题在LeetCode上是第3题属于那种看起来简单写起来容易出各种小问题的题目。我当时的解题思路是滑动窗口加哈希表。核心逻辑是维护一个左边界和一个右边界右边界不断向右扩展每遇到一个新字符就检查它上一次出现的位置是否在当前窗口内如果在就把左边界跳到那个位置的下一个字符处保证窗口内永远没有重复字符。然后每次更新窗口长度取最大值。时间复杂度O(n)空间复杂度O(n)。int longestWithoutRepeatingChar(string s) { unordered_mapchar, int lastIndex; int left 0, ans 0; for (int right 0; right s.size(); right) { char c s[right]; if (lastIndex.find(c) ! lastIndex.end() lastIndex[c] left) { left lastIndex[c] 1; } lastIndex[c] right; ans max(ans, right - left 1); } return ans; }这里有个关键细节我当时差点踩坑更新左边界时要加一个判断lastIndex[c] left。如果不加这个判断当遇到一个字符上次出现的位置已经在窗口左边之外时会把左边界往回拨导致答案出错。举个例子abba这个字符串当右指针走到第二个a时a上次出现的位置是0但此时的窗口是[2,3]左边界是2如果直接把left更新成1窗口就会错误地扩大。所以必须加条件判断确保只有当重复字符出现在当前窗口内时才移动左边界。这题其实还有个小变形如果字符串不是ASCII字符而是Unicode哈希表的key就要用字符而不是字节。笔试时题目默认是ASCII但我在面试中就被追问过这个变体所以提醒大家留意。2.2 第二题链表环检测与环入口定位快慢指针背后的数学原理第二题是经典中的经典判断一个链表有没有环如果有返回环的入口节点如果没有返回null。要求不能使用额外空间。输入是一个链表头节点输出按要求返回节点。思路就是快慢指针快指针每次走两步慢指针每次走一步。如果链表没有环快指针会先到达链表尾部直接返回null。如果有环两个指针一定会在环内相遇。关键是怎么从相遇点找到环入口。这里有个数学推导假设链表头到环入口的距离是a环入口到相遇点的距离是b环的周长是c。慢指针走了ab步快指针走了2(ab)步。快指针比慢指针多走了ab步这个值一定是环周长的整数倍也就是ab n*c。整理一下从相遇点继续走a步就能回到环入口。所以算法是相遇后把一个指针放回链表头另一个留在相遇点两个指针每次都走一步再次相遇的位置就是环入口。ListNode* detectCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode* ptr head; while (ptr ! slow) { ptr ptr-next; slow slow-next; } return ptr; } } return nullptr; }这道题说实话思路记住了就不难但很多人在笔试现场会卡在为什么相遇后再走a步就是入口这个推导上。我建议备考时不要只背代码要把数学原理自己推导一遍因为面试官很可能会顺着这题追问如果快指针每次走三步还能相遇吗答案是不一定快慢指针步数差为1才能保证在有限步内相遇如果快指针走三步慢指针走一步在某些环结构下快指针可能会永远跳过慢指针导致无法检测到环。实际笔试时这题还需要处理空链表和单节点无环链表的情况我见过有人因为没判空导致空指针异常直接把测试用例挂掉非常可惜。所以写任何链表题第一步永远是处理空指针边界。2.3 第三题Top K 高频词搜索引擎业务的缩影第三题一出来我就笑了这题太像搜狗会出的题了。题目大意是给定一个非空的单词列表返回出现次数最多的K个单词返回结果应该按单词出现频率由高到低排序如果两个单词出现频率相同则按字母顺序排列。这题考了两个核心点一是哈希表统计词频二是Top K的选择算法。最容易想到的做法是把所有单词按频率排序后取前K个时间复杂度O(n log n)但这不是最优解。当单词总量很大、K很小的时候更合适的做法是维护一个大小为K的最小堆遍历词频表堆满后如果新元素的频率比堆顶大就弹出堆顶、压入新元素。这样时间复杂度是O(n log K)当K远小于n时性能优势非常明显。这题还有一个细节容易翻车排序规则是频率降序、字母升序。用最小堆的时候堆顶是最应该被淘汰的元素所以堆顶要放的是当前K个元素里频率最小、字母序最大的那个。很多人在堆的比较器上写反导致输出顺序和预期相反。我当时是这样写的struct Node { string word; int count; bool operator(const Node other) const { return count other.count || (count other.count word other.word); } }; vectorstring topKFrequentWords(vectorstring words, int k) { unordered_mapstring, int freq; for (auto w : words) freq[w]; priority_queueNode pq; for (auto p : freq) { pq.push({p.first, p.second}); if (pq.size() k) pq.pop(); } vectorstring result(k); for (int i k - 1; i 0; i--) { result[i] pq.top().word; pq.pop(); } return result; }堆里每个元素存储单词和词频两个值。比较器的写法是频率小的优先出队频率相等时字母序大的优先出队。这样堆里留下的就是频率最大、字母序最小的那些词。最后从堆里取元素时由于堆顶是最弱的所以要倒序填充结果数组保证输出按频率从高到低排列。当时我写完这题后在最后的简答题里还顺手提到了搜索引擎收集用户搜索日志、统计热门搜索词本质上就是Top K问题的在线版本。这种跨题目联想不扣分有时候反而会让面试官觉得你有业务sense我后面在面试时确实被问到了相关内容。3. 基础选择题考点串讲不只是背八股3.1 C 与 Java 语言基础高频考点搜狗后端的选择题在语言基础上考得很细。C方向我印象比较深的有这么几类一是虚函数的实现机制问含有虚函数的类其对象模型是什么答案是对象内部有一个虚表指针指向虚函数表虚函数表里存的是函数指针二是构造和析构的顺序比如派生类对象构造时基类和成员对象的构造顺序三是智能指针像是shared_ptr的引用计数是线程安全的但指向的对象并不线程安全四是关于const和static的修饰规则比如静态成员函数不能访问非静态成员变量。Java方向的考点主要集中在JVM内存模型和垃圾回收。选择题里有一道印象很深JVM堆内存中哪个区域用于存放新建对象——答案是新生代的Eden区。还有一道关于HashMap在JDK1.8中的变化底层由数组加链表改为数组加链表加红黑树当链表长度大于等于8且数组长度大于等于64时转为红黑树。这里有两个前置条件很多人只记住了8这个阈值忘了数组长度还必须大于64笔试时很容易被这种细节绕进去。我的建议是语言基础这块没有捷径就是把高频考点做成表格反复过。虚函数、智能指针、JVM内存分区、垃圾回收算法、集合类源码这几个方向出现频率极高每个都要做到能默写框架、能讲清楚底层原理的水平。我当时是把这些考点按是什么、为什么这么设计、有什么坑、怎么答面试追问四个维度整理成一个文档考前一周每天过一遍效果很好。3.2 操作系统与计算机网络必背知识点操作系统方向搜狗笔试考了进程和线程的区别、死锁的四个必要条件、虚拟内存与页面置换算法。死锁那题考的是银行家算法的应用场景问系统能避免死锁的调度策略是什么答案是银行家算法。页面置换那块考了LRU和FIFO的缺页次数对比给定一个页面访问序列需要手动模拟计数。这类题不能光记概念必须亲手在草稿纸上模拟几次不然考场上算着算着就乱了。计算机网络方向选择题密度很高。TCP三次握手和四次挥手几乎是必考的搜狗也不例外。有一道题是客户端主动关闭连接后进入TIME_WAIT状态的是哪一方答案是主动关闭方也就是客户端。TIME_WAIT持续时间为2MSL作用是保证最后一个ACK能到达对端同时让旧连接中的报文在网络中自然消失。这个知识点我不止一次在笔试里见到属于网络部分的钉子户。HTTP相关的题也考了一道HTTP 301和302的区别是什么——301是永久重定向302是临时重定向。搜索引擎对这个很敏感因为重定向类型会影响爬虫和索引策略。搜狗是搜索公司它的笔试里出现这种和业务相关的网络题非常正常大家在准备这类公司时要注意把基础知识和业务场景挂钩。3.3 数据库与搜索相关的技术题数据库部分索引和事务是两道重头题。索引那道题问的是InnoDB的默认索引结构是什么答案是B树不是B树也不是红黑树。为什么是B树因为B树的非叶子节点不存储数据每个节点可以存储更多索引项树的高度更低磁盘IO次数更少同时叶子节点用指针相连适合范围查询。这个为什么一定要理解因为选择题只是热身面试时一定会被追问原理。事务那道题考的是隔离级别给了四个场景分别对应哪种隔离级别。比如一个事务读取到另一个事务已提交的数据但在当前事务里前后两次读到的数据不一致这是不可重复读需要RR级别才能解决。四个隔离级别的区别和各自的并发问题要能流利说出来读未提交、读已提交、可重复读、串行化分别解决的问题是脏读、不可重复读、幻读。作为搜索公司的笔试还考了一道关于倒排索引的选择题倒排索引中词典的主要作用是什么答案是记录每个词项对应的倒排列表的位置或指针用于快速定位。这道题其实很友好只要知道倒排索引的基本结构都能做对。但如果想加分可以进一步思考词典本身用什么数据结构存哈希表、B树还是跳跃表不同方案在内存占用和查询效率上有什么权衡笔试虽然只考选择但思考深了面试环节会非常占优势。4. 简答题与系统设计搜索引擎公司爱考什么4.1 经典短链服务的后端设计思路设计题给了一个很常见的场景设计一个短链接服务用户可以提交一个长URL系统返回一个短网址用户访问短网址时能302重定向到原始长URL。要求写出核心架构、存储方案、ID生成策略以及可能遇到的性能瓶颈。这题我拆成了四层来答。第一层是ID生成短网址的字符集是大小写字母加数字共62个字符如果短码长度是7位能表示62的7次方大约是3.5万亿个URL足够用。生成方式我推荐雪花算法它由时间戳、机器ID、序列号组成64位整数转换成62进制就是短码。雪花算法的好处是趋势递增、分布式环境下不冲突、生成效率高。也可以选数据库自增ID加进制转换但高并发下会有单点压力。第二层是存储设计用一个映射表存储短码和长URL的对应关系主键是短码字段包括原始URL、创建时间、过期时间、点击次数。为了查询性能直接用短码作为主键索引即可不需要额外建索引。但如果要支持按用户查询短链列表就需要加一个user_id字段并建索引。第三层是跳转流程用户访问短网址服务器解析短码查存储拿到长URL返回302重定向响应浏览器自动跳转到长URL。这里有个小细节要说明为什么选302而不是301因为301是永久重定向浏览器和CDN会缓存以后想统计点击量或修改目标URL就麻烦了302是临时重定向每次都会经过短链服务便于统计和运营。第四层是性能与容灾短链服务读多写少完全可以加一层Redis缓存热点短码的请求打到Redis上减轻数据库压力。如果某个短码被恶意刷量还需要限流。我当时还加了一句因为需要记录点击日志用于分析可以考虑用消息队列异步写入避免同步写日志拖慢主流程。这一句虽然简单但能体现对高并发场景的思考。4.2 一个查询背后的完整流程除了短链设计我还把搜索引擎查询的完整流程也梳理了一遍因为这个是搜狗肯定会关注的方向。题目大概是这样用户在搜索框输入关键词后后端系统需要经过哪些步骤才能返回搜索结果我按流水线来答。第一步是分词中文文本没有天然分隔符需要用分词器把句子切成词项。比如北京烤鸭会被切分成北京和烤鸭也有可能被切分成北京烤鸭整体。分词策略直接决定召回结果的准确性常见做法是正向最大匹配加词典现在也有基于统计语言模型的分词方案。第二步是查询分析除了分词还要做拼写纠错、同义词扩展、意图识别。用户搜北京烤鸭店系统可能要识别出店是查询意图的词和北京烤鸭组合成一个完整的查询条件。第三步是召回将分词后的词项去倒排索引里查对应的倒排列表取交集或并集得到候选文档集合。这一步的性能压力最大因为倒排列表可能非常长需要用跳表指针做快速合并。第四步是排序对候选文档做相关性打分传统方法是BM25算法核心是TF-IDF思想的扩展同时考虑文档长度归一化。现在搜索引擎还会加一堆业务特征比如文档质量分、点击率、时效性等用机器学习模型融合这些特征打分。第五步是展示把排序结果返回前端同时记录用户的点击行为日志用于后续优化排序模型。整个链路对时延要求极高搜索引擎后端做到百毫秒级返回靠的是缓存、索引分片、并行计算等手段。这道题答好了基本能看出一个人有没有后端系统的全局视野比单纯背数据结构更能拉开差距。5. 笔试实战避坑与备考建议5.1 编码题最容易丢分的5个细节第一个细节是边界条件。字符串题的空串、单字符串链表题的空链表、单节点数组题的越界这些都是最容易导致用例不过的原因。我建议每道编程题写完立刻用几个特殊输入自测一遍用不了30秒但能救回很多用例分。第二个细节是返回值约定。题目要求返回长度还是子串本身要求输出节点还是节点的值要求升序还是降序看清楚再动手别写完了才发现方向错了。第三个细节是输入输出格式。在线笔试系统通常要求自己写输入输出而不是像LeetCode那样只写核心函数。有些同学平时刷题习惯了LeetCode的套路笔试时忘记处理标准输入输出整道题直接零分。平时练习时就要习惯用cin和cout或者Scanner自己写完整的主函数避免考场上不适应。第四个细节是复杂度预估。看到数据范围再去选算法。比如n是10的5次方级别O(n^2)大概率超时必须上O(n log n)甚至O(n)的解法。如果题目明确说数据量很小那暴力法反而最快最稳。第五个细节是编程语言的选择。搜狗笔试支持多种语言选自己最熟悉的那个不要在考场上尝试新语言。C选手要注意STL容器的时间复杂度Java选手要注意对象创建的开销Python选手要注意循环性能必要时用内置函数。5.2 时间分配策略与答题顺序建议整套题的时间分配我给一个可复用的模板。拿到卷子先花2分钟整体浏览一遍确认题型和题量。先做选择题遇到卡壳超过1分钟的先标记跳过去因为选择题分值一般不大不值得死磕。编程题就按题号顺序做先写框架再补细节不要一上来就追求一次写对。设计题放到最后但至少要留15分钟写出框架就不亏完全不写就很伤了。我还想强调一个策略编程题如果卡住了先把暴力解法写了拿部分分千万不要空着。很多在线笔试系统是按用例给分的暴力法也能通过一部分简单用例拿到30%到50%的分值这比一道题完全空着要强得多。我见过太多同学因为追求最优解卡在优化上最后连暴力分都没拿到。5.3 从笔试到面试的衔接准备笔试结束不是终点而是面试的起点。大厂面试官有个习惯就是拿你笔试的代码当面试素材。我就在面试中被问过你笔试第二题用了快慢指针能证明一下为什么第二次相遇点就是环入口吗或者第三题你用了最小堆如果内存放不下所有词频怎么办所以笔试结束到面试开始那段时间一定要把自己写的代码重新过一遍确保每一行都能讲出理由。我不会建议你在笔试时写超出自己理解的代码因为面试官一追问就会露馅。宁可写一个自己能讲清楚但不算最优的解法也不要抄一个背下来的高级解法面试官连续追问两轮你就顶不住了。备考阶段我个人的做法是刷题时给题目打标签标注它可能被追问哪些问题然后自己模拟面试官问自己。比如刷到最长不重复子串我就追问自己如果字符串里有中文怎么办刷到LRU缓存就追问为什么用双向链表而不是单向链表。这样笔试面试一次性准备到位效率比单纯刷题高得多。最后分享一个小技巧这套笔试题复盘完我最想强调的一点是大厂后端校招笔试从来没有所谓的偏题怪题所有题目都指向同一个目标——考察你有没有扎实的计算机基础、能不能写出干净的代码、有没有系统级思维。搜狗第一场笔试的三道编程题从滑动窗口到快慢指针再到Top K每一道都能在LeetCode上找到类似的题但需要灵活运用设计题也是常见的短链服务拼的是思路完整度。备考冲刺阶段我特别推荐一个练习方式按题型分类限时刷题模拟真实笔试的紧张感。我自己当时是每天上午固定两个小时用牛客网的模拟笔试功能做一套真题然后花一小时复盘把错题和低效解法整理进笔记。坚持一个月笔试状态肉眼可见地提升。笔试不只是考你会不会更考你在限时高压下能不能稳定输出这个能力只能靠模拟训练来培养。