Implement follow graph with snapshots and recommendations

Q: Implement follow graph with snapshots and recommendations

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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:

follow(u, v) : user u starts following user v .
unfollow(u, v) : user u stops following user v .
snap() -> sid : creates a snapshot of the current follow graph and returns a monotonically increasing snapshot id sid .
isFollowing(u, v, sid) -> bool : returns whether u was following v at the time snapshot sid was taken.
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.

Implement follow graph with snapshots and recommendations

Quick Overview

Comments (0)