跳到主要内容

现场编码中的反例与测试

现场编码需要同时展示问题澄清、算法推导、实现和自检。写出能通过示例的代码只是第一步，边界、反例和复杂度决定答案是否可靠。

1. 写代码前确认题目边界​

先用简短问题确认：

  • 输入可以为 null 或空吗？
  • 元素是否重复、已排序、可能为负吗？
  • 是否保证有解，可能有多个解吗？
  • 数量和值域上限是多少？
  • 可以修改输入吗？
  • 返回任意解、全部解还是稳定顺序？
  • 字符串字符集是什么？
  • 时间和额外空间限制是什么？

这些问题直接影响算法。两数之和若数组已排序，可以双指针；未排序通常用哈希；要求全部组合还要定义重复答案怎样处理。

不要把所有极端假设一次问完。先确认会改变方案或接口的条件，再在实现时说明普通边界。

2. 先陈述不变量和复杂度​

例如二分查找可以说：

我维护半开区间 [left, right)，目标如果存在，一直位于该区间。每次比较后至少排除一半，时间 O(log n)，额外空间 O(1)。

这句话确定了：

  • right 初始值应为数组长度。
  • 循环条件是 left < right。
  • 更新边界时是否加一。
  • 返回时如何判断没找到。

如果无法用一句话说明状态不变量，代码中的边界通常也还没想清楚。

3. 选择能直接表达意图的 Java 类型​

  • 栈和队列使用 ArrayDeque。
  • 频率与最近位置使用 HashMap 或在值域小时使用数组。
  • 大和、距离和乘积使用 long。
  • 比较使用 Integer.compare，不做减法。
  • 需要稳定输出时显式选择 LinkedHashMap 或排序。
  • 递归深度可能接近 n 时改用显式栈。

面试中不要为了展示熟悉框架引入不必要的 Stream、反射或并发工具。最短的代码不一定最容易验证。

4. 从等价类和边界值构造用例​

一组有效测试至少覆盖：

4.1 最小输入​

  • 空数组或空字符串。
  • 单个元素。
  • 两个元素刚好触发一次比较。

4.2 结构边界​

  • 答案在开头、结尾和中间。
  • 没有答案。
  • 所有元素都相同或都不同。
  • 已排序、逆序和交错顺序。

4.3 数值边界​

  • 0、负数。
  • Integer.MIN_VALUE、Integer.MAX_VALUE。
  • 加法、乘法或 Comparator 差值溢出。

4.4 规模边界​

  • 最大 n 是否导致 O(n²) 超时。
  • 深链是否导致递归栈溢出。
  • 输出是否本身过大。

用例应针对算法可能失效的假设，不是随机列一堆输入。

5. 用最小反例检查错误方案​

反例越小，越容易说明根因。

5.1 贪心反例​

若方案总选当前最大值，尝试构造一个较小当前收益能换取更大后续收益的三步输入。

5.2 边界反例​

二分死循环通常用长度 1 或 2 的数组暴露；滑动窗口 left 倒退可用同一字符多次出现在窗口外的短串暴露。

5.3 相等性反例​

HashMap 键问题可以用两个 equals 相等但哈希不同的对象；Comparator 问题可以用两个不同对象比较为 0。

5.4 溢出反例​

Comparator 使用减法时，取一个最大正数和一个负数即可让符号错误。

反例不是等代码失败后再补。提出方案时主动寻找最小失败输入，可以在实现前淘汰错误方向。

6. 手动执行关键路径​

完成代码后选择一个小输入，逐步记录核心变量：

步骤leftright当前状态答案
初始化00空窗口0
加入 A01A1
加入 B02AB2
加入 A13BA2

重点检查：

  • 循环是否一定推进。
  • 索引访问前是否在范围内。
  • 更新答案发生在正确时机。
  • 清理状态是否与加入操作对称。
  • 返回值是否符合空输入协议。

面试官能看到推导过程，比沉默地多跑几个样例更有价值。

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

本地准备时，可以把优化算法与小规模暴力实现对拍：

for (int round = 0; round < 10_000; round++) {
    int[] input = randomSmallArray();
    assertEquals(bruteForce(input), optimized(input));
}

暴力版本只处理小输入，但逻辑直观。随机生成能发现人没有想到的组合，再把失败输入缩小成固定回归用例。

还可以检查性质：

  • 排序后元素多重集不变且非递减。
  • 反转两次得到原序列。
  • 最短路径结果不超过任何已知可行路径。
  • 去重结果不含重复，且每个元素来自输入。

性质测试不能证明全部正确，但能扩大验证范围。

8. 修改代码后重新检查假设​

优化往往改变边界：

  • 二维 DP 压成一维后，循环方向是否仍使用旧状态。
  • int 改 long 后，中间乘法是否也已提升类型。
  • 递归改迭代后，访问顺序是否一致。
  • HashSet 改数组后，字符值域是否仍合法。
  • 并行化后，累积函数是否有关联副作用。

不要只重跑原示例。每次改动都应针对它改变的假设增加一个用例。

9. 面试中的完成顺序​

一个可执行的节奏：

  1. 复述输入、输出和关键约束。
  2. 给出直接方案和复杂度；需要时再优化。
  3. 说明核心不变量与选用的数据结构。
  4. 编写主路径，再补边界。
  5. 用最小正常例和一个反例手动执行。
  6. 重新报告时间、空间和可能的工程限制。

卡住时把已知条件和不成立的方向说出来。主动修正一个有证据的错误，比继续默写不确定模板更能展示推理能力。

10. 常见问题​

10.1 面试题没说明 null，要主动处理吗​

先确认接口约定。面试官若认为输入合法，不必为了 null 分支污染核心算法；可以口头说明生产 API 会按契约选择拒绝、返回空结果或抛参数异常。

10.2 可以先写暴力解吗​

可以，尤其在它能帮助建立正确性基线时。先说明复杂度为何不满足最终约束，再复用观察优化。不要把大部分时间用在明知不可交付的实现上。

10.3 测试用例越多越好吗​

不是。优先覆盖不同等价类、边界和算法假设。十个重复正常样例不如一个能击穿错误不变量的最小反例。

10.4 代码通过给定样例后还要做什么​

检查空与最小输入、最大数值、无解和重复值，手动验证循环推进与索引边界，再说明复杂度和对输入的修改。给定样例通常只覆盖主路径。

11. 面试题​

11.1 收到一道信息不完整的现场编码题，应该先确认什么​

出现公司：华为 OD、美团

考察重点

  • 哪些约束会改变算法或 API。
  • 怎样在沟通和编码时间之间取舍。
  • 无解、重复、顺序和输入修改边界。

相关内容：第 1 节“写代码前确认题目边界”、第 9 节“面试中的完成顺序”。

参考回答

先复述输入输出，再确认会改变方案的条件：数据规模和值域、是否排序、重复与无解是否允许、返回任意还是全部结果、能否修改输入，以及字符集或图边权等领域条件。由这些约束选择复杂度和数据结构。

普通的 null 处理、异常类型等可以按面试官给出的合法输入约定简化，并口头说明生产接口会补契约。确认完后先讲不变量和复杂度，再实现主路径并用边界反例检查。

11.2 怎样为算法主动构造反例​

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

考察重点

  • 从方案依赖的假设反向构造输入。
  • 最小反例为什么更容易定位根因。
  • 边界、重复、溢出和状态恢复的典型错误。

相关内容：第 4 节“从等价类和边界值构造用例”、第 5 节“用最小反例检查错误方案”。

参考回答

先写出方案成立依赖的条件，再尝试让其中一个条件失效。贪心就构造局部最优妨碍后续的短输入；窗口检查单调性被负数破坏；二分用长度一、二验证边界推进；哈希和排序用重复键、比较为零和整数溢出。

优先寻找最小失败输入，因为变量少、执行路径短，更容易说明错误来自哪条不变量。修复后把这个输入保留为回归用例，再补最大规模和普通路径。

参考资料
  1. JUnit 5 User Guide：Parameterized Tests
  2. Java API：Math.addExact
  3. Java API：ArrayDeque