Problem RestatementProblem
Design a to-do list service. Users create lists and tasks, then update, complete, delete and reorder them. Two versions of this appear in interviews:
- Microsoft: a clean backend with CRUD APIs (Create, Read, Update, Delete), plus authentication, rate limiting, caching and API versioning.
- Roblox: a shared list where several people edit at the same time and see changes quickly, with sensible behavior for conflicting edits and offline changes.
RequirementsRequirements
1.1 Functional
- Lists: create, rename, delete and share with others.
- Tasks: create, edit (title, due date, notes), complete or uncomplete, delete, and reorder.
- See changes from collaborators in near real time.
1.2 Non-Functional
- Simple, predictable APIs.
- Secure: users see only their own or shared lists.
- Fast (under 100 ms reads), highly available.
- Shared edits converge. Nobody's change silently disappears.
1.3 Scale Estimates
- 10M users, 100M tasks. Reads: 5K/sec, writes: 500/sec. This is modest scale, so correctness and API design matter most.
API Design (REST)
POST /v1/lists { name } → 201 { list }
GET /v1/lists?cursor=&limit=50 → 200 { items, next_cursor }
GET /v1/lists/{list_id}/tasks?status=open&cursor=
POST /v1/lists/{list_id}/tasks { title, due_at?, after_task_id? } → 201 { task }
PATCH /v1/tasks/{task_id} { title?, completed?, due_at? } (header If-Match: "v7")
POST /v1/tasks/{task_id}/move { after_task_id }
DELETE /v1/tasks/{task_id} → 204
POST /v1/lists/{list_id}/members { user_id, role: editor|viewer }Good practices to mention:
- Nouns for resources and HTTP verbs for actions. Use PATCH for partial updates.
- Status codes: 201 created, 204 no content, 400 bad input, 401 not logged in, 403 not allowed, 404 not found, 409 conflict, 412 precondition failed (stale ETag), 429 too many requests.
- Cursor pagination instead of page numbers (stable when items are added).
- Idempotency-Key header on POST, so a retried create doesn't make two tasks.
- Versioning: put the version in the URL (
/v1/), keep v1 working while v2 exists, only add fields in minor changes, and announce deprecations early.
High-Level ArchitectureArchitecture
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
C["Web / Mobile"] --> GW["API Gateway - auth, rate limit"]
GW --> API["Todo Service"]
API --> DB[("Postgres - lists, tasks")]
API --> CA[("Redis cache")]
API --> PS[("Pub/Sub - channel per list")]
PS --> WS["WebSocket servers"]
WS --> C- API Gateway: checks the auth token (OAuth/JWT) and applies rate limits per user (e.g., 100 requests/min).
- Todo Service: stateless and horizontally scalable.
- Postgres: lists, tasks and memberships. Every query filters by lists the user can access.
- Redis: caches list contents (invalidated on writes).
- Pub/Sub + WebSockets: push changes to everyone viewing a shared list.
Data ModelData model
CREATE TABLE lists (list_id UUID PRIMARY KEY, owner_id UUID, name TEXT, updated_at TIMESTAMP);
CREATE TABLE list_members (list_id UUID, user_id UUID, role TEXT, PRIMARY KEY (list_id, user_id));
CREATE TABLE tasks (
task_id UUID PRIMARY KEY, list_id UUID, title TEXT, notes TEXT,
completed BOOLEAN DEFAULT FALSE, due_at TIMESTAMP,
rank TEXT, -- fractional index for ordering
version INT DEFAULT 1, -- for optimistic concurrency (ETag)
updated_by UUID, updated_at TIMESTAMP, deleted BOOLEAN DEFAULT FALSE
);
CREATE INDEX ON tasks (list_id, rank);Deep Dive A — Two people editing the same taskDeep dive
One person renames a task on their laptop while another marks it complete on their phone. Both requests are legitimate and neither should lose.
Last write wins on the whole object
The client sends the full task object; the server stores it.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
sequenceDiagram
participant A as Laptop
participant S as Server
participant B as Phone
A->>S: GET task - title "Buy milk", done false
B->>S: GET task - title "Buy milk", done false
A->>S: PUT title "Buy oat milk", done false
B->>S: PUT title "Buy milk", done true
Note over S: title reverted - A's edit silently erasedEach client sends everything it knows, including the fields it did not touch, so the later request overwrites the earlier one's change with a stale value. Nothing errors, and the user who lost their edit finds out later, if ever.
Optimistic concurrency with ETags
A GET returns ETag: "v7"; a PATCH sends If-Match: "v7". If the task is now v8, the server returns 412 and the client refreshes and retries.
No edit is silently lost, which is the important property. But every concurrent edit is now a conflict, including the ones that are not really in conflict: A changed the title, B changed done, and one of them gets a 412 and a merge prompt for changes that could have both applied. On a phone with intermittent connectivity, that prompt appears constantly.
Send only what changed, and conflict only on the same field
Combine field-level patches with the version check:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
A["PATCH title - If-Match v7"] --> S["Server"]
B["PATCH done - If-Match v7"] --> S
S --> CMP{"Do the patches touch the same field?"}
CMP -->|"no"| MERGE["Apply both - title from A, done from B, version v9"]
CMP -->|"yes"| C412["412 on the second - client refreshes"]
MERGE --> PUSH["Both devices receive the merged state"]Disjoint edits merge automatically, which covers the overwhelming majority of real concurrent editing. The version check is still there for genuine same-field conflicts, where somebody does have to choose.
Two related decisions that fall out of the same thinking:
- Reordering uses a fractional rank, not an index, so a move writes one row. Two people moving different tasks never touch the same data and never conflict.
- Deletes are soft for a short window. An offline client that comes back needs to distinguish "this task was deleted" from "this task is missing from my sync", and undo needs the row to still exist.
Deep Dive B — Real-time sync and offlineDeep dive
- Every successful write publishes
{ list_id, task, version }to the list's channel. Clients viewing that list apply it. Clients ignore events older than the version they already have. - Reconnect: the client sends its last seen change timestamp or sequence number, and the server returns changes since then (
GET /v1/lists/{id}/changes?since=...). - Offline: the app queues edits locally (with task IDs created on the client as UUIDs) and replays them on reconnect. Conflicts are handled as above.
Caching and Rate Limiting
- Cache a list's tasks in Redis by
list_id, and delete the cache key on any write to that list. - Use HTTP caching for GETs with ETags (
If-None-Match→ 304 Not Modified) to save bandwidth. - Rate limit per user and per IP at the gateway (token bucket). Return 429 with
Retry-After.
Wrap-UpWrap-up
Design resource-based REST APIs with proper status codes, cursor pagination, idempotency keys and URL versioning, behind a gateway that handles auth and rate limits. Store tasks in Postgres with a fractional rank for ordering and a version for optimistic concurrency (ETags), and cache per list. For shared lists, publish every change to a per-list channel pushed over WebSockets, and let clients catch up with a "changes since" API after reconnecting or working offline.