Google 面试中，oavoassist 带我上演教科书级 Trade-off 分析

第一轮 Coding: 设计一个“区间集合类”
📜 题目精髓 (Essence of the Problem):
实现一个类，它内部维护一个区间的集合。这个类需要支持两个核心操作：

1. add(interval): 插入一个新的区间。
2. query(point): 判断一个点是否存在于任何一个已插入的区间内。

这道题的迷惑性在于，它没有一个放之四海而皆准的“最优解”。 你的设计，完全取决于 add 和 query 哪个操作更频繁。

oavoassist 的“思维注入”：
在学员开始思考具体的数据结构前，我们立刻引导他，先向面试官展示更高维度的思考框架：

“This is a very interesting design problem. The optimal solution depends heavily on the use case. I’d like to analyze two primary scenarios: one where query operations are much more frequent than add, and one where add is the dominant operation.”(这是一个非常有趣的设计问题。最优解在很大程度上取决于使用场景。我想分析两种主要情况：一种是查询操作远比添加频繁，另一种是添加是主导操作。)

这番开场白，直接将面试的格局，从“解题”提升到了“设计”。

场景一：Query-heavy (查询密集型)

• oavoassist 的引导： 如果查询是瓶颈，那么我们应该在 add 的时候做更多的“预处理” (pre-computation)。
• 学员阐述的思路：
  • 数据结构： 维护一个有序且无重叠的区间列表。
  • add 操作 (较慢): 每次插入一个新区间时，都需要与现有区间进行合并。例如，插入 [5, 8] 到 [[1, 3], [6, 9]] 中，会合并成 [[1, 3], [5, 9]]。这个操作的复杂度是 O(N)。
  • query 操作 (极快): 由于区间列表是有序的，我们可以使用二分查找 (Binary Search) 在 O(log N) 的时间内，快速定位到可能包含该点的区间，然后进行一次判断。

场景二：Add-heavy (插入密集型)

• oavoassist 的引导： 如果插入是瓶颈，那么 add 操作就应该尽可能快，我们可以把计算的压力转移到 query 上。
• 学员阐述的思路：
  • 数据结构： 直接使用一个简单的列表，不要求有序，也不进行合并。
  • add 操作 (极快): 每次插入，只需将新区间追加到列表末尾即可。这是 O(1) 的操作。
  • query 操作 (较慢): 需要线性扫描所有已存的区间，逐一判断该点是否落在其中。这是 O(N) 的操作。

结果： 这场精彩的“双场景”分析，完美地展示了学员对时空复杂度、预处理和在线/离线计算的深刻理解，彻底征服了面试官。

---