Reddit Software Engineer Phone Screen Questions

The phone screen was over google hangouts plus a code sharing site. The first part of the interview was general knowledge. Again, this is front end. What is cross site...

## Problem Design a build system that compiles targets in dependency order, using cached results where possible. Each target has a list of source files and dependencies on other targets. A target needs rebuilding if any source file or dependency has changed since the last build. ```python class BuildSystem: def add_target( self, name: str, sources: list[str], deps: list[str], build_fn: callable ) -> None: def build(self, target: str) -> str: # returns build artifact path def invalidate(self, source_file: str) -> None: # mark file as changed ``` ## Example ``` build.add_target("libfoo", sources=["foo.c"], deps=[], build_fn=compile_c) build.add_target("app", sources=["main.c"], deps=["libfoo"], build_fn=link) build.build("app") # compiles libfoo, then app build.build("app") # fully cached: nothing recompiles build.invalidate("foo.c") build.build("app") # recompiles libfoo AND app (transitive invalidation) ``` ## Follow-ups 1. How do you detect circular dependencies? 2. Which targets can be built in parallel? How do you schedule them? 3. How would you implement content-based caching (hash of inputs) vs. timestamp-based?

## Round 1 - System Design ## Problem Design the backend storage and retrieval system for a chat application. Requirements: - Users can send messages in 1:1 and group conversations - Retrieve messages for a conversation paginated by time (newest-first) - Support message search by keyword within a conversation - Message delivery guarantees: at-least-once; UI deduplicates by `message_id` - Scale: 100M DAU, 10B messages/day ## Key Design Decisions - **Data model**: `(conversation_id, message_id, sender_id, content, ts)` — partition by `conversation_id` - **Storage**: Cassandra or HBase (write-heavy, time-series, partition by conv) - **Pagination**: cursor-based using `(ts, message_id)` as the cursor - **Search**: async index to Elasticsearch; acceptable lag of seconds - **Fanout**: for group chats, write to each member's inbox vs. single conv store + pull ## Follow-ups 1. How do you handle message ordering across multiple senders in the same conversation? 2. What are the trade-offs between push fanout vs. pull-on-read for group messages? 3. How do you implement end-to-end encryption and what does that mean for search?

## Problem Design a hit counter that records timestamps and returns the number of hits in the past 5 minutes (or a sliding window). ## Likely LeetCode equivalent Directly matches Design Hit Counter (LC 362). ## Tags hash_table, queue, reddit, design

## Problem Find the shortest transformation sequence from one word to another, changing one letter at a time, with each step a valid dictionary word. ## Likely LeetCode equivalent Directly matches Word Ladder (LC 127). ## Tags graph, bfs, strings, reddit

## Problem Implement a billing status tracker that models the lifecycle of invoices. Each invoice moves through states: `DRAFT -> SENT -> PAID | OVERDUE | DISPUTED -> RESOLVED`. Implement: ```python class BillingSystem: def create_invoice(self, invoice_id: str, amount: float, due_date: date) -> None: def send_invoice(self, invoice_id: str) -> bool: def mark_paid(self, invoice_id: str, paid_amount: float, paid_date: date) -> bool: def dispute(self, invoice_id: str, reason: str) -> bool: def resolve(self, invoice_id: str, resolution: str) -> bool: def get_overdue(self, as_of: date) -> list[str]: def get_summary(self) -> dict: # total billed, collected, outstanding ``` Invalid transitions (e.g., paying a DRAFT invoice) must return `False`. ## Example ``` billing.create_invoice("INV-1", 500.0, due_date=date(2025,5,1)) billing.send_invoice("INV-1") billing.get_overdue(as_of=date(2025,5,10)) -> ["INV-1"] billing.mark_paid("INV-1", 500.0, date(2025,5,10)) -> True billing.get_overdue(as_of=date(2025,5,10)) -> [] ``` ## Follow-ups 1. How do you handle partial payments? 2. What audit trail does each state transition need to store? 3. How would you implement automated overdue reminders as a background job?

## Problem Given a dataset of communities and their member sets, implement a function that returns the top `k` communities most similar to a given community, ranked by **Jaccard similarity** of member sets. ```python def similar_communities( target: str, community_members: dict[str, set[str]], # community_id -> set of user_ids k: int ) -> list[tuple[str, float]]: # [(community_id, jaccard_score)], descending pass ``` ## Example ``` community_members = { "python": {"alice", "bob", "carol", "dave"}, "django": {"alice", "bob", "eve"}, "flask": {"bob", "carol", "frank"}, "java": {"dave", "george"} } similar_communities("python", community_members, k=2) # jaccard(python, django) = |{alice,bob}| / |{alice,bob,carol,dave,eve}| = 2/5 = 0.4 # jaccard(python, flask) = |{bob,carol}| / |{alice,bob,carol,dave,frank}| = 2/5 = 0.4 # jaccard(python, java) = |{dave}| / |{alice,bob,carol,dave,george}| = 1/5 = 0.2 Output: [("django", 0.4), ("flask", 0.4)] # ties broken arbitrarily ``` ## Follow-ups 1. With millions of communities, computing pairwise Jaccard is infeasible. How does MinHash/LSH help? 2. How would you update similarities incrementally as users join and leave communities? 3. Should you exclude very large communities (>10M members) from similarity? Why?

## Problem Model a tennis match using object-oriented design. A match is best-of-3 or best-of-5 sets; a set is first to 6 games with 2-game lead (tiebreak at 6-6 for non-final sets); a game follows standard tennis scoring (0, 15, 30, 40, deuce, ad). Implement: ```python class TennisMatch: def __init__(self, player1: str, player2: str, best_of: int = 3): ... def point_won_by(self, player: str) -> None: ... def current_score(self) -> str: # e.g., "Set: 1-0 | Game: 30-15" def is_over(self) -> bool: ... def winner(self) -> str | None: ... ``` ## Example ``` match = TennisMatch("Federer", "Nadal", best_of=3) # Play points... for _ in range(4): match.point_won_by("Federer") match.current_score() -> "Set: 0-0 | Game: Federer leads 1-0 games" # After 4 points: Federer wins game (0,15,30,40,game) match.is_over() -> False ``` ## Follow-ups 1. How does your class hierarchy change to support doubles matches? 2. Where does the tiebreak rule fit — in the `Set` class or the `Match` class? 3. How would you serialize and replay a match from a sequence of points?

## Problem Given `n` people at positions on a 2D grid, find the location that minimizes the **total travel distance** (Manhattan distance) for all of them to meet. The meeting point does not need to be at an existing person's location. ```python def find_meeting_point(positions: list[tuple[int, int]]) -> tuple[int, int]: pass ``` ## Example ``` Input: positions = [(0, 0), (2, 2), (4, 0)] For Manhattan distance, the optimal x is the median of x-coords, and the optimal y is the median of y-coords. Median x = 2, median y = 0 Output: (2, 0) Total distance: |0-2|+|0-0| + |2-2|+|2-0| + |4-2|+|0-0| = 2+2+2 = 6 ``` ## Follow-ups 1. Prove why the median minimizes total Manhattan distance (vs. mean, which minimizes L2). 2. If people have different weights (e.g., some need to travel multiple times), how does the solution change? 3. How do you solve the Euclidean (L2) version — is there a closed-form solution? 4. What if the meeting point must be on an existing road network (graph), not a free grid?

## Problem Design a moderation access control system for a multi-community platform. Moderators have roles scoped to specific communities: `viewer`, `moderator`, `admin`. Implement: ```python class ModerationSystem: def assign_role(self, moderator_id: str, community_id: str, role: str) -> None: def can_perform( self, moderator_id: str, community_id: str, action: str # "view_reports"|"remove_post"|"ban_user"|"appoint_mod" ) -> bool: def revoke_role(self, moderator_id: str, community_id: str) -> bool: def list_moderators(self, community_id: str) -> list[dict]: ``` Permission matrix: `viewer` can `view_reports`; `moderator` adds `remove_post`, `ban_user`; `admin` adds `appoint_mod`. ## Example ``` mod_sys.assign_role("alice", "r/python", "moderator") mod_sys.can_perform("alice", "r/python", "ban_user") -> True mod_sys.can_perform("alice", "r/python", "appoint_mod") -> False mod_sys.can_perform("alice", "r/java", "view_reports") -> False # no role in r/java ``` ## Follow-ups 1. How do you model global super-admins who can act in any community? 2. How would you audit every permission check and role change for compliance? 3. Roles change frequently — how do you cache permission checks without serving stale data?