社交网络Snapshot：关注关系、列表和二跳推荐

题意与假设

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

• 训练有向follow，已存在用户、无自关注；snapshot用不可变users/edges副本。
• 二跳推荐按“我关注的人关注谁”计共同followees，排除我及已经关注的人，平局ID升序。followers措辞若不同需换方向。

解题路线

1. 当前Network用users/edges set，follow重复幂等。create_snapshot复制为frozenset，历史查询直接该版本，不拿当前edges加时间猜历史。
2. followers检查边目标，followees检查边起点，两者不能互换。推荐从我的followee集合找其出边，候选每位共同中介计一次，重复消息不加分。
3. 全量copy baseline简单，snapshot很多可用persistent maps/边的版本区间；保留删除和用户incarnation语义。不变snapshot仍应避免暴露可改内部对象，生产权限变动可能限制读取历史关系。

手动走一遍

A→B、B→C，snapshot后删B→C，旧snapshot仍推荐C，当前版本不推荐。A已关注C，即使B→C分数高也排除，自己A也不推荐。

Python 参考实现

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

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

from collections import Counter
class Snapshot:
    def __init__(self,users,edges):self.users=frozenset(users);self.edges=frozenset(edges)
    def is_follow(self,a,b):return (a,b) in self.edges
    def followers(self,user):return sorted(a for a,b in self.edges if b==user)
    def followees(self,user):return sorted(b for a,b in self.edges if a==user)
    def recommend(self,user,k):
        if k<0:raise ValueError("nonnegative k")
        followed=set(self.followees(user));counts=Counter()
        for a,b in self.edges:
            if a in followed and b!=user and b not in followed:counts[b]+=1
        return sorted(counts,key=lambda x:(-counts[x],x))[:k]
class Network:
    def __init__(self):self.users=set();self.edges=set()
    def add_user(self,user):self.users.add(user)
    def follow(self,a,b):
        if a==b or a not in self.users or b not in self.users:raise ValueError("known distinct users")
        self.edges.add((a,b))
    def unfollow(self,a,b):self.edges.discard((a,b))
    def create_snapshot(self):return Snapshot(self.users,self.edges)

复杂度

snapshot O(U+E)时间/空间；followers/followees O(E)基线；推荐O(E+C logC)含排名，k小可heap，多个snapshot总copy O(S(U+E))。

易错点与追问

容易失分的边界

• 浅拷贝dict但内部set仍共享会污染历史。
• 按邻居的followers而非followees会推荐不同对象。

继续深挖

• 用户删除再同名重建，snapshot身份该怎么区分？
• 快照创建O(1)的persistent结构会将成本移到哪些操作？