Katkat
Back

Follow Graph with Cheap Snapshots and Top-K Follow Recommendations

OpenAISoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Build a one-directional follow graph that supports cheap snapshots and queries against past snapshots, then recommend the top k accounts a user should follow. It tests versioned data structures, snapshot semantics, two-hop graph traversal, heap-based top-k selection and scaling to highly connected accounts.

Implement the core of a social network's follow graph. Users are identified by integer IDs, and following is one-directional: user a following user b does not mean b follows a. The interview has two stages: a follow graph that supports snapshots, then top-k recommendations of whom to follow.

Clarifying Questions

  • Can a user follow themselves? What should follow do if the edge already exists, and unfollow if it does not?
  • Does a snapshot capture every change made before the snapshot() call that created it?
  • How should recommendation candidates be scored, and how are ties broken?
  • Should recommendations exclude people the user already follows, and the user themselves?
  • Roughly how many users and follow edges are there, and how skewed are the follower counts?
  • Are snapshots taken rarely (daily) or frequently (every few seconds)?

Part 1 — Follow graph with snapshots

Support these operations:

  • follow(a, b) and unfollow(a, b)
  • snapshot(), which returns a snapshot ID (0 for the first call, then 1, 2, and so on) that captures the graph as it is at that moment
  • is_following(a, b, snap_id) and following(a, snap_id), which answer questions about the graph as it was when snapshot snap_id was taken

Taking a snapshot must be cheap even when the graph is large.

What This Part Should Cover

  • A snapshot operation whose cost does not grow with the graph size
  • Correct answers for edges that change several times between two snapshots
  • Time and space complexity of each operation
  • A comparison with copying the graph at every snapshot

Part 2 — Top-k recommendations

Implement recommend(user, k), which returns up to k users that user might want to follow, best first. Then make it work against a past snapshot as well.

What This Part Should Cover

  • A clearly stated scoring rule and a deterministic tie-break
  • Correct exclusions: the user, and accounts already followed
  • Efficient top-k selection and its complexity
  • What happens when a followee follows a very large number of accounts

Hints

Hint 1

Store changes, not copies: Rather than copying the graph at every snapshot, consider recording each edge's changes along with when they happened, then working out an edge's state at any snapshot.

Hint 2

Look two steps away: Think about which accounts are close to the user in the graph and what evidence ranks one above another, then how to pick the best `k` without sorting every candidate.

Follow-up questions

  • How would you serve recommendations for hundreds of millions of users with low latency?
  • How would you store snapshots durably, and delete old ones?
  • How would you change the scoring to prefer accounts followed by closer or more active connections?
  • Snapshots are now taken every few seconds. What in your design changes?