Follow Graph with Snapshots

PracticalhardPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

Every social platform is a directed follow graph that never stops changing, and the same graph has to serve three very different reads. Product wants "who should I follow" recommendations off friends-of-friends. Trust and safety wants to replay the graph exactly as it stood when an abusive account went viral - so snapshots must be immutable, and you cannot afford to deep-copy millions of edges every time one is taken. You will build a FollowGraph that grows from a plain follow/unfollow store into one that snapshots cheaply and ranks recommendations against either the live graph or a frozen one.

User ids are integers. An edge a -> b means "a follows b" and is one-way.

Level 1 - Follow / unfollow

Implement the mutable graph core.

follow(a, b) makes a follow b. Self-follows (a == b) are ignored. Following someone you already follow is a no-op.
unfollow(a, b) removes the edge. Unfollowing an edge that does not exist is a no-op.
follows(a, b) returns whether a currently follows b.
following(a) returns a's current followees sorted ascending, or [] if there are none.

Example:

g = FollowGraph()
g.follow(0, 1)
g.follows(0, 1)     # -> True
g.follows(1, 0)     # -> False  (edges are one-way)
g.follow(0, 0)      # ignored (self-follow)
g.following(0)      # -> [1]
g.unfollow(0, 1)
g.follows(0, 1)     # -> False

Level 2 - Immutable snapshots

Add point-in-time history.

snapshot() freezes the current graph and returns a monotonically increasing id, starting at 0.
follows_at(snap_id, a, b) returns whether a followed b at that snapshot.
Snapshots are immutable: a follow or unfollow after a snapshot must never change what an earlier snapshot reports, and edges added after a snapshot must not appear in it.

Example:

g = FollowGraph()
g.follow(0, 1)
s = g.snapshot()        # -> 0
g.unfollow(0, 1)
g.follows_at(s, 0, 1)   # -> True   (frozen before the unfollow)
g.follows(0, 1)         # -> False  (live state)

Level 3 - Friends-of-friends recommendations

Add recommendation ranking on the live graph.

recommend(u, k) returns up to k recommended users.
A candidate c scores one point for every intermediary x such that u follows x and x follows c.
Exclude u itself and anyone u already follows. Only candidates with a positive score qualify.
Rank by descending score, then ascending user id. Return the top k.

Example:

g = FollowGraph()
for a, b in [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4)]:
    g.follow(a, b)
# 3 is reachable via 1 and 2 (score 2); 4 via 2 only (score 1)
g.recommend(0, 2)   # -> [3, 4]

Level 4 - Recommendations over a snapshot

Combine the previous two: rank recommendations against a frozen graph.

recommend_at(snap_id, u, k) runs the exact ranking from Level 3, but against the graph captured at snap_id instead of the live one.
Mutations made after the snapshot must not change its recommendations.

Example:

g = FollowGraph()
g.follow(0, 1)
g.follow(1, 2)
s = g.snapshot()
g.follow(1, 3)             # new candidate, added after the snapshot
g.recommend_at(s, 0, 5)    # -> [2]      (snapshot only knew about 2)
g.recommend(0, 5)          # -> [2, 3]   (live state sees both)

Mastery checklist

Check	Why it matters
`snapshot()` shares structure instead of deep-copying every edge	Deep-copying on each snapshot is O(edges) time and memory per call - the whole point of the question is to avoid it
A post-snapshot mutation copies only the affected user's follow set	Copy-on-write per user is what keeps snapshots cheap without leaking later edits into them
Self-follow and duplicate-follow are dropped before any set mutation	A stray `a -> a` edge silently corrupts recommendation scores and follower counts
Recommendation excludes both `u` and everyone `u` already follows	Recommending an existing followee is the most common scoring bug
Ranking tie-break is ascending id after descending score	Without a deterministic tie-break the output order is unstable across runs
`recommend_at` traverses the snapshot graph, not just checks one edge	Snapshots must support full neighbor enumeration, not only `follows_at` lookups

Patterns used

Foundations primers this challenge draws on.

Loading editor…

Premium content

The live editor for this challenge unlocks with Premium.

0/0 passed