Uber 社交关注快照：Follow、Unfollow 与历史版本查询

题意与假设

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

• Follow(A,B) 和 Unfollow(A,B) 分别设置有向边 A→B 的布尔状态；重复 follow/unfollow 不改变结果。
• CreateSnapshot 返回当前版本号 v，并把写入版本推进到 v+1。已封存版本不可修改；按题目示例，IsFollowing 也可查询当前活动版本。
• 当前活动版本的查询是读取当下状态，会随本版本后续写入改变；若产品要求真正不可变的 snapId，应只允许查询已封存版本，并修改题目示例的查询时机。

解题路线

1. 为每条有向边维护按版本递增的 (version,state) 变化列表；同版本多次操作覆盖该版本最后状态，相邻版本状态不变时可不追加。
2. 创建快照不复制所有边，只推进全局版本，因此 O(1)；历史边状态查询在该边变化列表中二分找到 version≤目标的最后一次变化。
3. 若没有历史变化，该边从未被关注，返回 false。版本区间检查先于二分，避免把未来版本当作当前状态。

手动走一遍

Follow(1,2) 写版本 0；CreateSnapshot() 返回 0 并把活动版本设为 1；Unfollow(1,2) 写版本 1。查询版本 0 为 true，查询活动版本 1 为 false，正对应题目。

Python 参考实现

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

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

"""Historical directed follow state with an explicitly queryable current version."""

from bisect import bisect_right


class VersionedFollows:
    def __init__(self):
        self.version = 0
        self.history: dict[tuple[int, int], list[tuple[int, bool]]] = {}

    def _set(self, follower: int, followee: int, state: bool) -> None:
        key = (follower, followee)
        changes = self.history.setdefault(key, [])
        if changes and changes[-1][0] == self.version:
            changes[-1] = (self.version, state)
        elif not changes or changes[-1][1] != state:
            changes.append((self.version, state))

    def follow(self, follower: int, followee: int) -> None:
        self._set(follower, followee, True)

    def unfollow(self, follower: int, followee: int) -> None:
        self._set(follower, followee, False)

    def create_snapshot(self) -> int:
        sealed = self.version
        self.version += 1
        return sealed

    def is_following(self, follower: int, followee: int, version: int) -> bool:
        if version < 0 or version > self.version:
            raise ValueError("unknown version")
        changes = self.history.get((follower, followee), [])
        index = bisect_right(changes, (version, True)) - 1
        return index >= 0 and changes[index][1]

复杂度

设某条边状态变化次数为 h、所有变化总数为 H。Follow/Unfollow 摊还 O(1)，CreateSnapshot O(1)，IsFollowing O(log h)，空间 O(H+不同边数)。若采用整图复制，每次快照将变成 O(当前边数)。

易错点与追问

容易失分的边界

• 关注是单向的，A→B 为 true 不代表 B→A 为 true。
• 直接按版本保存整个社交图会放大快照成本；只存每条边的变化版本即可查询历史。
• 题目用 snapId=1 查询尚未调用 CreateSnapshot 封存的活动版本 1，不能悄悄把它解释为已封存快照。

继续深挖

• 若需要并发强一致，在创建快照与关系写入间使用统一的版本分配/事务顺序；仅靠内存整数自增不足以定义分布式提交顺序。
• 若要列出某用户某历史版本关注的全部对象，逐边二分查询可能昂贵；需按 follower 建索引或定期做检查点，再合并增量。