# Design a Versioned Social Follow Graph with Friend Recommendations Build an in-memory service that maintains a directed *follow* graph between users and answers both point-in-time relationship queries and friend recommendations. Each user is identified by a non-negative integer id. A directed edge `a -> b` means "user `a` follows user `b`" (following is one-directional, like Twitter/X). The graph is **versioned**: every mutation is stamped with a strictly increasing integer timestamp, and you must be able to answer whether one user was following another *as of any past timestamp*. Implement a class `SocialGraph` supporting the following operations. - `follow(timestamp, follower, followee)`: Record that `follower` begins following `followee` at time `timestamp`. If that edge already exists in the current state this records a no-op follow event; the edge stays present. - `unfollow(timestamp, follower, followee)`: Record that `follower` stops following `followee` at time `timestamp`. If the edge does not currently exist this records a no-op unfollow event; the edge stays absent. - `is_following(follower, followee, timestamp) -> bool`: Considering only events whose event-time is `<= timestamp`, return `True` if the most recent `follow`/`unfollow` event for the ordered pair `(follower, followee)` was a `follow`; otherwise return `False` (including the case where the pair has no event at or before `timestamp`). This query does **not** advance time. - `get_followees(user) -> List[int]`: Return, in ascending order, the users that `user` follows in the current (latest) state. - `get_followers(user) -> List[int]`: Return, in ascending order, the users that follow `user` in the current (latest) state. - `recommend(user, k) -> List[int]`: Return up to `k` recommended users for `user` to follow ("people you may know"). A candidate `c` qualifies when all of the following hold, evaluated against the current state: - `c != user`, and - `user` does **not** currently follow `c`, and - there exists at least one intermediary `m` such that `user` currently follows `m` **and** `m` currently follows `c`. Score each candidate `c` by the number of **distinct** such intermediaries `m` (the count of `user`'s followees who follow `c`). Return the qualifying candidates ordered by score descending, breaking ties by smaller user id ascending. Return fewer than `k` ids if fewer candidates qualify. ## Semantics & Constraints - Every `follow`/`unfollow` call receives a strictly increasing `timestamp`; no two mutations share a timestamp. The state queried by `get_followees`, `get_followers`, and `recommend` is always the latest state (after applying all mutations performed so far). - `is_following` may be called with any positive `timestamp`, including values between or before mutation timestamps; it must reflect the relationship state as of that instant without changing the current state. - User ids are non-negative integers; timestamps are positive integers. - Up to about `10^5` total operations. Aim for `follow`/`unfollow`/`get_*` to be efficient; an `is_following` historical query may be `O(log E)` in the number of events for that pair. ## Example ```text g = SocialGraph() g.follow(1, 10, 20) # at t=1, 10 follows 20 g.follow(2, 10, 30) # at t=2, 10 follows 30 g.follow(3, 20, 40) # 20 follows 40 g.follow(4, 30, 40) # 30 follows 40 g.follow(5, 30, 50) # 30 follows 50 g.is_following(10, 20, 1) # -> True g.unfollow(6, 10, 20) # at t=6, 10 unfollows 20 g.is_following(10, 20, 6) # -> False (latest event <= 6 is the unfollow) g.is_following(10, 20, 3) # -> True (as of t=3 the latest event was the follow at t=1) g.get_followees(10) # -> [30] (20 was unfollowed) g.recommend(10, 5) # 10 follows {30}; 30 follows {40, 50}; neither is followed by 10 # -> [40, 50] ``` In the final `recommend` call, user `10` currently follows only `30`. The single intermediary `30` follows `40` and `50`, so both qualify with score `1`; `20` is not an intermediary because `10` no longer follows it. Ordered by score then id, the result is `[40, 50]`.