每年到了春招秋招的节点我后台都会收到一大堆同学发来的笔试题目让我帮忙看看思路、改改代码。前两天正好有学弟甩来一份搜狗2019秋招后端工程师的第二场编程题合集说想让我讲讲这些题到底该怎么准备、怎么答。我重新把这套题翻出来做了一遍结合当时笔试的现场情况把整套题的考点、思路、做题顺序还有容易踩的坑全部整理成了这篇文章。先说结论这套题放到今天来看含金量依然很高。搜狗后端笔试一贯的风格是“题量适中、单题深度足、非常看重基础数据结构和边界处理能力”。如果你正在准备后端岗位的校招笔试或者想检验一下自己的算法基础扎实不扎实这套题都值得拿出来认认真真做一遍。这篇文章我会把做题的完整思路、代码实现、现场取舍讲透同时也告诉你哪些地方是最容易被扣分的。1. 为什么这套2019年的题到现在依然值得刷后端工程师的算法笔试和前端、客户端、算法岗都不一样。它不追求那种“非人类”的数学推导也不怎么考特别偏门的套题而是更看重你对数据结构、字符串处理、排序、哈希、树、动态规划这些基础知识的综合运用能力以及写出来的代码是否健壮、可读、能扛边界情况。1.1 搜狗后端笔试到底在考什么搜狗这家公司的业务线大家都很熟搜索、输入法、地图、AI这些。它的后端笔试题目风格也跟业务强相关。我当时做完第二场的感觉就是这套题明显偏重字符串处理和大规模数据的处理逻辑这和搜狗做搜索、输入法、自然语言处理的底子是完全对得上的。整套题约四道编程题题量在秋招笔试里算中等但每一道题的思考深度都不低。不像有些公司动辄十道选择题加两道编程题搜狗这四道题更像是在考察你“能不能一个人在限时条件下把一个小型工程问题拆解清楚并落地实现”。这个能力模型和真实的后端开发日常非常接近——你在公司里写需求本质上也是把一个模糊的问题拆清楚然后实现它。另外值得说的是这份题的难度阶梯设计得很典型。从第一题的“热身题”到最后一题的“筛人题”梯度很明显。如果你能在一个半小时内稳定AC前两题、第三题拿部分分、第四题能写暴力解那在当时的通过率环境下已经算很有竞争力的水平了。1.2 从题目难度阶梯看后端工程师的能力模型我当时做完这场笔试回宿舍复盘的时候整理过一个表把整套题的梯度画出来就是这样题目位次建议耗时难度核心考点预期目标第一题15-20分钟低哈希表、字符串、边界处理必须AC第二题25-30分钟中排序、数组操作、双指针尽量AC第三题30-40分钟中高动态规划、状态设计部分分或AC第四题40分钟以上高数据结构设计、贪心堆、大数据思想暴力分冲AC这个能力模型其实很有代表性。第一题和第二题考察的是基本功哈希表、排序、字符串操作这些是后端开发每天都要用的东西写不熟练说明基础不牢。第三题开始上强度考动态规划的状态设计和边界推导这是区分“会写代码”和“会解算法题”的分水岭。第四题则是真正的拉分题它往往结合了贪心、堆、离线处理等更复杂的角度需要你不仅能写出正确解法还要有时间复杂度的敏感度。我当时在笔试现场的策略很简单前两题我必须拿满分第三题如果状态转移想清楚了就直接写第四题先写最朴素的暴力版本保底再想优化。这个策略看上去保守但在时间有限的情况下非常实用直接决定了你最后的总分能落在什么区间。2. 核心考点拆解与审题技巧刷题最忌讳的就是拿到题目直接上手写代码。我见过不少同学一看题目觉得“这题我见过”结果写着写着发现漏了关键条件整段代码推翻重来时间全浪费了。这套搜狗题特别明显的地方就在于它会在描述里埋很多条件你审题不仔细后面就会吃大亏。2.1 字符串处理搜狗系题目最常出现的考点先聊字符串。这套题的第一题就是一道典型的字符串操作题而且背景非常“搜狗”给定两个字符串判断其中一个能否通过重排变成另一个如果可以再输出重排后的某种字典序结果。这种题在LeetCode上能找到很多类似版本但搜狗把它稍微改了一点加入了一个“指定重点字符”的限制条件——意思是重排后某个位置必须放某个字符。这个改动的杀伤力非常大。很多人在LeetCode上刷过“有效的字母异位词”那种题看到这题第一反应就是“数一下字符频次不就行了吗”结果忽略了那个关键位置的限制导致输出全错。这其实模拟的是后端真实开发里的一种情况需求方给你提了一个大致需求但里面藏着一两个特殊条件你没问清楚、没注意到做出来的东西就是不符合要求。字符串题目的审题我建议大家固定看四个要素字符集范围是只有小写字母还是包含数字、大小写、空串如何处理、相同字符是否可区分、以及有没有位置或顺序上的限制。这四个要素全部确认完再开始设计算法基本不会跑偏。2.2 哈希表与数据结构选型空间换时间的关键接下来是数据结构选型的问题。哈希表是后端笔试里出现频率最高的数据结构没有之一。这套题的前两题用哈希表都能给出非常清爽的解。但哈希表也分很多用法简单计数、记录索引、映射结构甚至哈希表配合排序、配合双指针都是不同的思路。我记得第二题就很有意思它给了一个很大的数据序列让你输出某个滑动窗口内的中位数。这个题第一眼看上去很像经典的“滑动窗口最大值”的变种很多人就直接套单调队列结果写到一半发现根本行不通——因为中位数和最大值不一样它需要窗口内元素的有序性而单调队列只能在两端操作做不到维护全局有序。这种时候就需要你对数据结构有更深的理解窗口是动态滑动的你需要支持“快速删除”和“快速插入”同时随时取到中间那个数。朴素做法是每次重新排序复杂度太高AC不了。更优的思路是用“大根堆小根堆”的对顶堆结构来维护中位数同时配合懒删除来处理过期元素。这个套路在LeetCode上对应“数据流的中位数”和“滑动窗口中位数”两道题。做一个简单的对比方案单步时间复杂度能否AC每次排序取中位数O(k log k)不能平衡树/有序容器O(log k)可以对顶堆懒删除O(log k)常数更小可以推荐暴力计数依赖值域O(V)V为值域视数据范围而定我当时现场选的就是对顶堆方案。这种数据结构题其实比的不是你会不会某个高级技巧而是你能不能准确分析出“需要什么能力”然后从自己的知识库里把对应的结构拿出来用。这和后端系统设计很像——数据库不够快就上缓存消息堆积就上队列都是先定位问题再选择工具。2.3 动规与序列问题后端岗位的一场“必答题”动态规划在后端笔试里出现频率有多高我可以直接说大多数公司的后端岗位三场笔试里面至少有一场会出现DP题。搜狗这场也不例外第三题就是一道典型的动态规划。这道题的原型大概是给定一个整数数组你可以从任意位置开始每次向右跳一步或两步跳到某个位置就能获得对应分数但要求跳到的位置必须大于之前的位置或者分值递增求能获得的最大分数。这个描述一看就是“最长上升子序列”的变种但加了“跳跃”这个外壳。这道题的难点其实不在状态定义上——dp[i]表示以第i个位置结尾能获得的最大分数这个只要练过DP的同学都能想到。真正的难点在于转移优化。朴素的转移需要遍历i之前所有满足条件的j时间复杂度是O(n^2)如果n给到10^5直接超时。优化方案有两个方向一个是线段树/树状数组优化求前缀最大值把转移变成O(log n)另一个是贪心二分配合一个前缀最大值数组。我当时用的树状数组方案把数值离散化之后每次查询当前值域范围内的最大dp值然后更新到当前值对应的下标上。这个思路其实是“最长上升子序列的树状数组优化”属于竞赛选手非常熟悉、但很多校招生不太熟练的套路。说到这里我顺便给一个刷题建议动态规划不要只刷“会了这题”就完事一定要从暴力递归到记忆化搜索再到迭代递推最后到状态压缩/数据结构优化每一步都亲手写一遍。这种递进的训练方式才是你到了笔试现场能临场做对DP题的根本保障。3. 实操复盘三道典型题目的完整求解过程有了前面的考点分析这一节我直接上硬货把三道有代表性的题目从读题到AC的全过程完整走一遍。代码我会给可运行的完整版本用的是比较好读的写法方便大家理解核心思路不是那种竞赛选手写的怪癖风格。3.1 第一题字符串重排判断哈希表边界处理题目描述大致如下给定两个字符串s和t以及一个字符c和一个位置index判断能否通过重排s得到t并且重排后字符c必须出现在位置index上index从0开始计数。如果可以输出任意一种满足条件的重排结果如果不行输出空字符串。核心思路拆成三步第一步判断两个字符串长度是否相等、字符集合和频次是否一致。这一步可以复用“有效的字母异位词”的做法用哈希表记录每个字符的频次然后遍历t做减法。第二步单独处理那个限制条件如果s里面根本没有字符c或者c在s里出现的次数已经小于等于0因为在构造答案时还要用那直接返回空串。第三步构造答案。这一步有个细节你可以先直接把c放到target位置然后把s中剩余字符按任意顺序填充到其他位置。但要注意不能破坏频次关系——填充之前要把已经用掉的c从哈希表里扣一次。完整代码如下def solve(s: str, t: str, c: str, index: int) - str: if len(s) ! len(t): return from collections import Counter cnt_s Counter(s) cnt_t Counter(t) # 判断能否通过重排s得到t if cnt_s ! cnt_t: return # 判断关键字符是否足够放在指定位置 if cnt_s.get(c, 0) 0: return n len(s) res [None] * n # 放置指定字符到目标位置 if index n: return res[index] c cnt_s[c] - 1 # 填充剩余字符 i 0 for ch in s: while i n and res[i] is not None: i 1 if i n: break if ch c and res[i] is not None: continue # 跳过已经被用掉的c的情况 if cnt_s[ch] 0: continue res[i] ch cnt_s[ch] - 1 if any(x is None for x in res): return return .join(res)这题有几个很容易被忽视的坑一是“重排s得到t”这个条件很多人会直接去判断排序后的s和t是否相等这个可以但要记得同时检查长度。二是位置index可能越界这在题目里其实不会出现但稳健的代码还是应该判断一下。三是填充剩余字符时如果你直接用原字符串s里的字符去填可能同一个字符会被尝试多次需要用cnt_s这个哈希表控制剩余次数否则结果会出错。这类题的工程启示在于后端开发里写代码最重要的不是“能跑”而是“在极端条件下也不崩”。笔试考边界处理本质上就是在模拟生产环境的异常输入——用户不会按你预期的格式给你传参。3.2 第二题滑动窗口中位数对顶堆懒删除这题完整描述是给定一个长度为n的整数数组和一个窗口大小k窗口从左往右滑动每次移动一个位置要求输出每个窗口内的中位数。数组长度n最大10^5k最大也是10^5。中位数定义为排序后处于中间位置的数如果k是偶数取中间两个数中较小的那个方便起见不同定义方式并不影响核心思路。先说朴素思路每次窗口移动就对窗口内k个数排序取中间值时间复杂度O(n * k log k)必炸。优化思路要往“维护有序序列”方向走。对顶堆的思路是用两个堆一个大根堆和一个一个小根堆。大根堆存窗口内较小的一半数堆顶是最大值小根堆存较大的一半数堆顶是最小值并且保证大根堆的大小要么等于小根堆要么比小根堆大1。这样一来窗口内的中位数就是大根堆的堆顶如果k是偶数可以额外维护一个变量或者直接取两个堆顶的较小值。滑动窗口的麻烦在于“过期元素”的移除。堆本身不支持任意位置删除所以需要使用“懒删除”技巧先不急着删等这个元素成为堆顶时再判断它是否已经过期过期就弹出。为了准确判断过期需要维护每个位置上的元素在哪个堆里或者至少记录每个元素的值和位置然后判断堆顶元素的下标是否小于当前窗口左边界。由于可能有重复元素我建议记录三元组值下标所属堆标记堆排序时比较值再比较下标。完整参考代码import heapq def solve(nums, k): n len(nums) res [] small [] # 大根堆存较小的一半实际入堆取负 large [] # 小根堆存较大的一半 # 辅助记录每个元素当前是否已经“失效” # 这里直接用下标判断即可不必记录堆标记 def add(num, idx): # 默认先加入大根堆 heapq.heappush(small, (-num, idx)) # 如果大根堆的最大值大于小根堆的最小值需要交换 if large and -small[0][0] large[0][0]: v, i heapq.heappop(small) heapq.heappush(large, (-v, i)) # 平衡大小 if len(small) len(large) 1: v, i heapq.heappop(small) heapq.heappush(large, (-v, i)) if len(large) len(small): v, i heapq.heappop(large) heapq.heappush(small, (-v, i)) def get_mid(k): if k % 2 1: return -small[0][0] else: return min(-small[0][0], large[0][0]) # 初始化前k个 for i in range(k): add(nums[i], i) res.append(get_mid(k)) # 滑动 for i in range(k, n): # 插入新元素 add(nums[i], i) # 惰性删除过期元素 while small and small[0][1] i - k: heapq.heappop(small) while large and large[0][1] i - k: heapq.heappop(large) # 再次平衡 if len(small) len(large) 1: v, i2 heapq.heappop(small) heapq.heappush(large, (-v, i2)) if len(large) len(small): v, i2 heapq.heappop(large) heapq.heappush(small, (-v, i2)) res.append(get_mid(k)) return res这段代码有几个需要注意的地方一是当从大根堆弹出再插入小根堆时必须把取负的值恢复成原值再入堆。很多人在这一步写错符号导致结果莫名变大变小。二是懒删除不能只做一次要用while循环把所有堆顶的过期元素全部清掉因为可能连续多个过期元素都堆在堆顶。三是平衡堆大小和清除过期元素之间是互相影响的所以我建议把“清除过期重新平衡”放在一起形成一套稳定的流程。对顶堆这道题我给一句总结它考察的不只是你会不会用堆而是你能不能想到“让两个堆互相配合动态维护有序性”。这个思路在后端也有很多落地场景比如实时排行榜、库存最低价、数据流里的TopK等等都是同一个模型。3.3 第三题跳跃得分DP树状数组优化第三题描述大致是有一个长度为n的数组a每个位置有一个得分你可以从任意位置出发每次只能向右跳到一个得分比你当前所在位置得分高的位置得分累加问最大能够获得的总分也可以选择不跳但至少要获得出发位置的得分。简化后就是求上升子序列的最大和不过这里要求的是最大和而不是最长长度。经典的动态规划转移方程是dp[i] a[i] max(dp[j])其中 j i 且 a[j] a[i]如果直接枚举j总体复杂度O(n^2)。一旦n到10^5级别就顶不住。所以要用树状数组或者线段树来优化“查询前缀最大值”这个过程。具体做法是先对数值离散化因为树状数组的下标需要从1开始并且值域越小越好。离散化后a[i]对应一个排名rank然后我们用一个以rank为下标的树状数组维护当前位置能取到的最大dp值。转移时查询所有rank小于当前rank的位置的最大dp值即query(rank - 1)然后加上a[i]得到dp[i]再把dp[i]更新到树状数组的rank位置。完整代码class BIT: def __init__(self, n): self.n n self.tree [0] * (n 1) def update(self, i, val): while i self.n: self.tree[i] max(self.tree[i], val) i i -i def query(self, i): res 0 while i 0: res max(res, self.tree[i]) i - i -i return res def solve(a): n len(a) # 离散化 sorted_unique sorted(set(a)) idx_map {v: i 1 for i, v in enumerate(sorted_unique)} bit BIT(len(sorted_unique)) dp [0] * n ans 0 for i in range(n): rank idx_map[a[i]] best bit.query(rank - 1) dp[i] best a[i] bit.update(rank, dp[i]) ans max(ans, dp[i]) return ans这里有一个非常关键的细节由于要求严格递增所以查询是query(rank - 1)而不是query(rank)。如果是非严格递增查询就应该是query(rank)。这个区别很多同学写题的时候容易忽略是WA的重灾区。另外还有一个细节树状数组维护的是“值域维度上的最大值”它天然支持两种情况一是动态增加新元素二是每次查询都是前缀最大值。这正好符合dp从左到右推进的过程。而如果你用线段树也可以代码会更长一些但思路完全一样。从这道题可以总结出一个经验很多“看起来是进阶”的优化本质上都是在原有的朴素算法上找到一个可以快速查询的维度然后用数据结构挂上去。动态规划的优化通常就是从“枚举所有j”变成“用数据结构维护所有j的最优值”关键在于找到合适的“维度”。4. 秋招笔试的坑与实战心得代码说完了这一节聊一点更偏现场的东西。笔试和平时刷题最大的区别在于时间有限、压力大、容错低。很多同学平时LeetCode能稳定写对Medium笔试却只有两道AC问题往往出在笔试策略和细节把控上而不是算法能力上。4.1 笔试现场最容易犯的五个错误第一个错误是审题不仔细导致思路跑偏。前面说了搜狗这场的字符串题里埋了“指定位置必须放某个字符”的条件如果你没看到写出来的代码肯定是错的。更可怕的是这种错误在自测用例里可能发现不了因为普通用例都过了你还会以为自己AC了。我的建议是读题结束之后用30秒在草稿纸上把题目里的所有限制条件列出来然后再开始想解法。第二个错误是输入输出格式写错。后端笔试题的输入输出格式五花八门有的用逗号分隔有的用空格分隔有些是每行一个用例有些是多组用例。最好在开场后先花3分钟把本地模板配好包括快速读入、快速输出、debug标志关闭等。这一波操作能给你省下大量时间。第三个错误是边界条件考虑不周。空数组、单元素数组、目标字符不存在、窗口大小等于数组长度这些都是最常见的边界。一个比较实用的建议是写完代码后不要着急提交先用这几个固定用例自测一遍——空输入、最小输入、最大输入、重复元素输入。第四个错误是死磕一道题不放手。后端笔试时间通常90分钟到120分钟四道题。如果一道题20分钟内没有任何思路立刻放下写下一道。你要知道在一道题上拿30%的部分分性价比远高于另一道题拿0分。这就像系统设计里的负载均衡总吞吐量才是KPI不是单点延迟。第五个错误是局部变量污染。笔试环境一般允许你本地调试但很多同学在本地调试时改了代码提交时忘记恢复导致交上去的和本地跑出来的完全不一样。所以提交前的最后一步永远是把代码从头到尾自己读一遍确认没有调试残留。4.2 算法题之外的隐性考点搜狗这场笔试还有一个很有意思的地方就是它的平台会记录你的提交次数和每题耗时虽然这个不一定直接决定你的面试结果但它会影响你后面的简历评估。我当时听HR说后端岗位看重的排序大概是AC题目数 总耗时 提交通过率 代码风格。也就是说你AC了三题但每题提交了七八次可能不如AC了两题每题一次提交的人评价高。所以平时训练的时候就要有意识追求“一次写对”的能力。具体怎么训练呢我建议每个题做完后强制自己在白纸上把代码重新默写一遍不看答案不运行然后自己模拟几组数据手算结果。这个过程能大幅提升你对代码执行的掌控力减少笔试现场的“凭感觉写”。另外还有一个隐性的考点就是你对所写代码复杂度的解释能力。笔试写代码不像面试不需要你当场讲思路但在后续面试中面试官很可能拿着你的笔试代码问你“当时为什么用这个方案”。所以每一道题做完我都会花30秒在草稿纸上写一下这个方案的时间复杂度和空间复杂度以及大概的证明思路。这既是为了面试也是让自己更清楚解法为什么高效。4.3 复盘的价值把一场笔试变成一次提升我刷完这套2019搜狗秋招题之后最大的感受就是搜狗的出题质量是真的高每一道题都不是那种“背板子”能解决的题目而是需要你真正理解数据结构和算法的本质。如果你想把它当成一个训练项目来刷建议按下面的流程走第一遍限时90分钟模拟真实笔试环境全程不看题解、不联网、不中断。分数不是目的目的是暴露你的紧张状态和时间分配问题。第二遍不限时每一道题都力求写出最优解并且把朴素解、优化解、最优解分别实现一遍哪怕不提交只在本地跑自测用例。第三遍隔一周之后重新做一遍这次的目的是检验你到底有没有真的掌握。如果第二遍能AC但第三遍还卡壳说明当时是背题解的不是真正的理解。整个流程走下来你会发现自己对于哈希表、堆、树状数组、动规这些知识点的掌控力会有明显提升。这比零散地刷几十道LeetCode更有价值。最后分享一个小技巧笔试题里凡是有“窗口”“区间”“连续子序列”这些关键词优先想滑动窗口 数据结构维护凡是有“最大”“最小”“最优”优先想动规、贪心凡是有“数据量特别大”“超过内存能放下的范围”优先想哈希、离线、分批处理。这几个套路能覆盖后端笔试百分之八十以上的题型。