Design a Versioned Social Follow Graph with Friend Recommendations
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
# 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]`.
Quick Answer: This question evaluates the ability to design a versioned, in-memory graph data structure that supports point-in-time queries alongside live mutations. It tests skills in combining hash maps with sorted timestamp indexes for efficient historical lookups, plus graph traversal for generating ranked recommendations. This is a practical, implementation-level coding and algorithms question common in system design and data structures interviews.
# 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]`.
Constraints
- User ids are non-negative integers; timestamps are positive integers, strictly increasing across mutations (no two mutations share a timestamp).
- Up to about 10^5 total operations.
- get_followees / get_followers return ids in ascending order, reflecting the latest state.
- is_following considers only events with event-time <= the query timestamp, returns False when the pair has no such event, and does not advance the current time.
- recommend ranks qualifying candidates by number of distinct intermediaries descending, breaking ties by smaller id, and returns at most k ids (fewer if fewer qualify).
Examples
Input: (['SocialGraph', 'follow', 'follow', 'follow', 'follow', 'follow', 'is_following', 'unfollow', 'is_following', 'is_following', 'get_followees', 'recommend'], [[], [1, 10, 20], [2, 10, 30], [3, 20, 40], [4, 30, 40], [5, 30, 50], [10, 20, 1], [6, 10, 20], [10, 20, 6], [10, 20, 3], [10], [10, 5]])
Expected Output: [None, None, None, None, None, None, True, None, False, True, [30], [40, 50]]
Explanation: Problem's worked example: follow/unfollow, versioned is_following (True@t1, False@t6, True@t3), get_followees([30]), recommend([40,50]).
Input: (['SocialGraph', 'follow', 'follow', 'follow', 'follow', 'follow', 'follow', 'follow', 'follow', 'recommend'], [[], [1, 1, 2], [2, 1, 3], [3, 1, 4], [4, 2, 5], [5, 2, 6], [6, 3, 5], [7, 3, 7], [8, 4, 5], [1, 5]])
Expected Output: [None, None, None, None, None, None, None, None, None, [5, 6, 7]]
Explanation: recommend scoring: user 1 follows {2,3,4}; candidate 5 has three intermediaries (score 3); 6 and 7 tie at score 1, broken by smaller id -> [5,6,7].
Hints
- Keep the current state as two adjacency maps, followees[u] and followers[u] (sets), updated on every follow/unfollow. get_followees, get_followers, and recommend all read from these latest-state maps.
- For versioned is_following, store an append-only list of (timestamp, is_follow) events per ordered pair (follower, followee). Since mutation timestamps strictly increase, each list is already sorted, so binary-search (bisect_right - 1) for the rightmost event with time <= the query and return its flag.
- For recommend(user, k): for each intermediary m in followees[user], for each c in followees[m], increment score[c]; skip c == user and any c already in followees[user]. Sort candidates by (-score, id) and slice the first k.