Snapshot Set：不可变历史、删除和快照成本

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 值可哈希，集合去重；remove不存在值为幂等。snapshot返回从0递增版本号，read未知版本抛IndexError。
• 基线完整复制为frozenset；快照创建O(n)，没有额外O(1)要求。历史不提供可修改内部引用，示例无并发和快照回收。

解题路线

1. 当前集合正常add/discard，snapshot捕获一个独立frozenset，read按版本索引返回该不可变集合。与保存同一个set引用不同，后续删除不会穿透历史。
2. 保存历史的重点是容器隔离；如果值是可变但可哈希对象，frozenset不会递归复制其内部字段。训练值用不可变整数/字符串；对象快照须另定值语义及deep-copy/版本规则。
3. 大量快照可改持久化平衡树或HAMT，让版本共享未变节点；读某个版本依根节点。这样减少全量copy，但更新代价、节点生命周期与GC变重要。不要用可变共享树实现所谓O(1)快照。
4. 并发时snapshot需要线性化时刻，基线用同一互斥锁覆盖更新和复制；只给版本号加锁却无锁遍历集合会混入多个时点。回收只能删除无外部持有的版本或约定过期错误。

手动走一遍

add a、snapshot0、remove a、add b、snapshot1；read0={a}，read1={b}。重复add a不产生两个a，remove z不影响当前集合或已有版本。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class SnapshotSet:
    def __init__(self):self.values=set();self.snapshots=[]
    def add(self,value):self.values.add(value)
    def remove(self,value):self.values.discard(value)
    def snapshot(self):
        self.snapshots.append(frozenset(self.values));return len(self.snapshots)-1
    def read(self,index):
        if not 0<=index<len(self.snapshots):raise IndexError("snapshot")
        return self.snapshots[index]

复杂度

当前add/remove平均O(1)，snapshot O(n)时间/空间，版本索引读取O(1)、遍历O(n)。S快照最坏O(Sn)存储，返回frozenset本身不再复制。

易错点与追问

容易失分的边界

• snapshot.append(self.values)保存同一引用会污染所有版本。
• 返回历史可变set让调用方直接篡改过去。
• 浅容器复制不能保证对象内部字段被冻结。

继续深挖

• 要求O(1) snapshot、O(logn)更新时，持久化路径复制怎样工作？
• 按版本比较两个set的差异，结构共享能避免哪些扫描？