Implement follow graph with snapshots and recommendations

Design and implement an in-memory “social network” component that supports following/unfollowing, point-in-time (snapshot) queries, and a simple recommendation API.

You are given users identified by integers 1..N (assume N can be large). Implement the following operations:

1. follow(u, v): user u starts following user v.
2. unfollow(u, v): user u stops following user v.
3. snap() -> sid: creates a snapshot of the current follow graph and returns a monotonically increasing snapshot id sid.
4. isFollowing(u, v, sid) -> bool: returns whether u was following v at the time snapshot sid was taken.
5. recommend(u, k) -> list[v]: recommend up to k users that u does not currently follow (and excluding u). Rank candidates by the number of users that u currently follows who also follow the candidate (i.e., “friends-of-friends” count). Break ties by smaller user id.

Clarifications/assumptions you should state and handle:

• Repeated follow(u, v) when already following should be a no-op; similarly unfollow when not following.
• Snapshots are immutable; isFollowing must reflect state at that snapshot.
• Analyze time and space complexity of your approach, especially for large numbers of operations and snapshots.

Part 1: Basic Follow/Unfollow Graph

Implement a simple directed follow graph for a small social network and answer membership queries against it.

There are n users labeled 0 to n - 1. You are given a list of operations, each a tuple (kind, a, b) where a and b are user ids. Process the operations in order, maintaining for every user the set of users they currently follow (an edge a → b means "a follows b").

Function

def solution(n, operations):
    ...

• n — the number of users.
• operations — a list of tuples; each is one of the three kinds below.
• Return — a list of booleans, one for each check operation, in the order those check operations appear.

Operations

• ('follow', a, b) — user a starts following user b (add the edge a → b).
• ('unfollow', a, b) — user a stops following user b (remove the edge a → b).
• ('check', a, b) — append True if user a is currently following user b, otherwise False.

Rules

• No self-follow. A user cannot follow themself. A follow with a == b is ignored (no edge is created). Consequently, a check with a == b always returns False.
• Idempotent follow. Repeating follow on a relation that already exists does nothing.
• No-op unfollow. unfollow on a relation that does not exist does nothing.

Output

Return the answers to all check operations, in the order they were processed. If there are no check operations, return an empty list.

Constraints

• 0 <= n <= 10^5
• 0 <= len(operations) <= 2 * 10^5
• All user ids in operations are integers in the range [0, n - 1]
• Average O(1) set operations are acceptable

Examples

Example 1

Input: (4, [('follow', 0, 1), ('check', 0, 1), ('unfollow', 0, 1), ('check', 0, 1), ('follow', 0, 0), ('check', 0, 0)])
Output: [True, False, False]

Explanation: User 0 first follows 1, then unfollows 1. Self-follow is ignored, so checking (0, 0) is False.

Example 2

Input: (3, [('follow', 1, 2), ('follow', 1, 2), ('check', 1, 2), ('unfollow', 1, 2), ('unfollow', 1, 2), ('check', 1, 2)])
Output: [True, False]

Explanation: Repeated follow and unfollow operations should not break the state.

Hints

1. A hash set for each user is enough to represent who they currently follow.
2. Make follow and unfollow idempotent so repeated operations do not cause errors.

Approach

Approach: adjacency sets. The follow graph is a directed graph where an edge a → b means "user a follows user b." We store it as follows, a list of n Python sets, one per user. follows[a] holds exactly the set of users that a currently follows. Sets give us average O(1) insert, delete, and membership test — perfect for a stream of follow/unfollow/check operations.

Processing each operation:

• ('follow', a, b) — add b to follows[a], but only if a != b (self-follow is ignored per the rules). Adding to a set is idempotent, so repeating follow on an existing edge is automatically a no-op.
• ('unfollow', a, b) — use follows[a].discard(b). discard (unlike remove) does not raise if b is absent, so repeating unfollow on a missing edge is a silent no-op, exactly as required. The a != b guard is harmless here since a self-edge can never exist.
• ('check', a, b) — append a != b and b in follows[a]. The a != b short-circuit guarantees a user is never reported as following themself, even defensively, before doing the set lookup.

Why it's correct: the set membership of follows[a] is the single source of truth for whether edge a → b exists at any moment. Each rule (no self-follow, idempotent follow, no-op unfollow) maps directly onto a set property — uniqueness, add idempotency, and discard tolerance — so no extra bookkeeping is needed. check answers are appended in operation order, matching the required output.

• Time complexity: O(n + m) average, where n is the user count and m is the number of operations. Building n empty sets is O(n); each operation does O(1) average-case set work.
• Space complexity: O(n + E), where E is the number of currently active follow edges. The list holds n sets, and the sets collectively store E edges; the output list adds O(c) for the c check operations.

Part 2: Follow Graph with Snapshots and Historical Queries

Maintain a directed follow graph that supports immutable snapshots and historical queries against those snapshots.

There are n users labeled from 0 to n - 1. You are given a list of operations to process in order. Each operation is a tuple (or list) whose first element is a string naming the operation:

Operations

• ('follow', a, b) — user a starts following user b. The relationship is directed: a following b does not mean b follows a.
• ('unfollow', a, b) — user a stops following user b.
• ('snapshot',) — save the current state of the follow graph and return its snapshot id.
• ('check', snap_id, a, b) — ask whether user a was following user b in the saved state identified by snap_id. Returns a boolean.

Rules

• Snapshot ids start at 0 and increase by 1 each time snapshot is called (the first snapshot gets id 0, the second 1, and so on).
• A snapshot captures every follow/unfollow applied before it is taken. Snapshots are immutable: any follow/unfollow performed after a snapshot leaves that older snapshot's state unchanged.
• No self-follows. A follow where a == b is ignored (no state change). Likewise, a check where a == b always returns False.
• Idempotency. Repeated follow operations on a pair that is already following, or repeated unfollow operations on a pair that is not following, have no effect. Following → unfollowing → following again leaves the pair in the following state.
• Every check is guaranteed to use a snap_id that was previously returned by a snapshot call.

Return value

Return a list containing the result of every snapshot and every check, in the order the operations appear:

• For each snapshot, append its snapshot id (an integer).
• For each check, append a boolean (True if a was following b in that snapshot, otherwise False).

follow and unfollow operations produce no output.

Function signature

def solution(n, operations):
    ...

Examples

• Operations [('follow', 0, 1), ('snapshot',), ('unfollow', 0, 1), ('snapshot',), ('check', 0, 0, 1), ('check', 1, 0, 1)] with n = 3 return [0, 1, True, False]. Snapshot 0 is taken while 0 follows 1 (→ True); snapshot 1 is taken after the unfollow (→ False).
• Operations [('follow', 0, 1), ('unfollow', 0, 1), ('follow', 0, 1), ('snapshot',), ('check', 0, 0, 1)] with n = 2 return [0, True], since the final state before the snapshot has 0 following 1.
• Operations [('follow', 0, 0), ('snapshot',), ('check', 0, 0, 0)] with n = 2 return [0, False] — the self-follow is ignored and the self check is False.

Constraints

• 0 <= n <= 10^5
• 0 <= len(operations) <= 2 * 10^5
• All user ids are in [0, n - 1].
• Each check uses a valid snapshot id that has already been created.

Hints

1. You do not need to copy the whole graph at every snapshot. Store only when a specific follow relation changes.
2. For each pair (a, b), keep a sorted history of (snapshot_id, state) and binary-search it during historical queries.

Approach

The solution treats each ordered pair (a, b) as an independent boolean ("a follows b") that changes over time, and answers historical check queries with a per-pair binary search.

State kept

• current[(a, b)] — the live follow flag, used to enforce idempotency.
• history[(a, b)] — a list of (snap_version, flag) change-points, ordered by version.
• current_snap — the id the next snapshot will return; it also tags every change with the snapshot version it belongs to.

Per operation

• follow/unfollow: self-follows (a == b) are ignored. A change is recorded only when the flag actually flips (so repeats are no-ops). The new state is appended as (current_snap, flag); if the last history entry already has the same current_snap, it is overwritten so multiple flips between two snapshots collapse to the net state at that version.
• snapshot: appends current_snap to the answers, then increments it. No copying of the graph happens — snapshots are implicit, identified purely by version number.
• check(snap_id, a, b): self-pairs return False. Otherwise it binary-searches the pair's history with bisect_right(hist, (snap_id, 1)) - 1 to find the last change-point whose version is <= snap_id. That entry's flag is the answer; if none exists, the answer is False.

Why correct: because change-points are tagged with the version active when they happened, the most recent change at version <= snap_id is exactly the pair's state as it existed when snapshot snap_id was taken, and later mutations (higher versions) never affect it — giving immutable historical reads without ever materializing a full graph copy.

• Time complexity: O(len(operations) log len(operations))
• Space complexity: O(len(operations))

Part 3: Recommend Top-K Users by Two-Hop Follow Count

Build a friend-recommendation engine on a directed follow graph, processing a stream of operations and returning a recommendation list for each query.

There are n users labeled 0 to n - 1. The follow graph is directed: "user a follows user b" does not imply b follows a.

Function

Implement solution(n, operations):

• n — the number of users.
• operations — a list of tuples, each one of three kinds, applied in order.

Return a list of lists: one recommendation list for every ('recommend', ...) operation, in the order those operations appear. follow and unfollow operations produce no output.

Operations

• ('follow', a, b) — user a starts following user b. Following someone you already follow has no effect.
• ('unfollow', a, b) — user a stops following user b. Unfollowing someone you don't follow has no effect.
• ('recommend', u, k) — produce up to k recommended users for user u (see below).

Recommendation rule

For a recommend(u, k) query, score every candidate user c by counting two-hop follow paths u → x → c:

• A candidate c earns 1 point for each user x such that:
  • u currently follows x, and
  • x currently follows c.
• Equivalently, c's score is the number of users u already follows who in turn follow c.

Apply these filters to the candidates:

• Exclude u — never recommend a user to themselves.
• Exclude users u already follows — only recommend new connections.
• Keep only positive scores — a candidate with score 0 (no qualifying two-hop path) is not recommended.

Ranking

Sort the surviving candidates and return at most k of them:

• Higher score first.
• Ties broken by smaller user id first.

Return the first k ids in this order. If fewer than k candidates qualify, return all of them.

Edge cases

• Self-follow is ignored. A ('follow', a, a) (and likewise ('unfollow', a, a)) is a no-op and contributes no edge to the graph.
• k <= 0 yields an empty recommendation list [] for that query.
• If no candidate has a positive score, the recommendation list is [].

Constraints

• 0 <= n <= 10^5
• 0 <= len(operations) <= 2 * 10^5
• All user ids are in [0, n - 1]

Examples

Example 1

Input: (5, [('follow', 0, 1), ('follow', 0, 2), ('follow', 1, 3), ('follow', 2, 3), ('follow', 2, 4), ('recommend', 0, 2)])
Output: [[3, 4]]

Explanation: User 3 gets score 2 because both followed users 1 and 2 follow 3. User 4 gets score 1.

Example 2

Input: (6, [('follow', 0, 1), ('follow', 0, 2), ('follow', 1, 4), ('follow', 2, 3), ('recommend', 0, 2)])
Output: [[3, 4]]

Explanation: Users 3 and 4 both have score 1, so the smaller id 3 comes first.

Hints

1. For a recommendation query on user u, iterate through everyone u follows, then through each of their follow sets, and count candidate frequencies.
2. After counting, sort candidates by (-score, user_id) and take the first k.

Approach

The algorithm maintains an adjacency list of sets: follows[a] holds every user that a currently follows. Using sets makes follow, unfollow, and membership tests all O(1) average, and naturally deduplicates repeated follows.

Mutations. follow/unfollow simply add/discard on follows[a], but only when a != b, which silently ignores self-follows as required.

Recommendation (the core). For ('recommend', u, k):

• If k <= 0, append [] and skip — nothing can be recommended.
• Build blocked = set(follows[u]) ∪ {u}. This enforces two rules at once: never recommend a user u already follows, and never recommend u itself.
• Compute the two-hop score. For each x in follows[u] (the users u follows), iterate over follows[x] (whom x follows). Each such candidate c not in blocked gets +1 via scores[c] = scores.get(c, 0) + 1. So a candidate's score is exactly how many of u's followees also follow c — precisely the problem's definition. Candidates with zero qualifying paths never enter scores, so only positive scores remain.
• Rank with sorted(scores.items(), key=lambda item: (-item[1], item[0])): descending score, then ascending id to break ties. Take the first k ids.

Why correct: scores are accumulated only over genuine u → x → c paths, the blocked set removes self/already-followed users, and the sort key matches the ranking rule exactly. Test 5 confirms the self-follow ('follow', 1, 1) is ignored, so user 1 contributes no two-hop edge.

• Time complexity: O(1) average per follow/unfollow. Each recommend(u, k) is O(T + C log C), where T is the total number of outgoing edges across all users that u follows (the work to accumulate scores) and C is the number of distinct positive-score candidates (the sort).
• Space complexity: O(n + E) for the adjacency-list-of-sets (n sets plus E total follow edges), plus O(C) per recommend query for the transient scores map and blocked set, where C is the number of candidate users for that query.