题目重点：用幂等接收集合表达正确状态，分析查询输出下界及巨大稀疏 ID 的区间压缩。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练合同ID为非负整数，重复receive幂等；没有收到时返回(-1,[])。
- missing范围为[0,max received]，不含未知未来ID。训练示例一次snapshot读一致状态。
解题路线
- 接收时set插入并更新maximum，查询扫描0..maximum并过滤未收到ID。先用最简单状态说明正确性：集合精确表示已收到，最大值是右界，补集就是所需缺失列表。
- 若最大ID突然到10^12，直接扫描会不可用，但完整列表本来可能有约10^12项。不能声称所有missing查询O(1)，输出m项至少Ω(m)；必须与面试官讨论分页或missing区间接口。
- 改为互不重叠缺失区间时，扩大maximum新增尾部区间，receive从区间中删除点并可能拆成两段。有序树查找/拆分O(log r)，输出区间O(r)，但正式接口要所有ID仍需展开。
- 并发中receive和snapshot必须用同锁、版本快照或事务语义，否则maximum新而set旧可能虚报刚收到项。持久化需写日志与恢复；重试幂等不能替代事务。
手动走一遍
训练例receive(3)查询(3,[0,1,2])；receive(1)后为(3,[0,2])；重复receive(1)不变；最后收到0和2查询(3,[])。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class PackageTracker:
"""IDs are nonnegative integers; duplicate receives are idempotent."""
def __init__(self):
self.received = set()
self.maximum = -1
def receive(self, package_id):
if not isinstance(package_id, int) or isinstance(package_id, bool) or package_id < 0:
raise ValueError("expected nonnegative integer ID")
self.received.add(package_id)
self.maximum = max(self.maximum, package_id)
def snapshot(self):
return self.maximum, [i for i in range(self.maximum+1) if i not in self.received]
复杂度
receive期望O(1)，集合O(n)；当前示例snapshot O(M+1)时间、O(m)输出空间，M最大ID、m缺失数。区间实现需有序树而非把Python list插入写成O(log r)。
易错点与追问
容易失分的边界
- 把未收到未来包裹也列为missing。
- 漏掉ID0。
- 巨大稀疏ID仍承诺常数时间返回全列表。
- 无锁并发读混合状态。
继续深挖
- 只返回连续已收最大前缀能否更省？
- 缺失区间分页如何固定快照版本？
- 收到ID后能否删除或纠错，状态怎么改？
