Versioned Friend Recommendations

A directed social graph has n users numbered from 0 to n - 1. A relationship u -> v means that user u follows user v.

Process relationship updates, immutable snapshots, and historical recommendation queries. Every snapshot includes all earlier updates, and later updates never change an earlier snapshot.

Operations

• FOLLOW u v activates u -> v. The relationship is inactive immediately before the command.
• UNFOLLOW u v deactivates u -> v. The relationship is active immediately before the command.
• SNAPSHOT creates the next snapshot. IDs start at 0. Append the ID as a decimal string.
• RECOMMEND user snapshot_id k appends up to k recommendations computed from that snapshot.

Recommendation Rule

A candidate must be different from user, must not already be followed by user, and must be reachable by at least one two-hop path user -> middle -> candidate at the requested snapshot.

The candidate's score is the number of distinct active middle users that form such a path. Rank candidates by score descending, then user ID ascending. Return the first k candidate IDs.

Serialize each recommendation list as a string containing IDs inside brackets, separated by commas and no spaces. Serialize an empty list as []. Only SNAPSHOT and RECOMMEND produce output. Return those strings in command order.

Historical Storage

For this exercise, assume each directed relationship is stored as a change history and the whole graph is not copied for each snapshot. Use binary search on that authored history and a bounded heap for recommendation selection.