Skip to content

$ cat resources/system-design.md

# system design

Low-level design, multithreading and system design, grouped into pattern families. Read a family's approach first, then practise its problems. CORE marks the 30 must-do problems.

94 problems · 20 pattern families · 30 core

## low-level design machine coding · OOD

L1 Game Engines 3

how to approach · start with Snake & Ladder → Tic-Tac-Toe → Chess

Model (board, pieces, players) is separate from the rules and from the game loop. The engine never knows about the UI.

steps

  1. List entities: Game, Board, Cell/Piece, Player, Dice/Move.
  2. Put every rule behind an interface (MoveValidator, WinChecker).
  3. Model game states: NOT_STARTED → IN_PROGRESS → WON / DRAW.
  4. Keep win/move checks cheap (row/col counters, lookup maps).
  5. Keep the engine UI-free so it is unit-testable.
patterns
Strategy (rules, dice), State (game status), Factory (pieces/boards), Command/Memento (undo), Observer (UI events)
follow-ups & traps
Undo/redo; new board size or rules; AI player; multiplayer / concurrent moves; save & load game.
start with
Snake & Ladder → Tic-Tac-Toe → Chess
  • Snake & Ladder (opens in a new tab) easy · core · W1

    Model an N-player board game with snakes, ladders and dice; rules and board size should be configurable.

    key ideas: Configurable board, dice strategy, turn mgmt, win detection

    Amazon · Adobe · Microsoft · Flipkart · Swiggy · Zynga

  • Tic-Tac-Toe (N×N) (opens in a new tab) easy · skim

    Two players on an N×N board; detect a win in O(1) per move and keep the engine independent of the UI.

    key ideas: Game state, win check in O(1), extensible players

    Atlassian

  • Chess Game Engine (opens in a new tab) hard · core · W2

    Pieces with their own move rules, move validation, check and checkmate; adding a new piece type should not touch existing code.

    key ideas: Polymorphic pieces, move validation, check/checkmate, extensible rules

    Asana · Wayfair · Atlassian

L2 Booking & Reservation 3

how to approach · start with Parking Lot → Movie Ticket Booking → Meeting Room

A resource (spot, seat, room) is claimed for a time window. The hard part is allocation and never double-booking.

steps

  1. Identify Resource, Slot/Time, Reservation, User.
  2. Reservation lifecycle: AVAILABLE → HELD → CONFIRMED → EXPIRED/CANCELLED.
  3. Allocation as a Strategy (nearest, first-fit, cheapest).
  4. Make check-and-claim atomic (per-resource lock or CAS).
  5. Add hold-expiry and a pricing Strategy.
patterns
Strategy (allocation, pricing), State (reservation), Factory (vehicle/seat types), Observer (notify on release)
follow-ups & traps
Concurrent users; payment timeout; overlapping intervals (sort + sweep / interval tree); multi-floor / multi-city.
start with
Parking Lot → Movie Ticket Booking → Meeting Room
  • Parking Lot (opens in a new tab) easy · core · W1

    Multi-floor lot with spot types (bike, car, truck), entry/exit tickets and pricing; follow-up: many gates at once.

    key ideas: Strategy (pricing / spot allocation), enums, ticketing; follow-up: concurrent entry/exit

    Uber · Swiggy · Flipkart · Amazon · Google · Microsoft · Adobe

  • Movie Ticket Booking (BookMyShow) (opens in a new tab) medium · core · W2

    Cities, theatres, shows and seat maps; hold seats while the user pays and never sell the same seat twice.

    key ideas: Seat locking, double-booking prevention, payment timeout

  • Meeting Room Booking (calendar conflicts) (opens in a new tab) medium · skim

    Book rooms for time slots, find free rooms, and detect overlapping meetings, including recurring ones.

    key ideas: Interval overlap, room allocation strategy, calendar integration

    Flipkart

L3 Money & Ledger 4

how to approach · start with Splitwise → Digital Wallet → Payment Gateway

Money movement must be atomic, auditable and idempotent. Think append-only entries, not "update the balance".

steps

  1. Model Account + immutable Transaction/Entry (integers or BigDecimal, never float).
  2. A transfer = debit + credit as one atomic unit; lock accounts in id order to avoid deadlock.
  3. Add an idempotency key per request.
  4. Payment state machine: INIT → PENDING → SUCCESS/FAILED → REFUNDED.
  5. Retries with backoff + reconciliation job.
patterns
State (payment), Strategy (split type, bank routing), Command (transaction), Observer (webhooks)
follow-ups & traps
Duplicate requests; partial failures; multiple banks / virtual banks; simplify debts (Splitwise); audit trail.
start with
Splitwise → Digital Wallet → Payment Gateway
  • Splitwise (expense sharing) (opens in a new tab) medium · core · W2

    Record shared expenses split equally, exactly or by percentage, show who owes whom, and simplify debts.

    key ideas: Balance graph, split strategies (equal/exact/%), simplify debts

    Swiggy · Flipkart · Upstox

  • Digital Wallet System (opens in a new tab) medium · skim

    Users top up, pay and transfer between wallets with a transaction history; transfers must be atomic.

    key ideas: Accounts, transactions, atomic transfer, idempotency

    Flipkart

  • In-Memory Banking System (opens in a new tab) medium · skim

    Accounts, deposits, transfers and scheduled payments, extended level by level (rankings, merges, history).

    key ideas: Accounts, transfers, scheduled payments, ranking, level-by-level extension

    Anthropic

  • Payment Gateway / Merchant Payout Controller (opens in a new tab) hard · skim

    Route payments to banks or providers, track each payment through its states, retry failures and pay merchants out.

    key ideas: Multi-bank routing (virtual banks), retries, idempotency, state machine

    Meesho · Razorpay · Stripe · PayPal

L4 In-Memory Stores & Data-Structure Design 5

how to approach · start with LRU Cache → In-Memory KV DB → File System

Pick the right data structure first, then wrap it in a clean, extensible API.

steps

  1. Write the API (get/put/delete…) and complexity targets first.
  2. Choose structures (HashMap + DLL, Trie, heap, sorted map).
  3. Make policies pluggable (eviction, TTL) behind interfaces.
  4. Define edge behaviour (capacity, expiry, missing key).
  5. Add thread-safety last, thinking about lock granularity.
patterns
Strategy (eviction), Composite (file system), Decorator (TTL/stats), Iterator
follow-ups & traps
O(1) guarantees; TTL cleanup (lazy vs background); persistence / crash recovery; concurrency; versioned reads.
start with
LRU Cache → In-Memory KV DB → File System
  • LRU Cache (pluggable eviction + TTL) (opens in a new tab) medium · core · W1

    get/put in O(1) with least-recently-used eviction; then make eviction pluggable (LFU, FIFO) and add expiry.

    LC 146 key ideas: HashMap + doubly linked list; Strategy for LRU/LFU/FIFO; crash-resilient variant

    Google · Amazon · Microsoft · Facebook · Adobe · Netflix · Atlassian · Anthropic

  • In-Memory File System (mkdir / ls / …) (opens in a new tab) medium · skim

    Directories and files in memory with mkdir, ls, read and write on paths; extensible to new commands.

    key ideas: Composite pattern, Trie of path segments, extensible commands

    Uber

  • In-Memory Key-Value DB (TTL, tombstones, versioning) (opens in a new tab) medium · core · W2

    set/get/delete with expiry, then versioned reads ("value at time t") and prefix scans.

    key ideas: Versioned maps, TTL eviction, prefix scan, historical reads

    Anthropic · Atlassian

  • Spreadsheet Engine (aggregation APIs, dependent cells) (opens in a new tab) hard · skim

    Cells hold values or formulas like =SUM(A1:A3); when a cell changes, dependants update and cycles are caught.

    key ideas: Dependency graph, cycle detection, recomputation, formula parsing

    Google · Stripe

  • Multi-Level Cache (L1/L2, write-through/back) hard · skim · ★ extra

    A small fast cache in front of a larger one; define reads, writes, write policies and eviction across levels.

    key ideas: Layered caches, eviction/consistency policies, metrics

L5 Pluggable Policy Engines 6

how to approach · start with Rate Limiter → Logger → Notification Service

Behaviour that changes (algorithm, channel, rule) lives behind an interface so new variants never touch existing code.

steps

  1. Identify what varies (algorithm, channel, rule).
  2. Define the interface + a Factory / registry.
  3. Build 2 concrete implementations to prove the design.
  4. Add config / dynamic reload.
  5. Show how a 3rd variant is added without editing old code.
patterns
Strategy, Chain of Responsibility, Factory, Observer, Command (+ Memento for undo)
follow-ups & traps
Add a new algorithm; dynamic config; thread safety; memory growth from per-client state; retries / backoff.
start with
Rate Limiter → Logger → Notification Service
  • Hit Counter / Logger Rate Limit (opens in a new tab) easy · skim

    Count hits in the last 5 minutes, or print a message at most once every 10 seconds.

    key ideas: Queue + sliding window, rate-limiter adjacent

    Atlassian

  • Logging Framework (opens in a new tab) easy · skim

    Log levels, several destinations (console, file) and formats; a message flows through a chain of handlers.

    key ideas: Chain of Responsibility (log levels), Singleton, async appenders

    Amazon · Microsoft · Apple · Google · Splunk

  • Rate Limiter (pluggable algorithms) (opens in a new tab) medium · core · W2

    Allow or reject requests per user with token bucket, fixed or sliding window, chosen by configuration.

    key ideas: Strategy (token bucket / sliding window), factory, config reload

    Uber · Atlassian

  • Rating System (modular & extensible) (opens in a new tab) medium · skim

    Users rate items; compute averages and rankings, and add new rating rules or aggregations without rewrites.

    key ideas: Aggregation strategies, scale-up requirement added mid-round

    Atlassian

  • Notification Service (channels, retries, templates) medium · skim · ★ extra

    Send email, SMS or push from templates, with user preferences, retries and adding a channel without code changes.

    key ideas: Observer + Strategy per channel, retry/backoff, priority queue

  • Text Editor with Undo / Redo medium · skim · ★ extra

    Insert, delete and format text with unlimited undo and redo (Command / Memento).

    key ideas: Command + Memento patterns, cursor, selection

L6 Scheduling, Matching & State Machines 5

how to approach · start with Vending Machine → Elevator → Cab Booking → Stock Exchange

Entities move through states and a dispatcher decides who gets which resource.

steps

  1. Draw the state diagram first (states + events).
  2. Model each state as a class or a transition table (State pattern).
  3. Separate the Dispatcher / Scheduler from the entities.
  4. Make the matching policy pluggable (nearest, SCAN/LOOK, price-time priority).
  5. Think about concurrent requests hitting the dispatcher.
patterns
State, Strategy (dispatch), Observer, PriorityQueue / heap
follow-ups & traps
Multiple elevators / drivers; cancellations; fairness / starvation; order-book matching; runtime-configurable workflows.
start with
Vending Machine → Elevator → Cab Booking → Stock Exchange
  • Vending Machine (opens in a new tab) easy · core · W1

    Select a product, insert money, get it and the change; the machine moves through clear states (idle, has money, dispensing).

    key ideas: State pattern, inventory, payment handling

    Google · Amazon · Microsoft · Apple · Oracle

  • Coffee Machine (opens in a new tab) easy · skim

    Beverages from ingredient recipes, low-stock alerts, and several outlets making drinks at the same time.

    key ideas: Recipe/ingredient model, concurrent beverage preparation

    Flipkart

  • Elevator System (single → multi-lift) (opens in a new tab) medium · core · W2

    Handle floor requests for one lift, then dispatch requests across many lifts efficiently.

    key ideas: State machine, scheduling (SCAN/LOOK), dispatcher strategy

    Amazon · Microsoft · Uber · Google · Adobe · Lyft

  • Ride-Sharing / Cab Booking App (opens in a new tab) medium · skim

    Riders request trips, nearby drivers are matched, and each trip moves from requested to completed with a fare.

    key ideas: Driver–rider matching strategy, trip lifecycle, pricing strategy

    Flipkart · Uber

  • Stock Exchange / Order Matching Engine (opens in a new tab) hard · skim

    Keep buy and sell order books per stock and match orders by price and time priority; support cancels.

    key ideas: Order book (PriorityQueue per price), matching rules, concurrency

    Navi

L7 Catalog, Cart & Order Modelling 4

how to approach · start with Pizza Ordering → Food Delivery Cart → Shopping Cart with Coupons

Mostly entity design: get the nouns, relationships and order lifecycle right.

steps

  1. Extract nouns (User, Item, Cart, Order, Menu…).
  2. Draw relationships (1:N, N:M) and ownership.
  3. Model the cart / order lifecycle as states.
  4. Decorator or Builder for customisable items (toppings, add-ons).
  5. Search / filter via Specification or Strategy.
patterns
Builder, Decorator, State, Specification / Strategy (filters), Observer
follow-ups & traps
Price / discount rules; inventory; search filters; multi-restaurant carts.
start with
Pizza Ordering → Food Delivery Cart → Shopping Cart with Coupons

## multithreading concurrency rounds

M1 Thread Signalling Basics 4

how to approach · start with Print in Order → FooBar → Zero-Even-Odd

Make threads take turns in a fixed order using shared state plus a way to wait and wake.

steps

  1. Name the shared state (turn counter / flag).
  2. Pick the primitive (mutex + condition, semaphore, latch).
  3. Always wait in a while loop (spurious wake-ups).
  4. After changing state, signalAll / notifyAll.
  5. Check: no deadlock, no lost wake-up, correct order.
patterns
Mutex + Condition, Semaphore, CountDownLatch, Barrier
follow-ups & traps
Using if instead of while; notify() lost wake-ups; forgetting to unlock in finally.
start with
Print in Order → FooBar → Zero-Even-Odd
  • Print in Order (opens in a new tab) easy · core · W3 · ★ extra

    Three threads call first(), second(), third() in any order; make the output always come out in order.

    LC 1114 key ideas: Ordering with semaphores / latches / condition variables

  • Print FooBar Alternately (opens in a new tab) easy · W3 · ★ extra

    Two threads print "foo" and "bar"; make them alternate exactly n times.

    LC 1115 key ideas: Two-thread alternation, mutex + condition variable

  • Print Zero-Even-Odd (opens in a new tab) medium · skim · ★ extra

    Three threads cooperate to print 0 1 0 2 0 3 … by passing the turn between them.

    LC 1116 key ideas: Three-thread coordination, state variable + condition

  • Building H2O (opens in a new tab) medium · skim · ★ extra

    Hydrogen and oxygen threads must group into exact H₂O molecules before any of them proceeds (a barrier).

    LC 1117 key ideas: Barrier + semaphores, grouping threads

M2 Producer–Consumer & Queues 4

how to approach · start with Bounded Blocking Queue → Producer–Consumer → Async Logger

Decouple producers from consumers with a bounded buffer; block when full or empty.

steps

  1. State the invariant: 0 ≤ size ≤ capacity.
  2. Lock + two conditions (notFull, notEmpty) or two semaphores.
  3. enqueue waits while full; dequeue waits while empty.
  4. After each operation signal the opposite condition.
  5. Add shutdown (poison pill), timeouts, backpressure.
patterns
BlockingQueue, Semaphore pair, Condition variables
follow-ups & traps
Multiple producers / consumers; fairness; timed offer/poll; graceful shutdown; batching.
start with
Bounded Blocking Queue → Producer–Consumer → Async Logger
  • Design Bounded Blocking Queue (opens in a new tab) medium · core · W3

    A fixed-capacity queue: enqueue blocks while full, dequeue blocks while empty, safe for many threads.

    LC 1188 key ideas: Lock + 2 conditions or 2 semaphores; avoid lost wake-ups and deadlock

    Rubrik

  • Producer–Consumer (wait/notify, semaphores, BlockingQueue) (opens in a new tab) medium · core · W3

    Producers and consumers share a buffer; solve it three ways and explain the trade-offs.

    key ideas: Thread signalling, shutdown/poison pill, backpressure

    Netflix

  • Async Logger / Batched Writer with Background Thread medium · skim · ★ extra

    Callers log without blocking; a background thread batches and writes, and flushes on shutdown.

    key ideas: Queue + worker, flush policy, graceful shutdown

  • Connection / Object Pool (blocking, timeouts) medium · skim · ★ extra

    Lend a fixed number of connections, block or time out when none are free, and never leak one.

    key ideas: Semaphore-bounded pool, validation, leak handling

M3 Thread Pools & Executors 4

how to approach · start with Thread Pool → Scheduled Executor → DAG Task Scheduler

A fixed set of worker threads pulls tasks from a queue; extend with delays, futures and dependencies.

steps

  1. Core = bounded queue + N workers looping take().
  2. submit() returns a Future (result + exception).
  3. Decide the rejection policy when the queue is full.
  4. Shutdown: stop accepting, drain, interrupt.
  5. Scheduling: DelayQueue / PriorityQueue + timed wait.
  6. DAG tasks: track indegree, run when ready.
patterns
Worker pool, Future / Promise, DelayQueue, topological order
follow-ups & traps
Task exceptions; timeouts; reclaiming stuck threads; cancellation; work stealing.
start with
Thread Pool → Scheduled Executor → DAG Task Scheduler

M4 Locks, Sync Primitives & Deadlock 6

how to approach · start with Dining Philosophers → Reader–Writer Lock → Custom Latch / Semaphore

Reason about correctness: mutual exclusion, visibility, ordering and deadlock.

steps

  1. List shared variables and who writes them.
  2. Choose granularity: one lock vs striped locks vs lock-free (CAS).
  3. Check the 4 deadlock conditions; break one (lock ordering is the usual fix).
  4. Prefer tryLock with timeout where possible.
  5. Check visibility (volatile / happens-before).
patterns
ReentrantLock, ReadWriteLock, Atomics / CAS, lock ordering, double-checked locking
follow-ups & traps
Starvation; fairness; reentrancy; upgrade / downgrade; "can you remove the lock?".
start with
Dining Philosophers → Reader–Writer Lock → Custom Latch / Semaphore
  • Thread-Safe Singleton (double-checked locking, volatile) easy · skim · ★ extra

    Create exactly one instance lazily under concurrency, and explain why volatile is needed.

    key ideas: Memory visibility, happens-before, initialization-on-demand holder

  • Lock-Free Counter / CAS ("can I remove the lock?") (opens in a new tab) medium · skim

    Make a counter or stack thread-safe without locks using compare-and-swap, and discuss ABA.

    key ideas: AtomicInteger, compare-and-swap, ABA, follow-up on removing locks

    Pure Storage

  • Custom CountDownLatch / CyclicBarrier / Semaphore medium · skim · ★ extra

    Implement these primitives with a lock and conditions to show how they work underneath.

    key ideas: Build sync primitives from monitor (wait/notify)

  • The Dining Philosophers (opens in a new tab) medium · core · W4 · ★ extra

    Five philosophers share five forks; let them all eat without deadlock or starvation.

    LC 1226 key ideas: Deadlock avoidance: lock ordering / resource hierarchy

  • Reader–Writer Lock (fair / writer-preference) (opens in a new tab) hard · core · W4

    Many readers or one writer at a time, without starving writers; then make it fair.

    key ideas: Starvation, reentrancy, upgrade/downgrade

    Netflix

  • Deadlock Detection & Prevention (wait-for graph) hard · skim · ★ extra

    Detect deadlock with a wait-for graph, then prevent it with lock ordering or tryLock timeouts.

    key ideas: Lock ordering, tryLock with timeout, cycle detection

M5 Thread-Safe Products (applied) 5

how to approach · start with Thread-Safe Rate Limiter → Thread-Safe LRU → Pub/Sub

Take a normal LLD design and make it correct under concurrency.

steps

  1. Write the single-threaded design first.
  2. Mark shared mutable state and the invariant that must hold.
  3. Choose lock scope (per key / per resource), not one global lock.
  4. Make check-and-act atomic (computeIfAbsent, CAS).
  5. Walk through 2 threads on the critical path.
patterns
ConcurrentHashMap, per-key locks, atomic counters, optimistic vs pessimistic locking
follow-ups & traps
Hot keys; memory growth; lock contention; the distributed version of the same problem.
start with
Thread-Safe Rate Limiter → Thread-Safe LRU → Pub/Sub

## high-level design system design

H1 Real-Time Fan-out & Delivery 4

how to approach · start with Notification → News Feed → Chat

One event must reach many users quickly and reliably: feeds, messages, notifications, collaboration.

steps

  1. Requirements + scale (DAU, fan-out ratio).
  2. Choose push (fan-out on write), pull (on read) or hybrid for celebrities.
  3. Async pipeline: queue → workers → per-channel senders.
  4. Persistent connections (WebSocket) + presence for real time.
  5. Retries, dedup, ordering, delivery receipts.
patterns
Queues / Kafka, cache, WebSockets, fan-out, idempotency
follow-ups & traps
Celebrity with 100M followers; ordering guarantees; offline users; per-user rate limiting; multi-region.
start with
Notification → News Feed → Chat
  • Notification System (opens in a new tab) medium · core · W5

    Send millions of push, SMS and email notifications reliably, with user preferences, retries and rate limits.

    key ideas: Fan-out, channels, retries, dedup/idempotency, priority queues

    Meta · Amazon · Airbnb · Uber · Google

  • Chat / Messaging System (WhatsApp) (opens in a new tab) medium · core · W6

    1:1 and group chat with online status, delivery and read receipts, and offline message delivery.

    key ideas: WebSockets, delivery receipts, ordering, presence, group fan-out

    Meta · Uber · Apple · Discord · Tesla

  • News Feed / Twitter Timeline (opens in a new tab) medium · core · W5

    Build each user’s feed from accounts they follow; choose fan-out on write vs read, including celebrities.

    key ideas: Fan-out on write vs read, celebrity problem, ranking, caching

    Meta · Twitter/X · Dropbox · Microsoft · Amazon · LinkedIn

  • Collaborative Editing (Google Docs) (opens in a new tab) hard · skim

    Many users edit one document live; merge concurrent edits (OT or CRDT) and show cursors.

    key ideas: OT vs CRDT, presence, versioning, offline edits

    Google · Palantir

H2 Geo-Indexing & Marketplaces 4

how to approach · start with Nearby Places → Ride-Sharing → Food Delivery → Maps

Match supply and demand by location in real time.

steps

  1. Define entities: rider, driver, order.
  2. Index locations with geohash / quadtree / S2.
  3. Handle frequent location updates in memory + stream, not DB writes.
  4. Matching service + dispatch with timeouts.
  5. ETA and pricing as separate services.
patterns
Geo-index, streaming, cache, sharding by region
follow-ups & traps
Hot cities; surge pricing; driver re-assignment; assignment consistency.
start with
Nearby Places → Ride-Sharing → Food Delivery → Maps

H3 Consistency, Booking & Payments 5

how to approach · start with Ticket Booking → Payment / Ledger

Correctness over speed: no double-sell, no double-charge.

steps

  1. Name the invariants (a seat sold once; money in = money out).
  2. Reserve with a TTL lock, then confirm on payment.
  3. Idempotency keys on every write API.
  4. Pick the transaction model: ACID DB for the core, saga for multi-service.
  5. Reconcile asynchronously.
patterns
Idempotency, DB transactions, distributed locks / leases, saga / outbox, queues
follow-ups & traps
Flash-sale traffic; payment timeout; retries; exactly-once effects; reconciliation.
start with
Ticket Booking → Payment / Ledger

H4 Blob Storage, Metadata & CDN 6

how to approach · start with Dropbox → YouTube → S3

Big files live in object storage, metadata lives in a DB, and users read through a CDN.

steps

  1. Split data: blobs vs metadata.
  2. Chunk + resumable upload with pre-signed URLs.
  3. Async processing (transcode, thumbnails) via a queue.
  4. CDN + caching for reads.
  5. Dedup / versioning / sync in the metadata service.
patterns
Object store, chunking, CDN, queues, content hashing
follow-ups & traps
Sync conflicts; resume large uploads; cost tiers; hot content; durability (erasure coding).
start with
Dropbox → YouTube → S3
  • Pastebin easy · skim · ★ extra

    Store text snippets and share them by short URL, with expiry; a gentle intro to blob plus metadata storage.

    key ideas: Object store + metadata DB, expiry, CDN

  • Cloud File Storage (Dropbox / Google Drive) (opens in a new tab) medium · core · W6

    Upload, sync and share files across devices: chunking, deduplication, versioning and conflicts.

    key ideas: Chunking, dedup, sync protocol, metadata service, conflict resolution

    Google · Amazon · Microsoft · Dropbox

  • Video Streaming (YouTube / Netflix) (opens in a new tab) medium · skim

    Upload, transcode into many qualities, and stream through a CDN with adaptive bitrate.

    key ideas: Upload pipeline, transcoding, CDN/ABR, recommendations

    Google · Netflix · TikTok · Amazon · Meta

  • Instagram / Photo Sharing (opens in a new tab) medium · skim

    Upload photos, follow users and build a feed; store media and serve it fast worldwide.

    key ideas: Media storage, feed, CDN, graph storage

    Meta

  • Object Storage (S3-style) (opens in a new tab) hard · skim

    Store huge numbers of blobs durably: buckets, metadata, replication or erasure coding.

    key ideas: Erasure coding, metadata/data separation, durability, multipart upload

    Amazon · Backblaze · Google

  • CDN Design hard · skim · ★ extra

    Cache content close to users: routing to edges, cache fill and invalidation, origin protection.

    key ideas: Edge caching, cache invalidation, origin shield, routing

H5 Search, Indexes & Crawling 3

how to approach · start with Autocomplete → Web Crawler → Full-Text Search

Precompute structures so reads are fast; keep indexing separate from serving.

steps

  1. Define query types (prefix, keyword, geo).
  2. Pick the index (trie / inverted index / geo).
  3. Offline or streaming pipeline builds the index.
  4. Cache hot queries; rank results.
  5. Crawler: frontier + politeness + dedup.
patterns
Trie, inverted index, Bloom filter, cache, queue / scheduler
follow-ups & traps
Freshness; typo tolerance; personalisation; sharding the index; per-domain politeness.
start with
Autocomplete → Web Crawler → Full-Text Search

H6 Stream Aggregation & Analytics 4

how to approach · start with Top-K → Ad Click Aggregator → Metrics

Ingest massive event streams and answer aggregate questions (counts, Top-K) with bounded error and latency.

steps

  1. Clarify accuracy vs latency (exact vs approximate).
  2. Ingest through a partitioned log (Kafka).
  3. Window + aggregate in a stream processor.
  4. Store rollups in OLAP / TSDB.
  5. Handle late events and duplicates.
patterns
Kafka, stream processing, count-min sketch, TSDB / OLAP, dedup
follow-ups & traps
Exactly-once; hot keys; backfill; cardinality explosion.
start with
Top-K → Ad Click Aggregator → Metrics

H7 Core Distributed Infrastructure 10

how to approach · start with URL Shortener → Rate Limiter → Job Scheduler → KV Store → Kafka

The reusable pieces everything else is built from: limiters, KV stores, caches, queues, schedulers, locks.

steps

  1. Define the API + guarantees (at-least-once? ordering?).
  2. Partition data (consistent hashing).
  3. Replicate (leader / follower, quorum).
  4. Define failure behaviour (what happens when a node dies).
  5. Add observability + backpressure.
patterns
Consistent hashing, replication / quorum, Raft / Paxos, leases / fencing tokens, WAL
follow-ups & traps
Hot partitions; rebalancing; clock skew; split brain; exactly-once.
start with
URL Shortener → Rate Limiter → Job Scheduler → KV Store → Kafka
  • URL Shortener (TinyURL) (opens in a new tab) easy · core · W5

    Turn long URLs into short codes and redirect fast; ID generation, caching and analytics.

    key ideas: Base62/hash IDs, KV store, caching, redirect latency, multi-DC

    Uber · Amazon · LinkedIn · Palantir · Google · Microsoft · Meta · Atlassian

  • Rate Limiter (distributed) (opens in a new tab) easy · core · W5

    Limit requests per user across many servers with shared counters and low added latency.

    key ideas: Token bucket/sliding window in Redis, race conditions, per-tenant config

    Amazon · Atlassian · Uber · Microsoft · Stripe · Pinterest · Google

  • Distributed Key-Value Store (opens in a new tab) medium · W7

    A Dynamo-style store: partitioning, replication, quorum reads and writes, and failure handling.

    key ideas: Consistent hashing, replication, quorum, LSM trees

    Google · Anthropic

  • Job Scheduler (opens in a new tab) medium · core · W5

    Run millions of scheduled and recurring jobs on time, at least once, with retries.

    key ideas: Delayed/recurring jobs, at-least-once execution, sharding, leases

    Google · Amazon · Microsoft · DoorDash · Netflix · Atlassian

  • Online Coding Judge (opens in a new tab) medium · skim

    Run user code safely in sandboxes, judge it against test cases, and handle contest spikes.

    key ideas: Sandboxing, execution queue, isolation, result delivery

    Meta · Google

  • Distributed Cache (opens in a new tab) medium · skim

    A shared cache like Redis: sharding with consistent hashing, replication and eviction.

    key ideas: Sharding, eviction, hot keys, replication, invalidation

  • Distributed Message Queue (Kafka-like) hard · W7 · ★ extra

    Durable, partitioned log with producers, consumer groups, ordering and replay.

    key ideas: Partitioning, replication/ISR, ordering, consumer rebalancing

  • Distributed Lock Service (Chubby-like) (opens in a new tab) hard · skim

    Let services hold locks safely across machines using consensus, leases and fencing tokens.

    key ideas: Paxos/Raft, leases, fencing tokens, clock issues

  • Code Deployment System (opens in a new tab) hard · skim

    Build once and roll out to thousands of machines fast and safely, with rollback.

    key ideas: Build/artifact pipeline, rollout strategies, rollback, health checks

  • Distributed ID Generator (Snowflake) + Distributed Counter hard · skim · ★ extra

    Generate unique, roughly ordered IDs without a central bottleneck, and count at scale.

    key ideas: Clock skew, sharded counters, uniqueness vs ordering

H8 AI / LLM Infrastructure 5

how to approach · start with LLM Gateway → GPU Inference Batching → RAG / Semantic Search

GPU-heavy, long-running, expensive requests: batching, scheduling and metering matter most.

steps

  1. Define latency vs throughput targets.
  2. Queue + dynamic batching to keep GPUs busy.
  3. Fair scheduling + preemption / checkpointing for long jobs.
  4. Meter tokens / cost for quotas.
  5. Distribute large model artefacts with versioned rollouts.
patterns
Queues, schedulers, token-bucket quotas, caching, blob distribution
follow-ups & traps
Cold start; autoscaling; noisy neighbours; cost control.
start with
LLM Gateway → GPU Inference Batching → RAG / Semantic Search
  • Task Scheduler for Long-Running GPU Jobs ("Design Sora") (opens in a new tab) hard · skim

    Queue and run long, expensive GPU jobs (e.g. video generation) fairly, with progress and retries.

    key ideas: Queueing, fair scheduling, preemption, checkpointing, cost

    Google

  • Billing-Token Rate Limiter for AI Agents (opens in a new tab) hard · skim

    Limit and bill AI usage by tokens rather than requests, per user and per agent.

    key ideas: Token accounting, quotas, burst vs sustained, consistency

    Google

  • GPU Inference Request Batching / LLM Serving (opens in a new tab) hard · skim

    Serve a large model with low latency by batching requests on GPUs and streaming tokens back.

    key ideas: Dynamic batching, queueing, latency/throughput, autoscaling

    Anthropic · Google · OpenAI

  • LLM Gateway (multi-provider routing & fallback) medium · ★ extra

    One API in front of several LLM providers: routing, automatic fallback, quotas and cost tracking.

    key ideas: Unified API, provider adapters, routing, fallback, quotas, cost tracking

  • RAG / Semantic Search System hard · ★ extra

    Answer questions over your documents: chunk and embed them, search a vector index, and ground the answer.

    key ideas: Chunking + embeddings, vector index, retrieval + re-ranking, freshness

## reference cheat sheets

5 LLD patterns that solve most problems
Strategy
A behaviour has several interchangeable algorithms (pricing, eviction, matching, rules).
e.g. Rate limiter algorithms, LRU/LFU eviction, parking pricing, split types
State
An object behaves differently depending on its state; transitions are rule-driven.
e.g. Vending machine, elevator, order / payment lifecycle, game status
Observer
Many parties must react when something changes.
e.g. Notification service, pub/sub, price alerts, UI updates
Factory
Object creation depends on type or config and callers should not know the concrete class.
e.g. Vehicle / piece / limiter creation, notification channels
Command
Operations must be queued, logged, undone or replayed.
e.g. Text editor undo/redo, canvas commands, transaction log
12 HLD building blocks
Caching & invalidation
Reach for it when: Read-heavy traffic, hot keys
Trade-off: Staleness, invalidation complexity
shows up in URL shortener, feed, autocomplete
Sharding / consistent hashing
Reach for it when: Data or QPS exceeds one node
Trade-off: Hot shards, rebalancing, cross-shard queries
shows up in KV store, cache, chat
Replication & quorum
Reach for it when: Availability and durability
Trade-off: Consistency vs latency (CAP / PACELC)
shows up in KV store, DBs, queues
Queues & streams (Kafka)
Reach for it when: Async work, smoothing spikes
Trade-off: At-least-once ⇒ need idempotency; ordering only per partition
shows up in Notifications, ad clicks, logging
Fan-out on write vs read
Reach for it when: One-to-many delivery
Trade-off: Write amplification vs read latency
shows up in Feed, notifications, group chat
Idempotency & exactly-once effects
Reach for it when: Retries, payments, bookings
Trade-off: Needs key storage and a dedup window
shows up in Payments, ticketing, ledger
Geo-indexing
Reach for it when: Location queries
Trade-off: Cell-boundary issues, hotspots
shows up in Uber, maps, delivery
Blob storage + metadata + CDN
Reach for it when: Large media and files
Trade-off: Metadata consistency, cost, durability
shows up in Dropbox, YouTube, S3
Search: inverted index / trie
Reach for it when: Text and prefix queries
Trade-off: Index freshness and size
shows up in Autocomplete, search, crawler
Stream aggregation & sketches
Reach for it when: Counts / Top-K on streams
Trade-off: Approximation error, late data
shows up in Ad clicks, metrics, Top-K
Rate limiting
Reach for it when: Protect services, meter usage
Trade-off: Accuracy vs cost; distributed counters
shows up in API gateway, AI billing
Consensus & locking (Raft, leases, fencing)
Reach for it when: Leader election, coordination
Trade-off: Latency, complexity, clock skew
shows up in Lock service, scheduler, KV store
concurrency checklist
1. What is the shared state?
Write down every variable touched by more than one thread and who writes it.
2. What invariant must always hold?
E.g. 0 ≤ size ≤ capacity; a seat has at most one owner. Check it after every critical section.
3. What should a thread wait for?
Express it as a condition on shared state; wait in a while loop, never if.
4. Who wakes it up, and when?
Signal after every state change that can satisfy a waiter (signalAll if unsure).
Deadlock = 4 conditions
Mutual exclusion, hold-and-wait, no preemption, circular wait. Break one — usually via global lock ordering or tryLock with timeout.
Lock granularity
Global lock → striped / per-key lock → lock-free (CAS). Justify the choice with contention and complexity.
Always release in finally
Unlock / release in finally so exceptions cannot leave a lock held.
interview time-boxes
LLD / machine coding (60 min)
Clarify 5 → entities 5 → class diagram + APIs 10 → code core flow 25 → edge cases + concurrency 8 → extensibility / follow-ups 7.
HLD (45 min)
Requirements 5 → estimation 5 → API 5 → data model 5 → high-level design 10 → deep dive on 2 components 10 → bottlenecks, failures, trade-offs 5.
Multithreading round
State the shared state + invariant first → write the simple version → add synchronisation → walk through 2 threads → discuss follow-ups (timeouts, shutdown, fairness).