算法正确性
一个算法正确,是指它对每个合法输入都能终止,并且返回的结果符合输入输出的约定。只跑通题目给的样例证明不了这一点:样例往往避开了空输入、重复值和数值极限,而错误恰恰藏在这些地方。
现场编码时,正确性靠的是一条连贯的思路:先把约定问清楚,再用不变量说明代码为什么对,最后用边界用例和反例主动找错。面试官看重的也不只是代码能不能跑,还有你能不能说清它为什么对、在哪里可能出错。
1. 面试核心
先记住这几条,再读正文- 输入输出契约规定哪些输入合法、返回值表示什么、能否修改输入,动手前先确认会改变算法的那几条。卡 · 输入输出契约
- 循环不变量要在进入循环前成立、每轮更新后仍成立,循环退出时能由它推出答案。
- 最小反例只保留触发错误的关键输入,输入越小,越容易看出是哪条假设失效。卡 · 最小反例
- 对拍时,被测算法和基准算法各用一份独立的输入副本,并保存随机种子和失败用例。卡 · 随机测试与性质测试
2. 输入输出契约
输入输出契约是调用方和实现方共同遵守的约定:什么样的输入算合法,返回值代表什么,实现能不能改动输入。现场题给的信息常常不完整,不用每条都问到,优先确认会改变算法或返回结果的条件。可以从这些问题里挑:
- 输入数量和值域上限是多少?时间和额外空间限制是多少?
- 元素是否已排序,是否包含负数或重复值?
- 是否保证有解?无解时返回什么?
- 多解时返回任意解还是全部解?重复答案如何处理?
- 是否要求稳定的输出顺序?
- 能否修改输入,例如排序或原地压缩?
- 字符串按什么字符集与单位处理?图的边是否有方向和权重?
这些条件为什么重要?以两数之和为例:数组已排序可以用双指针,O(1) 额外空间;未排序就要用哈希表,或者先排序,而排序又会改动输入。要求返回全部组合时,还得约定重复答案怎么去掉。条件一变,实现就完全不同。
null、空输入和非法输入按接口约定处理即可。先把影响方案的关键条件确认下来,其余的直接说明你的假设,把时间留给推导和编码。
3. 不变量与复杂度
循环不变量是循环每次走到约定位置时都成立的事实。写代码前先把它说清楚,边界怎么初始化、每轮怎么更新、退出时返回什么,都能从它推出来,而不是靠试。
用不变量证明一个循环正确,要讲清三件事:
- 初始化:第一次进入循环前,不变量为什么成立?
- 保持:一轮更新后,它为什么继续成立?
- 退出:循环结束时,怎样由不变量推出答案?
这三件事只说明「如果循环结束,结果是对的」。循环会不会结束,还要找一个每轮严格推进、而且有界的量:二分的候选区间每轮缩小,单向扫描的下标每轮增加。数一数这个量最多推进多少次,顺便就得到了时间复杂度。
以 lower bound 为例,它查找第一个大于等于目标值的位置。它的不变量要说明候选区间左侧的值都小于目标、右侧的值都大于等于目标,这样才能解释所有元素都小于目标时为什么返回 n。right 的初值、left < right 的循环条件、更新时要不要加一,也都由这个不变量决定。完整定义和 O(log n) 时间、O(1) 辅助空间的推导见二分查找。
4. 类型选择
数据结构和类型选得能直接表达算法需要的操作,代码就更容易验证。Java 里常见的对应关系:
- 栈和队列用
ArrayDeque,从两端加入或移除元素。 - 频次和最近位置用
HashMap;值域很小时,直接用数组。 - 累加和、距离、乘积按上界选
long。 - 比较整数用
Integer.compare,避免相减溢出。 - 要求输出顺序稳定时,按要求排序,或者用
LinkedHashMap保留插入顺序。 - 递归深度可能接近 n 时,按数据规模考虑改用显式栈。
数值类型不光要装得下结果,还要装得下中间运算,见算法复杂度。
现场写代码,优先写能清楚体现不变量的版本。Stream、反射、并发工具只在题目确实需要时才用,否则只会增加验证的负担。
5. 构造测试用例
好的测试用例针对的是算法依赖的条件,每个用例都在验证一个具体的假设,而不是多跑几个普通样例。可以从输入大小、结构、数值和规模四个方向来选。
5.1 最小输入
最小的输入最容易暴露初始化和边界错误:
- 空数组或空字符串,检查初始化与返回约定。
- 单个元素,检查循环是否越界。
- 两个元素,检查一次比较、交换或区间推进。
5.2 结构边界
结构上的用例检查算法是不是只在某种排列下才对:
- 答案位于开头、结尾或中间。
- 输入没有合法答案。
- 元素全部相等,或全部不同。
- 元素按升序、逆序或交错顺序排列。
比如有序数组去重依赖「相同的值相邻」,用 [1,2,1] 这样交错重复的输入,就能看出这个前提有没有被说清楚。
5.3 数值边界
数值用例要让计算逼近类型的极限。用 0、负数、Integer.MIN_VALUE 和 Integer.MAX_VALUE 检查比较结果是否正确,再看加法、乘法和比较器里的减法会不会溢出。即使返回值是 long,中间的表达式也可能先按 int 算完,要单独检查。
5.4 规模边界
规模用例检查时间和空间能不能撑到输入上限:
- 最大 n 下,O(n²) 等方案是否超时。
- 链状树的递归深度是否接近节点数,导致线程栈溢出。
- 返回全部方案时,输出数量是否已经超过可承受的资源。
6. 最小反例
反例是让当前算法给出错误结果或无法终止的输入。不必等代码写完再找,提出方案时就可以试着构造反例,提前发现推导里的漏洞。
找到一个失败的输入后,逐步删掉无关的元素,每删一次都确认错误还能复现,当进一步删减都会让错误消失时,就得到了相对于这种删减方式的最小反例。这不保证它是所有可能输入里规模最小的那个,但已经有助于定位错误。输入越小,要跟踪的变量和执行路径越少,越容易看出是哪条假设失效了。
6.1 贪心反例
贪心按某条局部规则作选择,例如先选结束最早的区间,或先选面额最大的硬币。构造反例时,要让这条局部规则挡住更好的整体结果:对于“先拿最大收益”的方案,可以寻找先拿较小收益反而得到更大总结果的短输入。「优先用面额最大的硬币」的具体反例见贪心。
6.2 边界反例
边界反例让指针更新发生在最小的区间上。二分查找用长度为 1、2 的数组,就能检查每轮是否真的缩小了区间,死循环往往在这里出现。最长无重复窗口可以用 abba 检查 left 会不会倒退:处理第二个 a 时,它的旧位置已经在窗口外,left 应该保持不变。
6.3 相等性反例
Java 里有两种「相等」:equals 判断的对象相等,和比较器返回 0 的比较相等,测试时要分开看。哈希集合依赖一条约定:equals 相等的对象必须有相同的 hashCode。用两个违反这条约定的自定义键做测试,就能暴露哈希查找依赖的这个前提。
比较器对两个不同的对象返回 0 本身是合法的,但 TreeSet 会把比较结果为 0 的两项当成同一个元素,后加入的那个不会被存进去。所以要核对业务上的去重规则和比较规则是否一致。
6.4 溢出反例
比较器写成 a - b 时,取 Integer.MAX_VALUE 和 −1 就能让它出错:两者相减超出 int 上限,结果变成负数,比较器以为较大的值更小,把它排到了前面。改用 Integer.compare 后,把这组输入留作回归测试,防止同样的错误再出现。
7. 手动执行
手动执行是拿一个小输入,在纸上或白板上一步步记下核心变量的值,核对代码是否真的实现了你的推导。重点盯住边界的移动和答案的更新时机。下面用 ABA 检查最长无重复窗口:
| 步骤 | left | right(不含) | 无重复窗口 | 最长长度 |
|---|---|---|---|---|
| 初始 | 0 | 0 | 空 | 0 |
| 加入 A | 0 | 1 | A | 1 |
| 加入 B | 0 | 2 | AB | 2 |
| 加入 A | 1 | 3 | BA | 2 |
处理第二个 A 时,窗口里已经有 A,left 前进一格,窗口从 AB 变成 BA,最长长度仍是 2。手动执行时,顺带核对这几个问题:
- 每轮是否推进了指针,能够最终结束?
- 访问元素之前,索引是否处于合法范围?
- 加入与移除元素时,计数是否成对更新?
- 更新答案时,窗口是否满足题目约束?
- 结束后的返回值是否符合无解与空输入的约定?
现场可以边写表边解释每一步为什么这样更新,面试官能直接看到代码和不变量是怎么对应的。
8. 随机测试与性质测试
对拍是把同一个输入交给两个实现,比较它们的结果。通常一个是要验证的优化算法,另一个是写起来直观、只适合小规模的暴力解,作为独立的基准。再配上随机生成的输入,就能覆盖手写用例容易漏掉的组合。
下面是对拍框架的伪代码。随机数生成器用固定的种子(seed)创建,失败时就能重现同样的输入:
使用固定 seed 创建随机数生成器
重复生成小规模 input:
expected = bruteForce(copy(input))
actual = optimized(copy(input))
若结果不等价:保存 seed、轮次、input 并报告失败
两边各拿一份 copy(input),是为了防止一方把数组排序了,另一方读到的已经是改动过的输入。比较数组结果要比较内容,不能只比较引用。题目有多个合法解时,两个实现返回的解可以不同,要比较的是结果是否合法、目标值是否一致。
8.1 结果性质与测试隔离
性质测试不跟另一个实现比,而是检查结果本身必须满足的规则,可以弥补对拍的不足。常用的结果性质有:
- 排序结果按非递减顺序排列,并且每种元素的出现次数不变,也就是元素的多重集不变。只检查有序是不够的,返回一个空数组也是「有序」的。
- 反转两次后恢复原序列。链表还需检查节点是否丢失,以及是否意外成环。
- 最短路径的边都合法,起终点正确,并且长度与基准距离一致。
- 去重结果不含重复,每个元素都来自输入,并保留输入中每种不同的元素。
最短路的结果还可以和任意一条已知可行的路径比较,答案不应比它长。但这只是一个上界检查,路径本身是否合法、距离是否最优仍要单独验证。
还有两点容易忽略。同一个实例多调用几次,能暴露上次调用残留的状态。随机测试失败后,把输入缩小,保存成固定的回归用例;JUnit 5.13.4 的参数化测试可以让同一套断言跑多组边界输入。最后要记住,测试只能覆盖有限的输入,算法对所有输入都正确,仍要靠证明。
9. 修改后的复查
优化代码时,原来成立的条件可能被悄悄改掉了。每做一种修改,都要针对它改变的假设补充检查:
- 二维 DP 压成一维后,检查循环方向是否仍读取所需的旧状态。
- int 改成 long 后,检查中间乘法是否也已提升类型。
- 递归改成迭代后,检查访问顺序与空输入行为。
- 哈希集合改成数组后,检查字符或数值是否超出数组表示的范围。
- 改成并行累加后,检查是否存在共享变量写入等副作用。
补完针对性用例后,再把已有测试全部跑一遍,确认原有行为没有被破坏。
10. 现场编码流程
把前面的内容串起来,现场编码可以按这个顺序进行,推导和验证始终在同一条思路里:
- 复述输入、输出与关键约束。
- 给出直接方案和复杂度,需要时再提出优化。
- 说明不变量、终止依据和选用的数据结构。
- 实现主路径与必要边界。
- 手动运行正常例和反例。
- 重新说明时间、空间、输入修改和工程限制。
发现反例时,先指出是哪条假设失效了,再据此修正方案,而不是盲目改代码。卡住的时候,把已经确认的条件和试过但失败的方向说出来,面试官更容易给提示,你也更容易继续推导。修复以后,用那个反例再跑一遍,确认新实现确实解决了原来的问题。
11. 常见问题
11.1 现场题要处理 null 吗?
按接口约定来。可以拒绝 null 并抛出 IllegalArgumentException,也可以返回约定好的空结果。题目保证输入合法时,说明一句这个前提就够了,把精力放在算法本身。
11.2 先写暴力解会不会浪费时间?
不会,只要控制好时间。暴力解可以作为小规模的基准,但要说明它的成本为什么满足不了最终的约束,再从中找出可以优化的规律。
如果要拿它对拍,暴力解的逻辑要尽量和优化版本独立。两个版本共用同一个错误的判断,对拍时结果一致,错误也就漏掉了。
11.3 测试用例是不是越多越好?
不是,要看覆盖了多少种不同的假设和等价类。等价类是预计会走同一类处理逻辑的一组输入。同一个等价类里的正常样例再多,增加的覆盖也有限;一个能触发错误边界的反例更有用。
11.4 题目给的样例都通过了,还要做什么?
按第 5 节的四个方向补测边界用例,再手动核对循环是否推进、索引是否越界、返回值是否符合约定。最后重新说明复杂度,并确认对输入的修改符合题目要求。
12. 面试题卡片
13. 参考资料
- Java SE 21:Math.addExact
- Java SE 21:ArrayDeque
- JUnit 5.13.4:User Guide
- Java SE 21:Comparator
- Java SE 21:Random
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明