Databricks Snapshot Set Iterator：O(1) 创建与插入序快照

题目重点：用版本化 append-only 节点给迭代器固定可见范围，讨论移除再加入、多个迭代器及 O(N+M) 空间的 N 定义。

题意与假设

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

N 解释为成功 add 事件总数（移除后重加算新的插入事件），M 是仍被引用的迭代器数。若 N 被理解为历史上不同整数的数量，而同一值可无限次移除重加，简单 append-only 方案不满足空间要求；需澄清 N 与回收策略。
单线程语义；迭代器创建时捕获当前集合的值及插入顺序，后续 add/remove 不影响它。next 耗尽抛 StopIteration 是训练语言约定，题目未写异常协议。

解题路线

每次成功 add 建一个尾部节点，记 born 版本；current map 保存当前值对应节点。remove 将该节点的 dead 版本设为当前递增版本，并从 map 删除。重加同值创建新节点，新的插入顺序位于尾部。
getIterator 只保存首节点、当时尾节点和当前版本，O(1) 不复制。hasNext 从游标向后扫，在 born≤snapshotVersion<dead 的节点上停下；达到捕获尾节点后就结束，不读取后来追加的节点。
add/remove/contains 的 hash map 更新期望 O(1)。一个迭代器可能扫描大量已删除节点，因此总遍历最坏 O(N)，单次 next 不能保证 O(1)；题面只要求创建 O(1)，必须明确这一取舍。
每次成功 add 留一个历史节点，所以空间 O(A+M)，A 为成功插入次数。若要求 O(U+M)、U 为不同值数，需要无活跃快照节点的垃圾回收/epoch 管理；长寿命迭代器可能阻止回收，须重新界定目标。并发版本发布还需锁或原子快照。

手动走一遍

add(7), add(9), 建快照 I，remove(7), add(7)。当前集合插入序是 [9,7]；I 仍迭代 [7,9]。版本化节点中旧 7 的 dead 晚于 I 的版本，新 7 的 born 晚于 I 的版本，因此 I 只看旧 7。

Python 参考实现

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

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

"""Snapshot set in insertion-event order without copying at iterator creation.
N is the number of successful add events (including re-adds after removal).
Each event node is append-only with birth/death versions; iterators capture a
version and tail pointer. Iteration may scan dead historical nodes.
"""
from dataclasses import dataclass

@dataclass
class _Node:
    value: int
    born: int
    dead: int | None = None
    next: '_Node | None' = None

class SnapshotIterator:
    def __init__(self, first: _Node | None, tail: _Node | None, version: int):
        self.cursor = first
        self.tail = tail
        self.version = version
        self.ready: _Node | None = None

    def hasNext(self) -> bool:
        if self.ready is not None:
            return True
        while self.cursor is not None:
            node = self.cursor
            if node.born <= self.version and (node.dead is None or self.version < node.dead):
                self.ready = node
                return True
            if node is self.tail:
                self.cursor = None
                break
            self.cursor = node.next
        return False

    def next(self) -> int:
        if not self.hasNext():
            raise StopIteration
        node = self.ready
        assert node is not None
        self.ready = None
        self.cursor = None if node is self.tail else node.next
        return node.value

class SnapshotSet:
    def __init__(self):
        self.first: _Node | None = None
        self.last: _Node | None = None
        self.current: dict[int, _Node] = {}
        self.version = 0

    def add(self, value: int) -> bool:
        if value in self.current:
            return False
        self.version += 1
        node = _Node(value, self.version)
        if self.last is None:
            self.first = node
        else:
            self.last.next = node
        self.last = node
        self.current[value] = node
        return True

    def remove(self, value: int) -> bool:
        node = self.current.pop(value, None)
        if node is None:
            return False
        self.version += 1
        node.dead = self.version
        return True

    def contains(self, value: int) -> bool:
        return value in self.current

    def getIterator(self) -> SnapshotIterator:
        return SnapshotIterator(self.first, self.last, self.version)

复杂度

add/remove/contains 期望 O(1)，getIterator O(1)，完整迭代最坏 O(A) 且单次 hasNext 可能 O(A)；持久节点 O(A)、M 个迭代器 O(M)，合计 O(A+M)。这里 A 是成功 add 事件数，不是不同整数数。

易错点与追问

容易失分的边界

getIterator 直接 copy 当前集合，违反 O(1) 创建。
只保留当前 map，remove 后旧迭代器内容消失。
重加同一值却沿用旧节点，插入顺序错误。
迭代器走过捕获的 tail 看到未来新值。
声称 O(unique values+M) 但永不回收历史节点。

继续深挖

如果 next 也要求摊还 O(1)，代价是什么？
若 N 是不同值数量且反复重加，如何回收无用版本？
并发 add/remove 与 getIterator 的线性化点在哪？
如何支持快照中的 remove 操作？