跳到主要内容
约 10 分钟3 张卡

算法正确性

算法正确性要求程序能够终止，并且结果满足输入输出约定。现场编码时，需要把问题澄清、推导、实现和自检连起来。本文先说明怎样确认约束和不变量，再讲解边界用例、最小反例与可复现的测试。

1. 面试核心​

先记住这几条，再读正文
  • 输入输出契约。 算法的输入输出契约规定哪些输入合法、返回结果表示什么，以及实现是否可以修改输入。卡 · 输入输出契约
  • 循环不变量。 循环不变量在初始化后成立、每轮更新后仍成立，并在循环退出时帮助推出正确答案。
  • 最小反例。 最小反例保留触发错误的关键输入，便于定位算法依赖的哪条条件失效。卡 · 最小反例
  • 对拍验证。 对拍时，被测算法和基准算法应分别使用独立的输入副本，并保留随机种子和失败用例。卡 · 随机测试与性质测试

2. 输入输出契约​

必会卡 · 信息不完整的现场题应先确认哪些条件？

输入输出契约就是调用方与实现方共同遵守的约定。现场题的信息不完整时，优先确认会改变算法或返回结果的条件。

可以围绕以下问题澄清：

  • 输入数量和值域上限是多少？时间和额外空间限制是多少？
  • 元素是否已排序，是否包含负数或重复值？
  • 是否保证有解？无解时返回什么？
  • 多解时返回任意解还是全部解？重复答案如何处理？
  • 是否要求稳定的输出顺序？
  • 能否修改输入，例如排序或原地压缩？
  • 字符串按什么字符集与单位处理？图的边是否有方向和权重？

比如，两数之和在已排序数组中可以用双指针，未排序时可以用哈希表。若要求返回全部组合，还要约定重复答案怎样去除。这些条件直接决定实现方式。

null、空输入和非法输入按接口约定处理。先确认影响方案的关键条件，再说明其余假设，便于把时间留给推导与编码。

3. 不变量与复杂度​

不变量描述循环在约定位置始终成立的事实。写代码前把它说清楚，才能判断边界怎样初始化、每轮怎样更新，以及退出时返回什么。

循环证明需要解释以下三个部分：

  1. 初始化：第一次进入循环前，不变量为什么成立？
  2. 保持：一轮更新后，它为什么继续成立？
  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 结构边界​

结构测试用于检查算法是否过度依赖某一种排列。应覆盖以下情况：

  • 答案位于开头、结尾或中间。
  • 输入没有合法答案。
  • 元素全部相等，或全部不同。
  • 元素按升序、逆序或交错顺序排列。

例如，有序去重依赖相同值相邻，交错重复的输入就能检验这一前提是否已明确。

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 相等性反例​

相等性测试要区分对象相等与比较结果相等。哈希键需要满足：equals 相等的对象具有相同哈希值。用两个违反这一约定的自定义键，可以暴露哈希查找依赖的前提。

Comparator 对不同对象返回 0 本身合法。若 TreeSet 用该比较器，比较为 0 的项会被视为同一元素。需核对业务去重语义是否与比较规则一致。

6.4 溢出反例​

比较器用减法时，可以取最大 int 与 −1。两者相减超出 int 上限，结果变为负数，原本较大的值就会被排到前面。改用 Integer.compare 后保留该输入作回归测试，确认相同错误不会再次出现。

7. 手动执行​

手动执行用于核对代码是否实现了推导。选一个小输入，逐步记录核心变量，尤其关注边界与答案的更新时机。下面用 ABA 检查最长无重复窗口：

步骤leftright（不含）无重复窗口最长长度
初始00空0
加入 A01A1
加入 B02AB2
加入 A13BA2

处理第二个 A 后，窗口从 AB 变成 BA，最长长度仍为 2。执行过程中，逐项核对以下问题：

  • 每轮是否推进了指针，能够最终结束？
  • 访问元素之前，索引是否处于合法范围？
  • 加入与移除元素时，计数是否成对更新？
  • 更新答案时，窗口是否满足题目约束？
  • 结束后的返回值是否符合无解与空输入的约定？

现场可以边记录边解释更新原因，让面试官看到代码与不变量怎样对应。

8. 随机测试与性质测试​

必会卡 · 对拍一致为何仍会漏错，怎样提高验证质量？

对拍是把同一输入交给两个实现，再比较结果。准备面试时，可以写一个直观的小规模暴力解，作为优化算法的独立基准。随机输入能覆盖手工用例容易遗漏的组合。

下面是测试框架伪代码，双方接收独立数组。固定 seed，也就是随机数种子，便于重现生成过程：

使用固定 seed 创建随机数生成器
重复生成小规模 input：
    expected = bruteForce(copy(input))
    actual = optimized(copy(input))
    若结果不等价：保存 seed、轮次、input 并报告失败

独立副本能避免一方排序后，另一方读到已被改动的输入。数组结果应比较内容，不能只比较引用。存在多个合法解时，应比较是否合法、目标值是否一致，而无需要求两个实现返回同一个解。

8.1 结果性质与测试隔离​

性质测试检查结果必须满足的规则，可以补充对拍。常用的结果性质包括：

  • 排序结果按非递减顺序排列，元素及每种元素的出现次数保持不变。后一个条件也称为元素多重集不变。
  • 反转两次后恢复原序列。链表还需检查节点是否丢失，以及是否意外成环。
  • 最短路径的边都合法，起终点正确，并且长度与基准距离一致。
  • 去重结果不含重复，每个元素都来自输入，并保留输入中每种不同的元素。

最短路还可以与任意已知可行路径比较，答案应不长于它。但这个上界只是一项检查，仍需核验路径本身和最优距离。

多次调用同一实例，可以暴露上次调用留下的状态。随机测试失败后，应缩小输入并保存固定回归用例。JUnit 5.13.1 的参数化测试可以让同一套断言运行多组边界输入。测试覆盖的是有限输入，一般性的正确结论仍需依靠证明。

9. 修改后的复查​

优化会改变原先的实现条件。修改后，应围绕变化补充针对性检查：

  • 二维 DP 压成一维后，检查循环方向是否仍读取所需的旧状态。
  • int 改成 long 后，检查中间乘法是否也已提升类型。
  • 递归改成迭代后，检查访问顺序与空输入行为。
  • 哈希集合改成数组后，检查字符或数值是否超出数组表示的范围。
  • 改成并行累加后，检查是否存在共享变量写入等副作用。

每次围绕改变的假设补充用例，再运行已有测试，确认原有行为仍然成立。

10. 现场编码流程​

现场编码可以按以下顺序完成，把推导与验证留在同一条思路中：

  1. 复述输入、输出与关键约束。
  2. 给出直接方案和复杂度，需要时再提出优化。
  3. 说明不变量、终止依据和选用的数据结构。
  4. 实现主路径与必要边界。
  5. 手动运行正常例和反例。
  6. 重新说明时间、空间、输入修改和工程限制。

发现反例时，应指出失效的假设，再据此修正方案。卡住时，可以说明已确认的条件和失败的方向，便于继续推导。修复后保留反例，确认新实现覆盖了原问题。

11. 常见问题​

下面说明现场编码中怎样分配澄清、实现与测试的时间。

11.1 空值契约​

null 的处理由接口约定决定，可以拒绝空值、抛出参数异常或返回约定的空结果。题目保证输入合法时，说明这一前提即可，把实现重点放在算法本身。

11.2 暴力基线​

11.3 用例覆盖​

11.4 样例之后的验证​

12 · 面试题卡片​

先想答案，再翻面先在心里答一遍，再点开卡片对照参考回答。卡片之间可以左右切换，看完会回到这里。
逐张翻看 3 张 →
输入输出契约必会
信息不完整的现场题应先确认哪些条件？
华为 OD美团
考察 1 点 · 相关 §2
最小反例必会
怎样主动构造算法反例？
字节跳动华为 OD
考察 1 点 · 相关 §6
随机测试与性质测试必会
对拍一致为何仍会漏错，怎样提高验证质量？
本站自测
考察 1 点 · 相关 §8

12.1 信息不完整的现场题应先确认哪些条件？​

出现公司：华为 OD、美团

考察重点：识别会改变算法或返回结果的条件，并说明怎样在澄清和编码之间分配时间。

相关内容：输入输出契约。

参考回答

应优先确认会改变算法选择和返回结果的条件。

复述输入输出后，重点澄清以下内容：

  • 数据规模和值域，以及是否排序、是否含重复或负数。
  • 是否保证有解，多解时返回任意结果还是全部结果。
  • 输出是否要求稳定顺序，以及能否修改输入。
  • 字符单位、图边权等与题目直接相关的条件。

这些约束决定复杂度和数据结构。null 等常规边界按接口约定说明即可。确认之后，讲清不变量与复杂度，再实现主路径并用边界反例检查。

12.2 怎样主动构造算法反例？​

出现公司：字节跳动、华为 OD

考察重点：从算法依赖的假设构造失败输入，解释怎样缩小反例，并将它保留为回归用例。

相关内容：最小反例。

参考回答

从算法成立所依赖的条件出发，构造让其中一个条件失效的小输入，就能主动寻找反例。

可以按不同算法选择检查方向：

  • 贪心用较小当前收益换取更大后续收益，检验局部选择是否安全。
  • 窗口用负数检验和的单调性，用 abba 检验 left 是否倒退。
  • 二分用长度 1、2 的数组检查区间是否推进。
  • 哈希和排序用重复键、比较为零与整数极值检查相等性和溢出。
  • DP 检查读取的是上一轮还是本轮结果，回溯检查返回后是否恢复状态。

找到失败输入后，删去无关元素并保持错误可复现。这样能缩短执行路径，更容易定位根因。修复后把最小输入保留为回归用例，再补普通路径和最大规模测试。

12.3 对拍一致为何仍会漏错，怎样提高验证质量？​

出现公司：暂无已核验的公开来源（本站自测）

考察重点：说明共用错误逻辑和输入修改为何会干扰对拍，并判断多解结果应怎样比较。

相关内容：随机测试与性质测试。

参考回答

两个版本若共用错误逻辑，或互相影响输入，即使结果一致也会漏错。

基准应独立实现，并让两方分别接收输入副本，避免一方排序后改变另一方的输入。数组按内容比较，多解题则比较合法性和目标值。还要核验排序有序性、元素是否保留等结果性质。失败时保存种子、轮次和输入，再缩小为固定回归用例。

13. 参考资料​

本页
有对应面试题卡片