先说一个很多候选人都有的误区准备后端笔试第一反应是去刷高频题、背模板却忽略了最该研究的是“这家公司的业务基因决定了它爱考什么”。搜狗的后端笔试无论哪一年、哪一场都带着明显的搜索和输入法业务烙印——字符串处理永远是大头动态规划永远藏在业务场景后面数据结构考察往往朴实但极其吃基本功。2019秋招后端工程师第一场整体给我的感觉就是不偏不怪但每一题都踩在基本功的刀刃上。这篇文章不是给你贴一份原题清单而是基于搜狗后端笔试一贯的命题风格把这类笔试里最高频、最容易翻车的几类题型拆开讲透从解题思路、代码模板到考场上真实的时间分配和自查方法全部按我自己的实战经验来写。准备后端笔试的应届生、想转行做后端的开发者、以及想拿大厂offer但对编程题没底的同学都可以直接照着这份思路去练。1. 搜狗后端笔试的命题偏科为什么字符串和动态规划总是主角1.1 由业务基因决定的考点倾向搜狗的业务线是搜索、输入法、AI问答这些东西后端工程师每天面对的核心问题就是用户输入了一段文本系统怎么在毫秒级把它处理好。这个业务逻辑延伸到笔试题目里就变成了非常明确的考察倾向。2019秋招第一场后端编程题我复盘下来题型分布大致是题型大类出现频次核心考察点字符串处理高匹配、分割、字典序、子串统计动态规划中高状态设计、转移方程、边界初始化数据结构设计中栈、队列、堆的灵活运用数学/模拟中同余、幂次、二分查找字符串处理排在第一位一点都不意外。搜索业务倒排索引里要处理分词结果输入法引擎里要匹配用户输入的拼音序列这些落到算法题上就是字符串匹配和处理的变体。所以备考搜狗先把字符串类题目刷透性价比最高。1.2 从三道典型题看命题人的出题逻辑我选了三个和那场笔试高度同源的题目类型来复盘每一类都能看到搜狗业务场景的影子。第一类是“给定一个字符串统计满足某种条件的子串数量”。这对应的是输入法里的候选词生成逻辑——从一串拼音里切分出所有可能的合法词组合就是典型的子串统计问题。这类题拿到手第一反应必须是能穷举吗不能就上动态规划或者前缀和优化。第二类是“在有序数组中查找目标值”但会套一个旋转或者偏移的壳子。搜索系统的索引分片经常需要做范围查找考的就是二分查找到底是死记硬背还是真正理解。第三类是“设计一个支持某种操作的数据结构”比如最小栈、循环队列。后端面试几乎所有公司都爱问搜狗也不例外因为缓存设计、连接池这些实际工作里全是栈和队列的应用。1.3 输入输出格式的处理细节笔试翻车第一大源头搜狗这场笔试用的是牛客网平台绝大多数题目要求从标准输入读数据把结果打印到标准输出。这里面的坑非常多。最典型的坑是题目给了多组测试用例但没明确告诉你输入什么时候结束。常见的有两种约定一种是以固定数字n开头后面跟n条数据这种最简单先读n再循环读就行。另一种是读到文件末尾为止也就是EOF结束。很多人死在第二种上因为循环条件写错导致只能通过部分测试用例。// C 处理以EOF结束的多组输入 #include iostream using namespace std; int main() { int n; while (cin n) { // 处理一组数据 cout result endl; } return 0; }# Python 处理多组输入直到EOF import sys for line in sys.stdin: line line.strip() if not line: continue n int(line) print(compute(n))还有一个坑是行尾空格和换行符。牛客平台的判题系统对输出格式的要求不如ACM严格但多余的空格仍然可能导致Presentation Error。统一的做法是所有输出最后都手动加一个换行符行内不要有多余空格所有需要空格分隔的用join拼好。我自己刷题的习惯是每道题写完核心逻辑后至少花30秒检查输入输出那段代码。笔试时最冤的死法不是题不会做而是读入逻辑写错导致0分。2. 字符串匹配与子串统计题从暴力到出奇迹的完整演化2.1 这类题的标准解题框架搜狗后端笔试里字符串题基本都会涉及“字符频率统计”“子串计数”“结果取模”三个要素的组合。取模这个点很多人会忽略但搜狗这类业务体量的公司字符串长度动辄10^5甚至10^6结果不取模根本存不下。这类题的标准拆解方式我总结为四步第一步读完题先判断字符串长度范围。长度小于100的暴力双重循环没问题长度达到10^5的必然需要O(n)或者O(n log n)的做法别再想纯暴力。第二步识别题目要的是“数量”还是“最值”。要数量大概率跟排列组合和前缀和有关要最值大概率用滑动窗口或者单调栈。第三步找固定点。字符串题几乎都有一个不变性质比如字符集大小固定为26或者回文串的中心位置固定。把这个性质找出来解题思路就通了一半。第四步写代码前先想清楚边界条件。空字符串、全相同字符、长度为1的串这三种边界必须在纸上过一遍。2.2 经典例题统计只包含一种字符的子串数量这类题在搜狗笔试的变体非常多。原题大概是给定一个只包含小写字母的字符串s问有多少个子串其中的所有字符都相同。暴力求解很容易写——枚举所有子串对每个子串检查是否所有字符相等复杂度O(n^3)字符串稍微长一点就挂了。实际上这题有非常漂亮的做法。观察到“所有字符相同”的子串本质上就是字符串里每一段连续相同字符组成的区块内部的子串。比如字符串aaabbc可以分成三个区块aaa、bb、c。aaa这个区块内部所有子串都只包含一种字符子串数量是3 2 1 6。这里的关键是数学推导。一个长度为len的连续相同字符区块内部有多少个子串答案是len * (len 1) / 2。因为长度为1的子串有len个长度为2的有len-1个以此类推。def count_substrings(s: str) - int: n len(s) if n 0: return 0 ans 0 cnt 1 for i in range(1, n): if s[i] s[i - 1]: cnt 1 else: ans cnt * (cnt 1) // 2 cnt 1 ans cnt * (cnt 1) // 2 return anscnt * (cnt 1) // 2这里用的是整数除法因为组合数必然是整数。这个题要是放在后端场景里直接对应输入法里连续同音字序列的候选个数统计搜狗考这个方向简直不要太合理。2.3 升级版字符频率统计与回文判定搜狗这类笔试的升级套路是在基础子串统计上叠加“字符频率”“回文”等条件。比如这类变体给定字符串s找出最长的子串使得该子串中所有字符的出现次数均为偶数。这种题型直接用暴力O(n^3)必死。正确的做法是把“字符奇偶性”这个状态用位运算压缩。因为字符集是小写字母只有26个可以用一个26位的整数表示某个前缀中每个字符出现次数的奇偶性。某一位为1表示这个字符出现了奇数次为0表示出现了偶数次。然后利用前缀和的思路[l, r]子串满足条件当且仅当前缀状态state[r] state[l-1]。所以要把每种状态第一次出现的位置记下来遍历时更新答案。def longest_even_substring(s: str) - int: # 记录每个状态第一次出现的位置 first_pos {-1: 0} # 空前缀的状态0位置记为-1初始长度0 mask 0 ans 0 for i, ch in enumerate(s): mask ^ 1 (ord(ch) - ord(a)) if mask in first_pos: ans max(ans, i - first_pos[mask]) else: first_pos[mask] i return ans这题的思维量在于把“字符频率”压缩成“状态哈希”把O(n^2)的子串枚举降成O(n)的一次遍历。笔试考场上能独立想出来的人不多但如果你提前练过“状态压缩 前缀异或”这个组合10分钟内就能写出来。3. 动态规划题状态定义对了代码三十分钟能写完3.1 动态规划题怎么一眼识别出来搜狗后端笔试的动态规划题披着业务外衣但内核非常清晰。识别这类题有几个记号题目里有“最大/最小”“多少种方案”“能否”这些词而且数据范围在10^2到10^4之间——范围再大用贪心范围再小用暴力唯独这个区间大概率是DP。另一个判断标准是当前决策会影响未来的选择。比如找零钱问题选了面额10的硬币之后剩下的金额还能不能凑出来依赖于后面的选择这种就有子结构重复适合DP。考场上最忌讳的是拿到题就套背包九讲或者最长上升子序列模板。我见过太多人看到“最优解”就直接开一个二维dp数组结果状态定义错了写到一半发现转移方程推不下去返工又来不及。3.2 一个典型的状态设计推演过程搜狗这场笔试考过的动态规划类型核心可以归纳成一个场景有一个序列需要你从中选取若干元素选和不选都会影响后续结果要求最优解。这个场景的具体案例就是“打家劫舍”类型一个数组nums不能选相邻的两个元素问最多能选出的元素和是多少。这个题的状态设计非常经典。定义dp[i]表示考虑前i个元素时能获得的最大和。转移方程是不选第i个元素dp[i] dp[i-1]选第i个元素dp[i] dp[i-2] nums[i]取两者较大值。def rob(nums): n len(nums) if n 0: return 0 if n 1: return nums[0] dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i-1], dp[i-2] nums[i]) return dp[n-1]这题在搜狗笔试里会换一层业务皮比如“不连续取样本”“间隔推荐商品”之类。但核心状态设计一成不变下标代表处理到哪里值代表当前最优。想清楚这个所有变体都能秒解。这里有必要讲一下为什么状态要这样定义。定义dp[i]为“前i个元素的最优解”是因为题目要求全局最优而全局最优天然包含局部最优。子问题具有重叠性dp[i]依赖dp[i-1]和dp[i-2]这就是重叠子问题。边界状况就是dp[0]和dp[1]要单独初始化。3.3 空间优化技巧从O(n)到O(1)的思维跳跃搜狗笔试机考环境里内存限制一般比较宽裕但空间优化是个很好的加分项也反映出你对DP是否真正理解。打家劫舍这个题dp[i]只依赖dp[i-1]和dp[i-2]前面的状态用不到了。所以不必开整个数组用两个变量滚动更新就行。def rob_optimized(nums): prev, curr 0, 0 for num in nums: # prev 相当于 dp[i-2]curr 相当于 dp[i-1] prev, curr curr, max(curr, prev num) return curr这两行滚动更新的代码和上面用数组的版本逻辑完全等价。一次遍历结束后curr就是答案。时间复杂度O(n)空间复杂度O(1)。这个优化的本质是dp数组的下标在转移过程中只在局部滑动时就不再需要完整数组。以后凡是看到转移方程只依赖前两个、前三个状态的题都可以做滚动压缩。不光是打家劫舍斐波那契数列、爬楼梯、最长湍流子数组全都可以这样优化。4. 模拟与数据结构题笔试限时下的取舍之道4.1 模拟题容易“一看就会一写就错”搜狗后端笔试里经常有一两道模拟题描述一个业务规则让你逐步模拟。这种题算法难度不高但非常考编码细心程度。常见的设计是给定一个队列队列中每个元素有耗时和优先级按规则出队并计算总时间。我复盘过很多同学的笔试答卷发现一个规律模拟题挂掉的人十有八九是没把规则读完整。题目用三段话描述规则中间藏了一句“若优先级相同则按到达顺序”这句话漏看了整个实现就错了。我的经验是第一遍读题时把所有规则性描述都画出来尤其是“如果”“当”“否则”这些条件词。然后翻译成伪代码最后再落成正式代码。不要跳步笔试时间再紧这一步30秒的投入换来的是稳稳的AC。4.2 经典栈/队列设计题的笔试题型变化搜狗笔试考过一道非常经典的数据结构设计题要求设计一个支持push、pop、top和getMin四种操作的数据结构所有操作的时间复杂度都是O(1)。这道题的核心思路是用辅助栈。主栈正常存数据辅助栈同步存主栈每个时刻的最小值。当push一个值时如果该值比辅助栈栈顶小就往辅助栈压入该值否则压入辅助栈栈顶的旧最小值。这样两个栈高度始终相同getMin直接读辅助栈栈顶。class MinStack: def __init__(self): self.stack [] self.min_stack [] def push(self, x: int) - None: self.stack.append(x) if not self.min_stack or x self.min_stack[-1]: self.min_stack.append(x) else: self.min_stack.append(self.min_stack[-1]) def pop(self) - None: self.stack.pop() self.min_stack.pop() def top(self) - int: return self.stack[-1] def getMin(self) - int: return self.min_stack[-1]这里有一个很关键的细节辅助栈压入的要用x min_stack[-1]的等号。为什么因为如果等值元素出现多个比如先压3、再压3不带等号的话辅助栈第一次压入3第二次不压主栈pop一次之后辅助栈的最低值还是3没问题。但主栈再pop一次主栈为空辅助栈的栈顶还是3此时getMin返回3但栈已经空了逻辑就错了。带等号让辅助栈在每一次push时都有对应记录pop时同步弹出两个栈始终保持同步逻辑无懈可击。这种题考察的其实不是如何设计一个新的数据结构而是你是否能在现有数据结构的基础上做组合创新。4.3 笔试考场上的调试策略不依赖IDE的定位方法在实际笔试中很多同学遇到测试用例不过第一反应是打开IDE调试器——但牛客网这类在线平台调试能力有限正确的策略是先在脑子里推演一遍小数据再用print大法定位。我的调试三步法第一步把样例数据手动画出来。比如设计最小栈的题样例是push(-2), push(0), push(-3), getMin() - -3, pop(), top() - 0, getMin() - -2。我就在纸上画两个栈一步步模拟看哪一步和预期不符。第二步检查边界。空队列能不能pop空栈能不能top这些操作在题目默认情况下不会出现但你要确认题目确实保证了这一点。如果题目说不保证你的代码就要加保护。第三步小规模随机数据自测。用代码生成几个随机操作序列暴力实现一个正确但慢的版本和优化版本对比结果。笔试时间不够的话这一步可以只测5组数据。注意笔试考场上不要追求写出“完美无缺”的代码再提交。先提交一版能过样例的拿到部分分再逐步优化。很多在线判题系统是“通过部分测试点给部分分”的交白卷才是最大的浪费。5. 实战向的备考路线从刷题到模拟考试5.1 按搜狗考纲定制刷题清单如果你时间充裕我建议按下面的清单准备搜狗这类后端笔试。这个清单不是让你盲目刷题而是每个专题练到“闭眼睛能写出模板”的程度。字符串专题KMP、Trie树、字符串哈希、滑动窗口、双指针动态规划专题最长上升子序列、背包九讲前四讲、区间DP入门、状态压缩DP入门数据结构专题单调栈、单调队列、优先队列、并查集、链表与树的遍历数学专题快速幂、最大公约数、素数筛排序专题快排、归并排序、堆排序、桶排序每个专题刷30道题左右整体刷够150道后端笔试的编程题基本就稳了。关键是每道题做完之后要做总结把“这道题考察的状态是什么”“转移方程怎么来的”写下来而不是做完看下答案就扔一边。5.2 一套通用快读快写的输入输出模板后端笔试的编程题输入输出节奏快慢直接影响整场时间。我把自己常用的模板贴出来C和Java的同学可以直接抄。// Java 快读模板处理大量输入时效率明显优于Scanner import java.io.*; import java.util.*; public class Main { static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static String next() throws IOException { while (st null || !st.hasMoreTokens()) { st new StringTokenizer(br.readLine()); } return st.nextToken(); } static int nextInt() throws IOException { return Integer.parseInt(next()); } public static void main(String[] args) throws IOException { int n nextInt(); int[] arr new int[n]; for (int i 0; i n; i) { arr[i] nextInt(); } System.out.println(solve(arr)); } }// C 快读模板 #include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint arr(n); for (int i 0; i n; i) { cin arr[i]; } cout solve(arr) \n; return 0; }ios::sync_with_stdio(false); cin.tie(nullptr);这两行是C选手的死记硬背项它能显著提升cin的读取速度。不加这两行数据量到10^5以上时cin会明显慢于scanf。Java选手尽量别用Scanner数据一多就超时。5.3 考场上最容易忽略的三类优化搜狗的后端笔试编程题每题的数据范围通常会标在题目里。忽略数据范围去裸写算法是大多数同学超时的原因。第一类优化是排序预处理。很多题目直接模拟会超时但把数据先排个序后续就只需要线性扫描。比如求两数之和等于target的配对数量排序后双指针一遍过复杂度从O(n^2)降到O(n log n)。第二类优化是前缀和/差分。区间求和、区间更新这类题裸循环O(n)每次操作总体可能到O(n^2)但前缀和把单次区间求和降到O(1)。这个技巧在后端笔试里几乎场场用得上。第三类优化是哈希表缓存中间结果。记忆化搜索在本质上是带缓存的递归很多DP可以先用DFS写出来再加一个memo数组做缓存就能把指数级复杂度降到多项式级。我写DP时如果一时想不出递推式就会先写一个记忆化搜索版本验证思路正确性再改写成递推版。5.4 最后两周怎么练如果你的笔试时间是两周后不建议再开新专题了。这时候最有效的是两件事第一每天上午固定时间做一套模拟卷严格掐表90分钟模拟考场的紧张感。第二把之前所有做错的题重新做一遍重点看那些“第二次做还写不对”的题这才是你的真实薄弱点。模拟卷选什么可以直接用牛客网历年大厂真题卷或者按我上面列的专题从题库里抽题组卷。做题时不要开任何辅助工具也不要用IDE的自动补全尽量贴近真实笔试环境。我自己在备考阶段的体会是编程题水平爆发式增长不是发生在疯狂刷题时期而是发生在错题复盘的第三天到第五天。那些曾经卡住你三个小时的题第二次做对时给你带来的信心提升远比做十道简单题管用。6. 容易翻车的隐藏扣分点6.1 返回值类型与数据范围的匹配搜狗笔试里有两道题明确要求结果对1000000007取模。对10^9 7取模是后端笔试的经典操作但这并不是所有的题都要求取模。真正容易翻的点是中间计算早就溢出了最后才取模等于白取。比如求组合数直接算n! / (k! * (n-k)!)在n10^5时中间结果早溢出成负数了最后取模结果完全不对。正确做法是每一步都对MOD取模或者用乘法逆元把除法转成乘法。MOD 1000000007 def mod_pow(a, b): # 快速幂算法求 a^b % MOD res 1 while b 0: if b 1: res res * a % MOD a a * a % MOD b 1 return res # 组合数 C(n, k) 使用质数模下的乘法逆元 def comb_mod(n, k, mod): if k 0 or k n: return 0 num den 1 for i in range(k): num num * (n - i) % mod den den * (i 1) % mod return num * mod_pow(den, mod - 2) % mod如果不熟悉费马小定理也可以直接用Python的大整数运算——Python的整数无限大不会溢出最后再取模就行。但C和Java选手在中间计算时就要用long long甚至unsigned long long如果还不够就得用模乘。6.2 多组输入时全局变量的重置多组测试用例的题目每组数据独立。很多人的代码在单组数据下没问题多组数据一起跑就出bug原因是全局变量没有重置。比如用全局数组存访问标记第一组数据跑完数组里的标记位没清零第二组数据就会受污染。正确的做法是要么每组数据都在局部声明这些变量要么在每组数据处理完后手动清理。这个错误非常隐蔽因为本地测试时每组数据是单独运行看不出问题但在线判题系统是同一个进程连续跑多组数据问题立刻暴露。我自己处理的方式是凡是用到全局数组或者全局集合的题目在每轮循环的开头统一执行一次初始化函数。6.3 读题顺序与时间分配的实操建议一场后端笔试大概90分钟3到4道编程题。我的时间分配固定是前5分钟把全部题快速扫一遍标注每道题的题号和难度直觉第5到15分钟从最简单、最有把握的题开始做拿到第一波分第15到60分钟主攻中等难度题一题最多花20分钟超过就跳过第60到80分钟做最后的难题不会就用暴力先拿部分分第80到90分钟统一检查一遍输入输出格式和边界条件这个分配的关键原则是不在难题上死磕超过20分钟。后面还有3道题等着你一道题卡死整场心态就崩了。笔试跟面试一样战略上要田忌赛马——先把确定能拿的分全部拿到再想着拉开差距。我自己见过太多同学前面的题写得飞快卡在最后一道难题上导致简单题反而没时间检查最后简单题因为小bug丢分难题也没做出来两头空。6.4 考后复盘比考中手感更重要笔试结束后不管考得好不好第一时间把题目大意记下来。搜狗这类大厂的笔试题目很多时候是多个部门共用的题库下一年或者秋招补录时可能会换个数字再出一次。你当时没做出来的题复盘时彻底搞懂下次再遇到就是送分题。复盘的具体做法是对照题解把正确解法自己重新写一遍然后对比自己的思路和正确答案的差异在哪一步——是状态定义的方向错了还是边界条件没考虑全。把差异记录下来下次考前翻一遍比盲目刷新题有用得多。我个人习惯是每场笔试后写一个复盘文档分类记录“看错题意的题”“思路对的题”“完全没思路的题”三类下次备考直接翻这个文档半小时就能把考点全部捡起来。这个方法我从秋招一直用到工作后面试别人才意识到它有多珍贵——大部分人的刷题量是够的缺的是对每一道错题的深度复盘。