Clarify and Design Social-Graph Milestones

An interview exercise progresses through a social graph with snapshots, a milestone for retrieving followers and followees, and a final recommendation milestone. The exact first-milestone API, snapshot semantics, recommendation score, exclusions, and tie rules are not provided. Treat those as requirements to clarify, then design a coherent implementation for the contract you establish.

Do not present one recommendation formula as if it were reported. Instead, compare defensible policies and show that each uses directed edges correctly.

Constraints & Assumptions

• A conventional follow edge can be modeled as directed from follower to followee, but mutation and validation behavior still need confirmation.
• getFollowers and getFollowees must be defined relative to the same graph state or snapshot.
• A snapshot might mean an immutable version, an explicit captured copy, or simply the graph input for one milestone; clarify which meaning is intended.
• Expected graph size, mutation volume, snapshot retention, recommendation latency, and output size are unknown.

Clarifying Questions to Ask

• Which operations and return values belong to the first milestone?
• When is a snapshot created, how is it identified, and must old snapshots remain queryable?
• Are duplicate follows, self-follows, missing users, and unfollowing a missing edge errors or no-ops?
• Should recommendation mean followees-of-followees, users with common followees, users with common followers, or another policy?
• Which candidates are excluded, how are scores and ties ordered, and is a result limit required?

Part 1: Graph Operations

After confirming the mutation contract, choose structures for the current directed graph and explain how follower and followee reads remain consistent.

What This Part Should Cover

• Forward adjacency for followees and reverse adjacency for followers.
• Atomic maintenance of both indexes and defensive read results.
• Complexity and behavior for duplicates, deletion, self-edges, and unknown users under the agreed contract.

Part 2: Snapshot Semantics

Define what the milestone's snapshot means and compare a simple implementation with an approach suitable for more versions or larger graphs.

What This Part Should Cover

• Full-copy, copy-on-write or persistent structures, and operation-log/checkpoint alternatives.
• Stable historical reads if immutable versions are required.
• Mutation, read, memory, retention, and garbage-collection trade-offs.

Part 3: Recommendation Policies

Compare at least two plausible recommendation definitions, select one only after clarification, and give its candidate generation, scoring, exclusions, tie behavior, and complexity.

What This Part Should Cover

• Correct directed traversal for the selected policy.
• The distinction between followees-of-followees and common-followee scoring.
• Snapshot consistency, deterministic output if required, and cache invalidation trade-offs.