Versioned Social Network

A directed social network has n users numbered from 0 to n - 1. A relationship u -> v means that user u follows user v.
Relationships change over time. The network can create immutable snapshots and later answer whether a relationship existed at a particular snapshot. A snapshot must not copy the entire graph. Instead, keep a history of changes for each directed relationship.
Every snapshot includes all preceding updates. Later updates never change an earlier snapshot. If the same relationship changes more than once before the next snapshot, that snapshot records its state after the last such change.
Operations
Process the commands in order:
FOLLOW u v: add the directed relationship u -> v. The relationship is guaranteed to be inactive immediately before this command.
UNFOLLOW u v: remove the directed relationship u -> v. The relationship is guaranteed to be active immediately before this command.
SNAPSHOT: save the current network state. Snapshot IDs start at 0 and increase by 1. Append the new ID to the output.
IS_FOLLOWING u v snapshot_id: append true if u followed v when that snapshot was created; otherwise append false. A relationship that had not yet been followed is inactive.
Only SNAPSHOT and IS_FOLLOWING produce output. Return their outputs in command order as strings.
Performance Requirements
FOLLOW, UNFOLLOW, and SNAPSHOT must each run in expected O(1) time. A historical query for one relationship must run in O(log h) time, where h is the number of recorded changes for that relationship. The total auxiliary space must be O(c), where c is the number of follow and unfollow commands.
Further Interview Stages
The reports also described listing relationships at a snapshot, recommending friends, and comparing two snapshots. The exact recommendation rule and snapshot-difference output were not provided.

Function
processVersionedSocialNetwork(n: int, operations: String[]) → String[]

Examples
Example 1
n = 4
operations = ["FOLLOW 0 1", "FOLLOW 0 2", "SNAPSHOT", "UNFOLLOW 0 1", "SNAPSHOT", "IS_FOLLOWING 0 1 0", "IS_FOLLOWING 0 1 1", "IS_FOLLOWING 0 2 1"]
return = ["0", "1", "true", "false", "true"]
Snapshot 0 contains both relationships from user 0. Snapshot 1 is created after 0 unfollows 1, while the relationship 0 -> 2 remains active.
Example 2
n = 3
operations = ["FOLLOW 1 2", "UNFOLLOW 1 2", "FOLLOW 1 0", "SNAPSHOT", "IS_FOLLOWING 1 2 0", "IS_FOLLOWING 1 0 0"]
return = ["0", "false", "true"]
Both changes to 1 -> 2 occur before the first snapshot, so its final state in snapshot 0 is inactive. The relationship 1 -> 0 is active.
Example 3
n = 3
operations = ["SNAPSHOT", "FOLLOW 2 1", "SNAPSHOT", "UNFOLLOW 2 1", "FOLLOW 2 1", "SNAPSHOT", "IS_FOLLOWING 2 1 0", "IS_FOLLOWING 2 1 1", "IS_FOLLOWING 2 1 2"]
return = ["0", "1", "2", "false", "true", "true"]
The relationship is absent in snapshot 0 and present in snapshot 1. It is removed and restored before snapshot 2, so its snapshot 2 state is active.

Constraints
1 <= n <= 100000
1 <= operations.length <= 200000
0 <= u, v < n and u != v
Every FOLLOW targets an inactive relationship.
Every UNFOLLOW targets an active relationship.
Every IS_FOLLOWING references a snapshot that has already been created.
Commands contain single spaces between tokens.
At least one command produces output.

Key the map on the pair (u, v), for example u * n + v as a long. Each key stores a list of (snapshotId, state) entries. On FOLLOW or UNFOLLOW, use the current snapshot counter as the version. If the last entry already has that version, overwrite its state. Otherwise append a new entry. That overwrite is the edge case. Example 2 tests it: follow then unfollow before snapshot 0 must read false, not true. SNAPSHOT just returns the counter and increments it. For IS_FOLLOWING, binary search the list for the last entry with version <= snapshot_id. No entry means false. Otherwise return its state. Pitfalls: appending duplicate versions, which breaks the search, and an off-by-one where a change made after snapshot k leaks into k. Pair it with the counter and you get O(1) updates, O(log h) queries and O(c) space. If the logic slips under pressure, StealthCoder is the hedge on the live OA.

StealthCoder is the hedge for the one pattern you didn't drill. It runs invisibly during the screen share.