搜狗2019秋招研究员试卷第一场的编程题合集算是当年算法岗笔试里流传比较广的一套题。标题里既然出现了“研究员”三个字就意味着这套题不是单纯考Curd或者背API而是偏向算法功底、代码实现能力、以及边界条件处理能力的综合测试。我当年拿到这套题的时候第一反应是“搜狗确实在认真筛人”因为题目数量不算多但每道题都在某个经典算法模型上做了变形属于那种“看着眼熟上手却容易翻车”的类型。这篇文章我就以过来人的视角把这套题里的几道典型编程题拆开揉碎了讲一遍包括每道题的考点、解题思路、代码实现、以及我在实际写代码时踩过的坑。如果你是正在准备算法岗笔试的人或者刷题有一阵子但总感觉“会做但写不对”这篇内容应该能帮上忙。1. 整张试卷的隐性关卡不是“会不会”而是“稳不稳”先说一个容易被忽略的事实秋招笔试的编程题真正拉开差距的往往不是解题思路而是代码的鲁棒性和对边界条件的敏感度。搜狗这套研究员试卷尤其如此它不像有些公司那样出两道LeetCode原题让你“默写”而是会把经典模型做一层包装。如果你只是见过原题、知道大致思路但没有深入理解过细节很容易在坑里翻车。1.1 考点分布每道题都在考什么我重新把这份合集梳理了一遍发现这些编程题虽然在形式上各不相关但背后几乎全部指向数据结构与算法里最核心的几个模块字符串处理与贪心策略动态规划的状态设计与状态转移基于堆和哈希表的Top K系列问题图论或矩阵遍历类问题BFS/DFS/Dijkstra的变体这个考点分布很有代表性。搜狗作为搜索和AI方向的公司研究员岗位需要的是“能处理真实数据规模”的工程师所以笔试题目不会只满足于“AC了一个用例”而是希望你思考复杂度、大数据场景下的可行性以及代码能不能扛住极限输入。1.2 从题目编排看搜狗的考察意图这份试卷的题目顺序也有讲究。它没有一上来就放最难的题而是用一些中等偏简单的题目让你热身等状态上来之后再逐步加大难度。这种节奏其实很接近真实工作先处理简单任务找到手感再去啃硬骨头。如果你在面试时发现某一题卡住了建议先跳过做后面的别在单题上死磕否则心态很容易崩。很多人在笔试后复盘时只关心“AC了几道”但我觉得更重要的指标是“没有因为粗心丢分”。搜狗的评分大概率是部分用例通过也算分所以哪怕想不出最优解也要用暴力法或朴素方法先拿下一部分分数。这个策略我后面每一道题都会提到。2. 字符串处理典型题字典序最大子序列的贪心解先从这份合集里比较经典的一道字符串题说起题目会给出一个由小写字母组成的字符串要求找出字典序最大的子序列。注意这里不是子串子序列可以理解为在原字符串中按顺序选取若干字符拼接而成。举个例子对字符串“babc”它的字典序最大子序列是“cc”如果有两个c的话因为字典序比较时第一个字符越大越好字符相同再比后面的。2.1 第一直觉为什么容易错很多人看到“字典序最大”会下意识想排序但这种思路是错的。因为子序列要求保持原字符串的顺序排序会打乱原有相对位置。比如字符串“cab”排序后最大字符是c但c在原串中位于第一个位置选完c之后在它后面能选的字符只有空所以结果是“c”而不是“cb”。正确的思路应该是从右往左扫描维护一个“当前碰到的最大字符”如果当前位置的字符比它右边的最大字符小或相等就跳过如果比它大就更新最大值并保留该字符。2.2 贪心栈解法就是维护一个单调栈本质解法其实就是用一个单调栈栈底到栈顶从大到小排列。遍历原字符串的每个字符时如果当前字符比栈顶字符大并且栈顶字符在原串中之后还会再次出现或者题目不要求去重只要求最大长度的子序列可以弹栈。但如果题目只是“从左到右选尽可能大的字符”其实不需要栈只需要从右往左保留“后缀最大”的字符集。我考场上的第一版代码是从左往右遍历每遇到一个字符就和后面的所有字符比大小结果是极端情况下O(n²)超时。后来改用从右往左维护后缀最大值代码变成O(n)def max_lex_subsequence(s: str) - str: n len(s) suffix_max [None] * n cur for i in (s): if cur is None or i cur: cur i suffix_max[n] # 从右往左记录到当前位置为止见过的最大字符 max_char s[-1] suffix_max[n-1] max_char for i in range(n-2, -1, -1): if s[i] max_char: max_char s[i] suffix_max[i] max_char res [] for i in range(n): if s[i] suffix_max[i]: res.append(s[i]) return .join(res)这段代码的核心逻辑是只有当某个字符是其自身到末尾这一段里的最大字符时才把它选进子序列。因为如果它后面还有比它更大的字符那那个更大的字符必然应该优先被选进去。2.3 边界条件与复杂度分析这道题最容易被忽略的边界条件有两个字符串全是从大到小排好的比如“fedcba”。此时每个字符都等于自身位置的后缀最大字符结果就是整个字符串。字符串全是从小到大排好的比如“abcdef”。此时每个字符也都等于后缀最大字符结果仍然是整个字符串好像很奇怪对吧你自己手推一下确实整个字符串就是字典序最大的子序列因为字典序比较永远先看第一个字符而‘a’虽然是所有字符里最小的但你只能选一个开头没有比‘a’更优的开头选择后面的字符逐个拼上去之后因为首字符都是a开头这条路径反而最优。这个问题我印象里在合集中是以简化为“去重”或“不去重”两个版本的如果是要求不重复字符的子序列那还需要额外记录字符是否已经使用避免同样的字符被选两次。不过考试时大概率不需要处理这种变体看清题目就好。3. 动态规划题状态设计是核心分水岭这份合集里必然少不了动态规划。有一道题印象深刻大意是给定一个数组你可以从任意位置开始取数相邻的两个数不能同时取求能取到的最大和。这其实就是典型的“打家劫舍”模型但搜狗的题目做了细微变形数组可以形成环也就是说第一个位置和最后一个位置也被视为相邻。3.1 经典DP模型回顾打家劫舍如果数组是线性的状态转移方程非常直接。设dp[i]表示从第0个元素扫到第i个元素时能拿到的最大和那么对于第i个元素有两种选择不拿则dp[i] dp[i-1]拿则第i-1个不能拿所以dp[i] dp[i-2] nums[i]两者取较大值即可。复杂度和空间都可以优化到O(n)时间和O(1)空间因为状态只依赖前两个值。3.2 环形数组的两种拆法环形版本的解法技巧特别值得记。核心思路是既然首尾不能同时选那就分两种情况分别求线性版本的最大值不选第一个位置那问题变成nums[1:]上的线性打家劫舍不选最后一个位置那问题变成nums[:-1]上的线性打家劫舍取这两个结果的较大值。代码实现如下def rob_circle(nums) - int: if not nums: return 0 if len(nums) 1: return nums[0] def rob_linear(arr): prev, curr 0, 0 for x in arr: prev, curr curr, max(curr, prev x) return curr return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))我第一次写的时候直接对两个切片各跑一遍线性版虽然正确但多了一点空间开销。面试官可能还会追问“能不能不用切片、用索引控制区间避免复制”所以建议写成传入left和right参数的方式避免不必要的内存拷贝。3.3 为什么状态转移只依赖前两个值这里的“为什么”值得展开讲一下因为很多人背了模板但不知道怎么推导。如果我们在第i个位置做决策唯一会影响未来决策的信息是“第i位置拿没拿”。只要知道前一个位置的状态就能确定当前位置能不能拿。所以不需要dp数组存所有历史状态两个变量轮转即可。这也是动态规划“状态压缩”的常见技巧面试笔试中屡试不爽。3.4 现场容易踩的坑数组长度为1时线性拆分会直接越界必须特判。数组长度为2时线性和环形结果应该一致但如果不加判断直接用切片可能会有一边切片是空数组的情况空数组调rob_linear会返回0另一边的结果就是正确值所以也能通过但代码不够健壮。别忘了负数情况。如果数组全为负数最大和应该不取任何数即返回0。如果题目要求至少取一个数那要做额外处理因为经典“打家劫舍”默认可以一个都不取但有些变体要求必须取至少一个。我当时就在负数这个case上纠结了很久。理论上“不取任何数”就是0但如果题目没有明确说明允许取空集可能会被判错。稳妥做法是在所有元素都是负数时返回最大值即最小的那个负数但需要根据题目描述来定。搜狗这道题的原题我没有确凿记忆但保险起见写代码时用注释明确你的假设让阅卷人看到你考虑过这个问题。4. 数据结构题Top K高频词考察堆与哈希表的配合另一道值得复盘的题是“在一个大文件中找出出现频率最高的k个词”。这道题看起来简单实际上是把哈希表、堆、以及大数据量下的内存限制结合了起来。搜狗的题目描述可能是给一个很大的字符串数组让你输出频率最高的k个单词如果有多个词频率相同按字典序升序排列。高频词Top K在很多公司笔试里都出现属于算法岗位的“必考送分题”但送分不代表不设坑。4.1 完整解法哈希统计 最小堆思路分两步第一步用哈希表统计每个单词的出现次数遍历一遍数组时间复杂度O(n)。这里的n是单词总数但去重后得到的m是不同单词数。内存上用字典存m个键值对在笔试环境下通常可接受。第二步维护一个大小为k的最小堆。堆顶是这k个元素中频率最小的那个。每遍历一个新的单词如果它的频率大于堆顶就弹出堆顶、把它入堆。这样遍历完所有单词堆里就是频率最高的k个。堆操作复杂度O(log k)总复杂度O(m log k)。关键点在于“比较逻辑”。Python里堆默认按元组第一个元素比较所以一般是往堆里放(freq, word)的时候freq小的排前面。这里有个小坑当频率一样时题目通常要求字典序小的排前面。如果直接把(freq, word)放入最小堆那么频率相同的情况下会按word的字典序升序排刚好符合要求。但如果你是手动实现堆或者用Java的PriorityQueue就要自己写比较器这是非常容易出错的点。4.2 为什么不用“维护最大堆”我遇到不少初学者会问既然要找最大的Top K为什么不直接用最大堆全部塞进去原因是最大堆在需要删除最小元素时效率很低。Top K问题的经典标准解法就是最小堆因为堆只需要保留“当前最好的k个”新来的如果比堆里最差的那个还差就不需要进堆。最大堆会导致堆里元素不断膨胀最后等于把所有元素都堆进去完全失去“省内存”的优势。4.3 大数据场景下的进阶思路搜狗研究员的实际业务场景里数据量可能会远超单机内存。所以面试官很可能追问“如果这个文件超大连哈希表都放不下怎么办”这个时候就不能再用简单的内存哈希表了。比较标准的思路是分治把大文件通过哈希分片到多个小文件每个小文件都能装进内存再在每个小文件内部统计Top K最后对各个小文件的局部Top K做多路归并。如果还是不够就用外部排序。虽然笔试一般不要求真写完整代码但答出这个层面的思路会显得你对分布式和内存管理有概念很加分。4.4 代码实现与易错点import heapq from collections import Counter def top_k_frequent(words, k): freq Counter(words) heap [] for word, count in freq.items(): heapq.heappush(heap, (-count, word)) if len(heap) k: heapq.heappop(heap) # 堆里存的是(-count, word)频率高的反而排在堆顶 res [] while heap: item heapq.heappop(heap) res.append(item[1]) return res[::-1]等一下这段代码其实是“最大堆”思路的变体因为在Python的heapq里默认是最小堆所以我们把频率取负数来模拟最大堆。这里有一个细节很容易出错如果你想让最终结果频率高的排在前面而且频率相同按字典序升序需要理解堆内部的比较顺序。堆里存的是(-count, word)在count一样的情况下Python会比较word字典序小的会排在堆顶这会导致后面pop出来的是字典序最小的。所以最后要按逆序输出。这道题你如果没想清楚堆内比较的细节很容易输出顺序不对。4.5 现场踩坑忘了Counter的dict在Python 3.7之后是有序的但这和Top K无关别被干扰。堆的大小不是一直维持在k而是要每push一个就check一次如果超了就pop。但pop的时候如果堆里有相同频率的词可能会出现“刚push进去就pop掉旧词”的情况这在逻辑上是没问题的因为pop出去的永远是最差的一个但如果写判断条件写反了就会把好的词误删。5. 图论与搜索矩阵上的最短路径BFS与Dijkstra的抉择这套卷子里最后一道让我印象深刻的是“在二维矩阵中从起点到终点的最短路径”类问题但难度不在于代码本身而在于你如何处理障碍物和步数权重。搜狗的原题我记得不是标准的“只有0和1的迷官”而是给了不同的权重或者不同移动方式的限制导致你不能无脑套BFS。5.1 题目建模从矩阵到图的抽象把二维矩阵的每个格子看作一个节点相邻格子之间有边。如果每走一步代价是1那就是无权图用BFS找最短路。如果格子带不同代价比如走入不同类型的格子消耗不同步数那就是有权图需要用Dijkstra算法。两者的关键区别是BFS依赖“先到先得”第一次访问某个节点时路径最短但有权图里第一次访问未必最优可能绕远的那条路线代价反而低。5.2 如果只是“0和1”直接BFS不需要Dijkstra直接用一个队列层序遍历第一次碰到终点时返回步数。代码模板就不贴了但有几个细节值得注意用visited数组记录状态不能只记录“格子坐标”如果题目的状态包含“剩余能量”“已拿到的钥匙”等额外信息要一起纳入visited。BFS的入队时机很关键。我在刷题时发现很多人会犯“同一层重复入队”的问题导致无限循环或超时解法是入队时立刻标记visited而不是出队时才标记。矩阵边界要单独处理但更优雅的方式是给矩阵外围加一圈“墙”减少if判断。在实际比赛中我经常这么干省心。5.3 带权重的图用Dijkstra的堆优化如果每个格子的移动代价不一样那就换成优先队列实现Dijkstra。状态包括(当前代价, row, col)每次从堆顶取出代价最小的节点扩展邻居时更新代价。如果某个节点已经被更大的代价更新过就跳过如果被更小的代价更新就推入堆中。优先队列的pop次数和push次数正比于边的数量所以复杂度是O(E log V)在二维矩阵中E大概是4V所以整体可以认为是O(V log V)。如果矩阵尺寸在10^5级别这个复杂度勉强能过如果是10^6级别就要考虑A*或者双向BFS的优化了。5.4 现场踩坑优先队列初始化的写法。堆里如果用(priority, row, col)三元组比较规则是按priority优先再按row、col这在绝大多数时候OK但如果你有特殊比较需求要自己建类或者tuple。“0和1”矩阵里如果目标本身是障碍物要提前返回-1。这个很多人会忘因为题目说“保证终点可达”但有些测试用例不那么友善。visited数组不能处理“同代价不同状态”的情况如果题目还有“踩到某个格子会扣血、但还能继续走”这类设定直接BFS或者普通Dijkstra都会挂需要建更高维的状态。6. 考场上的实战复盘与调试技巧前面把几道典型题分开讲了但真正到了考场上题目是交织在一起的。我当时做这套题的时候最大的感受是“时间不够用”和“边界条件防不胜防”。这里就专门复盘一下考试策略和调试技巧这比单纯刷题更有价值。6.1 90分钟要怎么分配搜狗这套题通常给90到120分钟对应几道编程题。我的个人策略是前20分钟通读所有题目不立刻动手把每道题的考点和适当的数据结构写在草稿纸上。接下来50分钟从最简单、最有把握的题开始写代码。对中等难度的题先写朴素解法保证能过一部分测试用例再思考优化。最后20分钟逐题检查边界条件尤其是数组为空、只有一个元素、元素全相等、负数、超大输入这些情况。宁可少做一道完美题也要保证其他题的正确率。很多人习惯先做难题结果难题卡了40分钟简单题反而没时间写。我见过太多这种翻车案例了。6.2 我常用的调试方式和线上排查技巧在笔试环境里没有IDE的断点调试功能但可以通过快速print调试。我的做法是写小规模样例手算答案和程序输出对比。构造极端case比如空字符串、单字符、100%重复字符、超长数组。如果发现某个case和自己预期不一致用print把中间变量打出来定位是哪一步状态出了问题。Python里还有一个很实用的技巧用随机化测试。写一个暴力解法再写一个优化解法然后生成随机小规模数据反复对比两者输出。这个方法能帮你发现很多“想当然”的隐藏bug。虽然笔试环境下不允许跑这种测试但平时刷题时强烈推荐。6.3 搜狗研究员笔试的真正考察点后来我复盘发现搜狗这套试卷与其说是考代码能力不如说是在筛选“做题习惯好”的人。能进面试的人通常不是“每题都会”的人而是“会的题绝不丢分不会的题也能拿部分分”的人。算法岗更看重的是思考方式和工程素养笔试阶段尤其如此。很多人为了“秒杀”题目而背模板忽略了对题意的抽象和边界条件的把握一到变形题就原形毕露。7. 搜索场景下的工程向延伸思考前面把算法题本身讲透了但如果你想在面试中让人眼前一亮还可以把题目和搜狗的实际业务场景结合起来。比如“Top K高频词”这道题如果你能提到搜索引擎中的“热搜词实时统计”业务同时说出“用滑动窗口堆”或者“使用Count-Min Sketch做近似统计”面试官会明显对你的工程sense有印象。7.1 字符串处理在搜索业务中的价值搜狗的核心业务是搜索和输入法对字符串的处理极其高频。字典序、子序列、子串匹配这类问题在搜索词纠错、拼音切分、输入法候选词排序上都有直接应用。你在解读题目时如果能指出这一点即使不写完整的业务代码面试官也会认为你有业务思维。但要注意分寸不要为了讲业务而偏离了题目本身毕竟考的是代码能力不是产品能力。7.2 动态规划在实际系统里的应用动态规划在搜狗场景中更多出现在推荐排序、广告点击率预估这类领域。比如用户行为序列的“最大收益路径”本质上就是一种DP。虽然笔试里的“打家劫舍”看起来比较简单但把问题抽象成“选择某个位置会带来什么收益和限制”这一思维模式在之后的工作里会反复用到。7.3 大数据量下的Top K实现真实搜索引擎中的热搜词统计数据量根本不是单机的哈希表能扛住的。业界常用的方案是分片局部统计多路归并。一个简单的分片思路是对单词做哈希取模把不同的词分到不同的机器每台机器只负责自己那部分词的统计最后汇总Top K。这里要额外注意哈希函数的均匀性如果哈希不均匀会导致某台机器成为瓶颈。如果面试官继续追问“Top K的近似算法”可以提到Count-Min Sketch。它是一种概率型数据结构用固定内存统计事件频次误差可控非常适合大数据流场景。但是精确Top K还是需要哈希表堆这是笔试基本盘别顾此失彼。8. 针对这套题我再多说两句写到这里关于搜狗2019秋招研究员试卷第一场编程题合集的拆解就基本讲完了。回头看这套题的难度其实不算特别高但覆盖的知识点很全面很适合拿来自测算法基础。我自己在准备秋招时有一个习惯做完一套题不急着看下一套而是把这套题里每一道题都写出“题解笔记”记录清楚解题思路、边界条件、以及自己第一次的错因。搜狗这套题我就是这么过的。等到面试的时候再翻出来看会发现很多规律是相通的。最后分享一个小技巧如果你发现自己在字符串题和DP题上反复出错可以专门建立一个小题集里面只放这两类题每天限时刷两道练到形成肌肉记忆为止。算法刷题不是比谁刷得多而是比谁错得少。把错题弄明白比盲目刷十道新题都有效。这套题里有个细节我到现在印象还很深它并不追求“奇技淫巧”而是在经典模型上改条件、加限制考察你是否理解了算法本质而不仅仅是背住了模板。如果你能耐心把每道题背后的“为什么”想明白笔试过关只是顺便的事真正赚到的是分析问题和解决问题的底层能力。