Katkat
Back

Implement follow graph with snapshots and recommendations

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates design and implementation skills for mutable graph data structures with point-in-time snapshotting and recommendation ranking, testing knowledge of data structures, versioning, graph traversal, and algorithmic time/space complexity analysis.

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.