# 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. ### What a Strong Answer Covers - A clear boundary between reported milestones and elicited product semantics. - Correct forward/reverse adjacency reasoning for a directed graph. - Snapshot storage chosen from measured read, write, and retention needs. - A recommendation algorithm that exactly matches the selected policy rather than a similarly named score. - Tests that distinguish recommendation definitions and exercise historical reads and graph mutations. ### Follow-up Questions - How would the design change if only explicitly requested snapshots must be retained? - How can you prove that a two-hop candidate generator implements the chosen directed-graph score? - When is precomputing recommendations worth its mutation and invalidation cost? - How would privacy blocks or high-degree users change the design?