瓜子二手车2019秋招算法笔试卷2这套题我一直想找机会好好复盘一下。当时做完最大的感受是整体难度中等偏上数据结构与算法占比很高机器学习部分考得比较基础但很细编程题算是对基本功的全面体检。特别是KMP的next数组、动态规划的状态设计、贪心的反例敏感度三道题连续出现如果你只是刷过题但没有真正理解原理很容易在考场上卡壳。这篇文章我会把整套卷子的考察逻辑拆开按模块把每个考点的解法、原理、易错点完整还原一遍也会分享一些我自己复盘时总结的注意事项给准备算法岗秋招的同学一个可参考的复习方向。1. 试卷整体画像这份卷子真正想筛什么样的人先说结论这套卷子不是那种“背熟了剑指Offer就能过”的类型也不是“全靠ACM竞赛功底碾压”的类型。它处在两者之间但更偏重后者一点点。考察范围覆盖了数据结构与算法、机器学习基础、概率统计、编程实现四个模块题型大致是选择题简答题两道编程题的结构。1.1 高频考点分布与对应分值逻辑从考试的设计逻辑来看这部分分值的分布是这样的逻辑模块典型考点考察意图数据结构与算法KMP、排序、堆、链表考察基本功是否扎实能否写出无bug的代码动态规划与贪心背包变体、区间调度、状态压缩考察建模能力和对“最优子结构”的理解机器学习基础过拟合、特征工程、评估指标考察是否真正做过模型而不只是看过书概率统计贝叶斯、期望、方差考察数学功底这是算法岗的底线编程题DP、DFS/BFS、双指针考察代码实现的速度和正确性所以说这份卷子筛的是两类人一类是基本功极其扎实、刷题量大的人另一类是虽然刷题量一般但对每个算法的原理理解得很深、能灵活变形的人。最怕的是“背题选手”题目稍微改个条件就崩。1.2 时间分配上的一个关键判断我印象很深的是这套卷子的题量不算特别大但计算量不小尤其是KMP手算next数组和几道概率题每一道都需要你踏踏实实算。我当时的时间分配是选择题控制在35分钟左右简答题控制在40分钟剩下45分钟给两道编程题。编程题是“先写对再优化”的思路——面试官不会只看最终代码还会看你写在草稿纸上的推导痕迹所以步骤写清晰比直接甩一个AC代码更重要。2. 数据结构题的精髓KMP的next数组到底怎么手算最快这份试卷里有一道让我印象深刻的KMP题目题目直接给了模式串pabacaba要求写出next数组。这不是一道难题但很能区分“背模板”和“真理解”的人。如果你只是背过代码遇到“next[i]到底代表什么”这种语义题很容易踩坑。2.1 “abacaba”的next数组逐位推导过程我们需要先约定next数组的定义。不同教材和不同公司的定义可能略有差异这套卷子的定义是next[i]表示模式串前i个字符组成的子串中最长相等真前缀和真后缀的长度当不存在相等真前后缀时记为0。对于模式串p abacaba我们逐位来计算i1子串是a没有真前后缀next[1]0。i2子串是ab真前缀有a真后缀有b不相等next[2]0。i3子串是aba真前缀a与真后缀a相等长度为1更长的ab与ba不相等next[3]1。i4子串是abac前缀a与后缀c不相等前缀ab与后缀ac不相等前缀aba与后缀bac不相等next[4]0。i5子串是abaca最长相等真前后缀是anext[5]1。i6子串是abacab前缀ab与后缀ab相等长度为2next[6]2。i7子串是abacaba前缀aba与后缀aba相等长度为3next[7]3。所以完整的next数组是[0, 0, 1, 0, 1, 2, 3]。2.2 手算过程中的两个高频易错点第一很多人在算next[6]的时候会犹豫前缀a和后缀b不匹配但是前缀ab和后缀ab匹配这里要注意相等真前后缀必须是连续的且前缀和后缀不能重叠到只剩一个字符。第二如果你用的定义是“失配时跳转的下标”有些地方叫next[j] 最长公共前后缀长度 1那数组会整体变成[0, 1, 1, 2, 1, 2, 3]这种形式。这两种定义都不算错但如果你习惯了其中一种考试时一定要先看清楚题目给的是哪种这是我最想提醒大家的地方。2.3 为什么秋招笔试喜欢考KMP的手算KMP的价值不在于KMP本身而在于它考察了你对“字符串匹配暴力算法为什么慢”这个问题的理解深度。暴力算法在匹配失败后只能把模式串右移一位而KMP利用已经匹配的信息让模式串尽量多跳几步。手算next数组的过程实际上就是在考察你是否理解“相等真前后缀”的物理意义。除了KMP这套卷子的选择题里还出现了快速幂和堆排序的相关考点快速幂考察的是“二进制分解指数”的思维而堆排序问的是建堆的时间复杂度。这些都是常规内容但如果不亲自动手推一遍很容易忘。3. 动态规划与贪心从瓜子业务场景引申出的建模题当时卷子里有一道动态规划题让我觉得很“应景”它没有直接说“0-1背包”而是包装了一个场景一个门店有若干辆车每辆车有预估整备成本和预期售价你的预算有限要选择一组车辆使得总收益最大化。本质上这就是0-1背包问题。3.1 从业务场景到DP状态的建模过程这类题的难点不是背出状态转移方程而是如何把一个看起来不像背包的问题抽象成背包。我当时是这样分析的把“每辆车”看成“一个物品”。把“整备成本”看成“物品重量”。把“预期售价减去收车成本”看成“物品价值”。把“总预算”看成“背包容量”。状态定义dp[j]表示预算为j时能获得的最大收益初始化为0状态转移方程是dp[j] max(dp[j], dp[j - cost[i]] value[i])其中j从总预算倒序遍历到cost[i]。倒序遍历是0-1背包和完全背包的关键区别。如果正序遍历同一辆车会被重复选择多次那就变成了完全背包。这个细节是我在实际做题中反复栽过跟头的地方笔试时如果你在草稿纸上先写出“j正序”的错误版本再改成倒序也是可以拿大部分分数的因为面试官能看到你的思路轨迹。3.2 贪心题的反例敏感度为什么“看起来对”往往不对这套卷子的简答题里还考了一道区间调度问题有若干场线下活动每场活动有开始时间和结束时间问最多能参加多少场。对应的贪心策略是“按结束时间排序每次选结束最早且与已选活动不冲突的那场”。这是最经典的贪心策略但如果你只是背了答案没有理解为什么“按开始时间排序”或“按持续时间排序”是错的那你很可能在变种题上翻车。我当时在复盘笔记里专门给了一个反例活动A开始时间8结束时间12。活动B开始时间8结束时间9。活动C开始时间9结束时间10。活动D开始时间10结束时间11。如果按开始时间排序你会先选A然后发现B、C、D都冲突最多只能参加1场但如果按结束时间排序你会选B、C、D三场。这个反例说明贪心策略的选择依据是“哪个维度能让未来有最多可选空间”结束时间最早意味着你给后续活动留下了最充裕的时间窗口。3.3 动态规划的边界条件最容易丢分的地方动态规划题的边界条件是我这次笔试后的一个深刻教训。状态转移方程写对了但dp数组的初始化和越界处理没做好照样AC不了。以0-1背包为例dp[0]必须初始化为0表示预算为0时收益为0同时要注意cost[i]可能大于总预算这时候在状态转移中直接跳过就行。如果题目要求精确装满预算那dp数组需要初始化为负无穷只有dp[0]0。这套卷子的题干没有明确说明“是否可以剩余预算”这是一个隐藏的坑答题时一定要在代码注释里写清楚你的假设。4. 机器学习与概率统计数据驱动公司更看重的基础素养瓜子二手车本质上是一家数据驱动的公司所以算法岗笔试里机器学习相关的内容大概率会出现。这套卷子的机器学习题目不算难但考得很细属于那种“你没亲手训练过模型就会觉得模棱两可”的题。4.1 过拟合的判断题哪些手段“一定能”缓解过拟合有一道选择题大概是问下列哪些手段能缓解过拟合选项包括L1正则化、增加训练数据、增大模型容量、Dropout、交叉验证。如果对深度学习不熟悉看到Dropout可能会犹豫但它的原理是训练时随机丢弃部分神经元相当于多个子网络的集成效果上能起到正则化的作用。增大模型容量反而会加剧过拟合这是用来迷惑你的选项。这里我的经验是分析过拟合不能只背手段而要理解“过拟合的本质是模型记住了训练集中的噪声”。所有增加泛化能力的手段要么是“引入约束”正则化、Dropout要么是“增加多样性”更多数据、数据增强要么是“简化模型”剪枝、早停。4.2 贝叶斯公式的实际计算这类题一定要动手写公式概率统计部分有一道题让我觉得特别典型——已知某车型在二手车市场有缺陷的概率是1%检测设备的准确率是99%问如果一台车检测出有缺陷它真的有缺陷的概率是多少。这是一个标准的贝叶斯应用题但如果不写公式直接心算很容易得到错误答案。设事件A为车辆真的有缺陷事件B为检测结果为有缺陷那么P(A|B) P(B|A) * P(A) / (P(B|A) * P(A) P(B|¬A) * P(¬A)) 0.99 * 0.01 / (0.99 * 0.01 0.01 * 0.99) 0.5这个结果非常反直觉但它是贝叶斯公式的经典陷阱。即使在检测准确率高达99%的情况下因为缺陷率太低检测出有缺陷的车里真正有缺陷的也只有一半。复习这一类题时我的建议是永远不要把公式默背出来而是要把P(A)、P(B|A)、P(B|¬A)分别用文字写清楚尤其在时间压力下更要对齐符号的含义。4.3 模拟退火与粒子群等启发式算法题的答题策略这套卷子还涉及一些启发式算法相关的知识点比如模拟退火的Metropolis准则、粒子群算法的速度和位置更新公式。这类题的正确率很大程度上取决于你是否真正理解“探索”和“利用”的平衡。模拟退火的核心不是“降温”而是“在高温阶段容忍较差的解从而跳出局部最优”。粒子群算法里每个粒子的下一步移动受到自身历史最优位置和全局最优位置的共同牵引这个“牵引”如果设置得太强粒子群就会过早收敛到局部最优。考场上如果遇到这类简答题我建议先画出公式再解释每一项的物理含义比纯文字描述要更容易拿分。5. 编程题从暴力到最优的完整推导编程题是这套卷子的重头戏。两道题都是LeetCode中等难度偏上第一道是典型的DFS/BFS搜索题第二道是DP优化题。我当时第二道题做得不够好复盘后把完整推导过程写下来现在分享给你们。5.1 第一题岛屿数量变体的遍历策略第一道编程题是“给定一个二维矩阵0表示空地1表示车相邻的车属于同一批库存问一共有几批库存”。这是LeetCode 200题的变体只是把“岛屿”换成了“库存”。核心解法是DFS或BFS遍历。我选择的是DFS实现因为代码更简洁def num_islands(grid): if not grid or not grid[0]: return 0 count 0 rows, cols len(grid), len(grid[0]) def dfs(i, j): if i 0 or i rows or j 0 or j cols or grid[i][j] 0: return grid[i][j] 0 # 标记为已访问 dfs(i1, j) dfs(i-1, j) dfs(i, j1) dfs(i, j-1) for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 dfs(i, j) return count这里有一个很有价值的细节标记已访问时我直接在原数组上把grid[i][j]置为0省去了visited数组。这是一个空间复杂度上的优化也是面试官比较愿意看到的技巧。但前提是你必须确保后续不会再需要原始矩阵数据如果题目要求保留原矩阵就需要用额外的visited数组。5.2 第二题最长上升子序列的O(nlogn)优化第二道编程题是“给定一个数组求最长上升子序列的长度”。最直接的思路是动态规划dp[i]表示以nums[i]结尾的最长上升子序列长度状态转移方程是dp[i] max(dp[i], dp[j] 1)其中j i且nums[j] nums[i]。这个思路的时间复杂度是O(n^2)空间复杂度是O(n)在n比较大的时候会超时。我当时交的也是这个版本后来复盘发现了O(nlogn)的优化方法维护一个tails数组tails[k]表示长度为k1的上升子序列的最小末尾元素然后对每个nums[i]在tails中做二分查找。具体推导过程如下def length_of_lis(nums): import bisect tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这个方法的核心思想是“贪心 二分”tails数组本身是递增的所以可以二分查找。对每个新元素x如果x比tails中所有元素都大就扩展tails否则用x替换tails中第一个大于等于x的元素因为“更小的末尾元素”更有可能在未来接上更长的上升序列。这个“贪心”的直觉一定得理解否则背模板很容易在边界条件下出错。5.3 编程题的调试技巧如何用自定义用例快速定位bug复盘之后我总结了一套笔试中的调试流程。如果你的代码在大样例上报错了不要急着加print先用小样例快速验证核心逻辑。对于最长上升子序列这题我通常会用这么几个用例空数组输出0。单元素数组输出1。[1, 2, 3, 4, 5]完全递增输出5。[5, 4, 3, 2, 1]完全递减输出1。[10, 9, 2, 5, 3, 7, 101, 18]输出4。这些用例覆盖了边界、完全单调和混合情况。如果你的代码能通过这五个用例基本可以说明逻辑对了。但还有一个容易忽略的坑题目要求的是“严格上升”还是“非严格上升”。如果是严格上升需要用bisect_left如果是非严格上升需要用bisect_right。这套卷子题干写的是“上升”我当时默认理解成了严格上升后来发现如果不确定最好在代码注释里说明自己的理解。6. 那些笔试时容易忽略的隐藏扣分点最后来聊一聊分值之外的隐藏扣分点。这类细节一般不直接出现在题目里但恰恰是决定你能否进入面试环节的关键。6.1 代码风格和注释习惯笔试系统一般不会看注释但面试官会看你提交的代码。如果你的变量名全是i、j、k函数名是fun1状态方程写在注释里但不解释为什么面试官对你的印象分会下降不少。我的经验是变量名尽量语义化比如用cost而不是c用budget而不是b状态转移方程旁边加一行注释说明含义这样既方便自己检查也方便面试官快速理解思路。6.2 复杂度的计算要不要写在试卷上如果需要手写答案或在线答题但可以附文字说明一定要写上时间复杂度和空间复杂度。这是算法题的硬指标也是面试官判断你工程能力的重要依据。比如岛屿数量这道题时间和空间复杂度都是O(m*n)如果你不写面试官会默认你可能没算。对DP优化的题目一定要说明相比朴素版本优化在哪里以及为什么tail数组是单调递增的。6.3 覆盖高频题但别忽视冷门考点从这套卷子的考点来看KMP、堆排序、快速幂都属于“高频但容易被忽视”的考点因为很多人复习时只盯着动态规划和图论觉得字符串和基础数据结构简单。但实际上这些基础题才是最有区分度的。我记得考前一周我刚好重新推了一遍KMP和快速幂所以才在手算next数组时很从容。如果你现在正在准备秋招不要只顾着刷难题把你已经会的知识再做一遍系统梳理收益会更大。7. 这套卷子复盘完我最想留在最后的一句话笔试卷复盘这件事很多人只关心“对了几道”和“错了几道”但我认为更有价值的是“每一道错题背后的思维漏洞”。我做这套卷子的时候KMP的next数组一开始也算错了原因是我默认了“next[i] 最长相等真前后缀长度 1”这种定义而题目用的是另一种定义。这个错误和数据结构和算法本身没有关系纯粹是做题习惯问题——没有先确认题目定义。所以无论是准备笔试还是复盘题目我都会给自己定一个规矩分析任何一道题先问自己三个问题这道题的输入范围是什么边界条件是什么题目中的每个术语用的是哪一套定义把这三点想清楚再开始解题。这套瓜子二手车2019秋招算法笔试卷2的难度适中但它对“细致程度”的考察比很多标榜高难度的卷子更典型。如果你正在准备算法岗秋招不妨照着这个思路把近期做过的卷子重新梳理一遍你会发现自己能拿到的分数比预想中要高很多。