搜狗2019秋招研究员那场笔试的第二场编程题我到现在复盘起来还是挺有感触的。研究员岗的编程题不会上来给你一道特别偏门的数据结构题而是把几个核心算法的变形放在一起考察你快速建模和代码落地的能力。当时卷子上我记得是四道编程题覆盖了字符串处理、动态规划、图搜索、二分答案这几个方向语言不限但既然要快速写我基本都选了Python。这篇文章把其中几道印象比较深的题目整理成合集用Python重新解一遍顺便聊聊这类题在笔试环境里容易踩的坑。适合正在准备算法岗、研究员岗笔试的同学参考也适合想系统刷一波高频题型的同学当复习提纲。1. 搜狗2019秋招研究员第二场编程题的考察方向先说整体感受。第二场的四道编程题难易分布比较明显前两道偏基础后两道需要多转几个弯。它不是考你能不能背出某个算法的模板而是考你能不能把一个具体问题转化成已知的算法模型。比如字符串那道题表面上是括号匹配实际上是个贪心计数问题数组那道题表面上是查找实际上是二分的边界处理。这种出题风格对研究岗来说其实很友好因为研究员写代码通常不是为了刷题而是为了验证想法你得有快速把想法落地成代码的能力。另外要说的是时间安排。我印象中第二场考试时长是一个半小时左右四道题如果每道都死磕最优解时间会很紧张。我的建议是先把每道题都扫一遍判断难度先拿掉两题必拿分的基础题再花时间啃难题。我记得我当时的策略是第一题字符串和第二题DP优先搞定第三题搜索用BFS写第四题二分单独留了二十分钟最后还留了五分钟做整体检查。这个节奏下来基本能保证得分率。题目设计上还有一个明显特点边界条件非常阴险。四道题里至少有三道暗藏了数组越界、空输入、重复值之类的问题。如果你平时做题只关注主流程、不看边界这场的分数会很难看。所以后文里的代码我都会把边界处理单独标出来讲清楚。2. 编程题核心算法拆解字符串、DP、搜索、二分2.1 字符串问题交换括号使字符串平衡第一道题我记得是给一个只包含左括号和右括号的字符串长度是偶数且左括号和右括号数量相等但排列顺序是乱的。你每次可以交换任意两个位置的字符求出让整个字符串变成合法括号序列的最少交换次数。这类问题有一个经典的贪心解法遍历整个字符串用一个计数器 balance 维护“当前未匹配的左括号数量”。遇到左括号就加1遇到右括号就减1。一旦 balance 变成负数说明当前位置的右括号太多了必须从后面某个位置交换一个左括号过来。每做一次交换balance 加2交换次数加1。为什么每次 balance 为负时交换一次就是最优解因为题目保证左右括号总数相等所以字符串整体一定可以通过交换变得合法。当你走到某一个位置发现右括号比左括号多意味着这里至少需要一次交换来改变局面。如果拖到后面再处理反而可能让局部失衡更严重。这就是典型的贪心局部最优可以达到全局最优的场景。2.2 动态规划环形数组打家劫舍第二道题是一个常见的“打家劫舍”变种但加了一个环形条件有一排房子围成一圈相邻的房子不能同时抢第一个房子和最后一个房子也相邻求能抢到的最大金额。如果没有环形条件这就是一个非常基础的线性DPdp[i] max(dp[i-1], dp[i-2] nums[i])。加上环形之后核心矛盾变成了“首尾不能同时选”。处理方式也很标准把环形问题拆成两个线性问题。一种是“肯定不选第一个房子”那么最后一个可以选范围是 nums[1:]另一种是“肯定不选最后一个房子”那么第一个可以选范围是 nums[:-1]。分别跑一次线性DP取最大值同时单独处理只有一间房子的特例。思路说起来简单但笔试现场能快速意识到这一点需要你对DP的状态设计非常敏感。2.3 网格搜索求最大岛屿面积第三道题是二维网格问题。网格由 0 和 1 组成1 表示陆地0 表示水面相邻的 1 属于同一个岛屿需要找出最大的岛屿面积。这个题本质上是求无向图连通块的大小可以用 DFS 或 BFS 做。DFS 版本写起来最直观从每个未被访问过的陆地点出发向上下左右四个方向递归把访问过的点标记成 0 或者用一个 visited 数组记录避免重复计数。实际笔试时建议直接用 DFS因为它代码量少、不容易出错。但要注意 Python 的默认递归深度只有 1000 层左右网格很大的时候一定要用 BFS 或显式栈或者先用 sys.setrecursionlimit 提高递归深度。这种题不考察复杂算法但考察基础代码能力方向数组怎么写、边界判断怎么写、怎样保证不重复访问。很多人觉得简单一写就崩恰恰是因为细节没到位。2.4 二分答案旋转数组中的最小值第四道题是给一个旋转后的升序数组比如 [4,5,6,7,0,1,2]求最小值。常规解法是二分查找时间复杂度 O(log n)但这里有一个关键的判断逻辑每次取中点 mid如果 nums[mid] 大于 nums[right]说明最小值在右半部分left mid 1否则最小值在左半部分或者就是 midright mid。这个模板和普通二分查找不太一样它收缩的是“存在最小值”的区间而不是“等于 target”的位置。这道题最阴险的地方在于当数组本身就是完全升序、没有真正旋转过时标准模板也能正确返回第一个元素。但要小心处理元素重复的变体如果存在重复值边界判断会失效需要额外收缩幸好原题基本都假设没有重复元素否则就得退化成线性扫描确认了。3. Python实现四类编程题的完整代码与避坑细节3.1 字符串交换次数贪心计数的完整实现def min_swaps(s: str) - int: balance 0 swaps 0 for ch in s: if ch (: balance 1 else: balance - 1 if balance 0: swaps 1 balance 2 return swaps这段代码很短但我在笔试现场差点写错。问题出在 balance 0 的处理上交换之后为什么是加2而不是加1因为当前这个位置原本是右括号你从后面换过来一个左括号之后这个位置变成了左括号balance 要加1同时你又把一个右括号换到了后面那个位置的 balance 影响在后续遍历中会被重新计算但为了让当前状态立即合法只需要让 balance 回到非负就行所以实际上当前位的修正需要把 balance 增加 2。这是这道题最核心的“为什么”。另一个容易忽略的点是输入字符串长度可能很大频繁用字符串切片或者列表拼接会超时。直接用单指针遍历就够了不要在循环里做多余操作。还有如果测试用例里出现了左右括号数量不等的情况这个贪心解法会失效但原题明确说明数量相等所以不必额外判负。3.2 环形打家劫舍DP拆解与滚动变量优化def rob_line(nums): prev, cur 0, 0 for num in nums: prev, cur cur, max(cur, prev num) return cur def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] return max(rob_line(nums[:-1]), rob_line(nums[1:]))这个写法比维护 dp 数组更省空间。笔试时我看很多同学习惯开一个 n 长度的 dp 数组但研究员岗题目如果数据范围到 10^5内存虽然够滚动变量更稳妥。注意 rob_line 里prev, cur cur, max(cur, prev num)这行的赋值顺序必须先用旧值计算新 cur再整体更新否则会拿被修改过的 prev 来计算结果直接错。还有一点环形数组拆分成两个子问题时分别对应“包含尾部、不包含头部”和“包含头部、不包含尾部”。但如果数组中只有两个元素两个子问题分别是 nums[:-1] 和 nums[1:]算下来其实只能抢一个结果没错。这个细节我在验证时自己跑了一遍才放心。3.3 最大岛屿面积DFS与BFS两种写法DFS递归版本def max_area_of_island(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) max_area 0 def dfs(r, c): if r 0 or r rows or c 0 or c cols or grid[r][c] 0: return 0 grid[r][c] 0 area 1 for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)): area dfs(r dr, c dc) return area for r in range(rows): for c in range(cols): if grid[r][c] 1: max_area max(max_area, dfs(r, c)) return max_area这里我直接把访问过的陆地置成0免掉了 visited 数组省内存也快。但有一个前提题目允许修改输入网格。如果不允许修改就需要额外开一个 boolean 数组否则会污染数据。笔试时如果题目没说清楚我一般优先用 visited 方案避免后面其他题目还要重复用这个网格。用递归 DFS 的话强烈建议在函数开头加上sys.setrecursionlimit(1000000)。不然网格尺寸一大递归深度很容易超过 Python 默认限制直接报 RecursionError。我在自己电脑上试过 500×500 的全 1 网格默认递归深度1000根本不够网上不少人也踩过这个坑。如果你对递归深度没把握那就用 BFS 加队列循环代替递归最稳妥。BFS版本from collections import deque def max_area_of_island_bfs(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) max_area 0 for r in range(rows): for c in range(cols): if grid[r][c] ! 1: continue q deque([(r, c)]) grid[r][c] 0 area 0 while q: cr, cc q.popleft() area 1 for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)): nr, nc cr dr, cc dc if 0 nr rows and 0 nc cols and grid[nr][nc] 1: grid[nr][nc] 0 q.append((nr, nc)) max_area max(max_area, area) return max_areaBFS里一定要在入队时立刻把格子置0而不是在出队时处理。如果出队时才置0同一个格子会被多个相邻节点重复入队会直接导致死循环或者面积计算错误。这个细节非常关键我在本地测试时专门验证过确实是新手最容易忽略的问题。3.4 旋转数组最小值二分边界怎么收缩def find_min(nums): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] nums[right]: left mid 1 else: right mid return nums[left]这题代码不长但边界很容易搞混。核心思路是整个旋转数组可以看作两个递增段左边段的元素都比右边段大。最小值一定在右边段和左边段交界处偏右的位置。如果nums[mid] nums[right]说明 mid 落在了左边递增段最小值在 mid 的右侧所以把 left 推到 mid 1。如果nums[mid] nums[right]说明 mid 在右边递增段内最小值可能在 mid 或 mid 左侧所以让 right mid而不是 mid - 1否则会丢失答案。当你把 right 收缩到 left 相等时循环结束返回 nums[left]。这里我用的是开区间收缩的思路每次保持解在 [left, right] 闭区间内。笔试的时候我建议不要硬记模板而是用一个具体例子推一遍[4,5,6,7,0,1,2]left0right6mid3nums[3]7 nums[6]2所以 left4再继续。这样推一遍之后边界就不会写错。4. 笔试实战中的输入输出和调试技巧4.1 用sys.stdin.read统一读入减少IO时间笔试环境里Python的 input() 逐行读在数据量大的时候非常慢。我一般不管题目需求直接import sys然后data sys.stdin.read().split()再用索引按顺序取数。这样既避免 input() 的性能问题也方便快速解析多组输入。对于研究员岗的笔试代码准确性比可读性重要能用一行解决的问题不要拆开写十行。import sys def main(): data sys.stdin.read().split() t int(data[0]) idx 1 for _ in range(t): n int(data[idx]); idx 1 arr list(map(int, data[idx:idxn])); idx n # 处理当前测试用例 ... if __name__ __main__: main()这种写法还能帮你避免一个隐藏问题input() 在循环里如果遇到空行会报 EOFError而用 sys.stdin.read() 一次性读完就不会有这种问题。我当年笔试时有几道题就是因为空行处理不当导致本地跑得好好的在线判题直接崩溃。4.2 本地调试时准备一个暴力解法做对拍对于算法题尤其是二分和贪心我总是建议先写一个时间复杂度更高但绝对正确的暴力解法然后生成小规模随机数据对拍。比如旋转数组最小值可以用 min(nums) 做基准最大岛屿面积可以用一个 visited 数组的标准 DFS 做基准。对拍能最快发现边界条件下代码的隐藏问题。我当时在准备搜狗这类笔试时自己写了一个简单的random_test.py每次生成几百组随机输入比较两份代码的输出是否一致。这个习惯帮我排查掉了至少三四个隐藏在角落里的边界 bug。对拍脚本本身不复杂核心就三步构造随机数据、跑两个函数、对比结果。4.3 注意Python的递归深度和默认栈空间前面提到过递归 DFS 在一维和二维问题上都容易踩递归深度坑。Python 默认递归深度是 1000也就是说如果一个图或者一棵树的链条长度超过 1000递归解法会直接抛异常。笔试现场如果不想被迫改成迭代最好在一开始就写import sys sys.setrecursionlimit(1000000)但这里也要提醒一句递归深度设太大如果程序本身有死循环反而会消耗大量内存导致栈溢出。所以这个设置只是兜底不能成为你避开正确逻辑的借口。对于链表、树、图这类递归天然适用的结构能用迭代尽量用迭代比如树的遍历用显式栈图的遍历用 BFS。5. 编程题常见错误排查速查表每次笔试完我都会把自己犯错的地方记录成表格方便下一次复习。这里整理一张通用排查表其实就是这些年做算法题和实际笔试中反复出现的问题。问题表现可能原因排查与解决方案代码超时循环内嵌了字符串切片或数组拷贝尽量用下标访问避免每次循环都复制一遍数据递归报 RecursionError默认递归深度不够增加 sys.setrecursionlimit 或改为 BFS/显式栈二分死循环left 和 right 更新条件写成了 right mid - 1先跑一个具体例子验证区间收缩方向BFS 面积重复计算出队时才标记访问导致节点重复入队在入队时立刻标记而不是出队时标记贪心结果偏大或偏小没有理解局部决策对全局状态的影响写一个暴力解法用随机数据对拍数组下标越界网格边界判断漏写或漏了空输入判断统一用 0 r rows 的写法不要省略动态规划结果错空间优化的变量更新顺序不对拆分步骤先算新值再赋给旧变量输出格式不对多个空格或缺少换行按题目样例严格对齐最后不留多余空格这张表其实通用到什么程度呢就算你不是在打搜狗笔试而是在做其他公司的在线评测或者参加一些编程等级考试遇到的现象也都差不多。比如现在很多人刷Python编程题从一级到三级考的都是这类基础逻辑只是数据范围和题目包装略有不同。算法题的题眼从来不是背模板而是复述出问题到思路的转化过程。如果这道题你能讲清楚“为什么用这个方法”基本就稳了。还有几个实战小细节值得单独说一下第一在线编辑器里如果支持多种语言Python 3 通常是最好的选择不等于 C 没用而是研究员岗位的笔试更看重快速表达思路Python 的语法糖能帮你少写很多无用代码。第二提交前一定要自己构造几组边界数据比如空数组、单个元素、全部相同元素、已经有序的数组。我在搜狗这场考试中就因为没考虑“数组已经有序”的情况差点在旋转数组最小值上丢分。第三遇到不会的题不要空着把暴力解法写出来至少能拿部分分也可以给面试官留下“这个人会分析问题”的印象。最后再分享一个小技巧从搜狗这第二场笔试里我学到最有用的一个习惯不是某道题的解法而是“每个核心算法都要准备一个最小可用的模板库”。不是网上那种粘贴下来却看不懂的模板而是你自己推导过、改造过的版本。比如二分查找我整理成一套可以处理“找最小合法值”“找旋转点”“找峰值”的通用框架网格搜索我整理成一套 DFS 和 BFS 都对得上的方向数组写法。这样不管笔试遇到什么包装都能很快套回自己的框架节省大量现场思考时间。如果你最近也在准备算法岗、研究员岗的笔试我建议你拿这几道题的类型去刷一遍字符串贪心、环形DP、岛屿类搜索、二分边界查找。不要只刷一遍而是隔几天重写一次直到能闭着眼把代码写对、写快。这种肌肉记忆比考前几天临时背几百道题实用得多。