System design interview questions

Design a service like bit.ly: users submit a long URL and get a short link; opening the short link redirects to the original. Expect ~100M new URLs/month and a much higher read:write ratio. Walk a full 45-minute design.

Asked at: Amazon, Google, Microsoft, Uber — most common system-design opener · Difficulty: Medium · Pattern: Hashing · base62 IDs · read-heavy cache

• Custom aliases? Expiry? Auth?
• Analytics (click counts) required?
• Latency: redirect p99 < 100ms?
• Availability target (e.g. 99.9%)?
• Assume ~7-char base62 codes unless they specify otherwise.

1. API: POST /shorten {url, alias?} → code; GET /{code} → 302 Location: long URL.
2. Capacity: 100M/mo ≈ 40 writes/s avg; reads can be thousands/s — cache is mandatory. Storage: 100M × ~500B ≈ 50GB+/yr metadata (order-of-magnitude OK).
3. ID generation (pick one & defend): (1) distributed counter + base62; (2) hash URL + collision handling; (3) pre-generated key pool for bursts.
4. Data model: code → {long_url, user_id, created, expires, clicks?}. KV/NoSQL or sharded SQL by code hash.
5. Read path: edge/CDN optional → LB → app → Redis → DB. Prefer 302 (mapping can change; analytics stay server-side) unless they insist on 301.
6. Analytics: async click events to Kafka/queue — never block redirect.
7. Abuse: rate-limit shorten; malware URL scan offline.

• Hot keys: viral links — cache replicas / local caches.
• Enumeration: avoid raw sequential public IDs; salt / skip / encrypt.
• Multi-region: replicate read-only mappings; write to primary with async replication.
• Custom aliases: conditional put; reject if taken.

Design a photo-sharing social network: follow users, upload photos, see a home feed of posts from people you follow (roughly reverse-chronological with light ranking).

Asked at: Meta, Instagram, Twitter/X interviews · Difficulty: Hard · Pattern: Hybrid fan-out · timeline cache · media CDN

• Scale: hundreds of millions of users?
• Celebrity / mega-follower problem in scope?
• Stories? Likes counters? Ranking ML?
• Consistency: eventual feed OK?

1. Write media: pre-signed upload → object store + CDN; metadata row (post_id, author, caption, media_url, ts).
2. Fan-out on write: push post_id into each follower's timeline cache (Redis lists) — great for normal users.
3. Fan-out on read / pull: for celebrities, do not push to tens of millions of timelines; merge recent posts at read time.
4. Hybrid: write-fanout for normals, pull for celebs (or inactive users).
5. Read path: auth → timeline cache → hydrate posts → CDN URLs.
6. Ranking: start chronological; add retrieval + re-rank stage later.
7. Sharding: user_id for timelines; post_id for posts.

• Counters (likes/views): sharded in-memory with periodic flush; approximate display OK.
• Notifications / stories: separate services + queues.
• Feed can be eventually consistent; durable post metadata is enough for ACK.

Design 1:1 and group messaging with delivery receipts, online presence, and media sharing. Focus on low latency and reliability.

Asked at: Meta, WhatsApp, Slack, Discord-style rounds · Difficulty: Hard · Pattern: WebSocket · durable log · presence · group fan-out

• E2E encryption in scope?
• Max group size?
• Multi-device sync?
• Message history retention?

1. Connections: sticky WebSocket/MQTT to chat servers; presence map user→server in Redis.
2. Send path: client → chat server → durable queue/log (Kafka) → fan-out to recipient inboxes → push to online sockets or store-and-forward if offline.
3. ACK: persist before ACK to sender (at-least-once); clients de-dupe by message_id.
4. Ordering: per-conversation monotonic sequence from a single partition/writer.
5. Groups: small → fan-out to members; large → group log + members catch up / notify online only.
6. Media: upload to blob store; message carries URL/thumbnail.
7. Presence: heartbeats with short TTL.
8. Receipts: separate lightweight events; do not block delivery.

Design a distributed rate limiter for an API gateway: e.g. 100 requests per user per minute, consistent across many gateway instances.

Asked at: Amazon, Stripe, Cloudflare, Google — building-block favorite · Difficulty: Medium · Pattern: Token bucket · sliding window · Redis

• Token bucket: refill rate r; burst capacity — industry default.
• Leaky bucket: smooth constant outflow.
• Fixed window: simple counters; edge burst problem.
• Sliding window log/counter: fairer, more cost.

1. Gateways call a shared store (Redis) before forwarding.
2. Use atomic ops (INCR+EXPIRE or Lua) for token bucket — avoid races.
3. On deny: HTTP 429 + Retry-After.
4. Dimensions: per API key / IP / endpoint / tenant.
5. Multi-region: regional limiters + global budget, or accept approximate limits.
6. Redis down: product call — fail open vs fail closed.

# token bucket keys: tokens={key}, ts={key}
# atomic Lua: refill based on elapsed time, consume 1 if tokens>=1
# else return limited

Design ride-hailing: riders request trips, nearby drivers are matched, locations update in realtime, pricing/ETA computed.

Asked at: Uber, Lyft, DoorDash-adjacent geo interviews · Difficulty: Hard · Pattern: Geo index · matching · trip state machine

• Cities / regions in scope?
• ETA accuracy expectations?
• Surge pricing?
• Driver app battery / update frequency?

1. Location stream: drivers send GPS every few seconds → update geo index (geohash / S2 cells in Redis or specialized store).
2. Request: rider → query nearby cells → filter status/vehicle → rank by ETA/rating → offer with timeout → expand ring on miss.
3. Double dispatch: atomic claim / CAS on driver status with lease; only one rider wins.
4. Trip lifecycle: requested → matched → enroute → ongoing → completed (state machine + events to billing/notify).
5. ETA: map-match + traffic-aware routing service; cache segments.
6. Surge: demand/supply per cell, smoothed (EMA), capped rate of change.
7. Scale: shard by city/region — traffic is local.

Design video upload and streaming: users upload; millions watch with adaptive quality worldwide.

Asked at: Google, Netflix, Meta — storage + CDN heavy · Difficulty: Hard · Pattern: Transcoding pipeline · CDN · adaptive bitrate

1. Upload: pre-signed URL → direct to object store; metadata = processing.
2. Pipeline: queue workers transcode many resolutions/codecs, thumbs, duration → HLS/DASH segments → mark ready. Fast-start low-res first.
3. Playback: client fetches manifest; CDN serves segments; origin is object store; ABR by bandwidth.
4. Hot titles: heavy edge caching; short TTL for live.
5. Live: separate ingest POPs → packager → CDN; not the VOD path.
6. Cost: lifecycle to cold storage; fewer bitrates for rarely watched; copyright fingerprinting async.
7. Recs: offline ML + online re-rank — off the play path.

Design multi-channel notifications: push, email, SMS, in-app — with preferences, retries, and high throughput.

Asked at: Amazon, Meta, Uber, Slack · Difficulty: Medium · Pattern: Fan-out · priority queues · templates · DLQ

1. Producers enqueue jobs (do not block product writes).
2. Preferences/quiet-hours gate before send.
3. Kafka topics by priority/channel → workers render templates → provider adapters (APNs/FCM, SES, Twilio).
4. Idempotency keys; rate-limit per user and per provider.
5. Retries with exponential backoff → DLQ for poison messages.
6. Large audiences: chunked fan-out tasks.
7. Aim at-least-once + idempotent display — not exactly-once fantasy.

Design search autocomplete that returns top suggestions as the user types, with low latency and some trending awareness.

Asked at: Google, Amazon, Twitter · Difficulty: Medium · Pattern: Trie · top-k · edge cache

1. Offline: aggregate query logs → top-k per prefix → build trie/prefix index → ship snapshots to servers/edge.
2. Online: client debounces; request prefix → memory trie returns top-k (<50ms); light personalization/trending re-rank.
3. Cache popular prefixes at CDN/edge.
4. Limit prefix length; store only top-k not full postings.
5. Shard trie by first character(s) if needed.
6. Refresh index on minutes cadence — not per keystroke.

Design a distributed in-memory cache: get/put/delete, TTL, HA, horizontal scale.

Asked at: Amazon, Microsoft, Oracle — Redis/Memcached style · Difficulty: Hard · Pattern: Consistent hashing · replication · eviction

1. Client or proxy uses consistent hashing → shard.
2. Each shard: primary + replicas (async or semi-sync).
3. Eviction: LRU/LFU + TTL per node.
4. Membership via gossip/config service; virtual nodes for balance.
5. Hot keys: replicate popular keys; local caches.
6. Stampede: soft TTL + singleflight / probabilistic early expire.
7. Write strategies: invalidate-on-write common; write-through / behind when justified.
8. CAP: prefer AP for cache; miss → load DB.
9. Persistence optional — usually ephemeral by design.

Design ticketing for concerts: browse events, hold seats, pay, issue tickets — without double-selling under spikes.

Asked at: Amazon, Ticketmaster-style concurrency interviews · Difficulty: Hard · Pattern: Inventory locks · holds · idempotent payment

1. Browse: read replicas + CDN for event pages; seat maps cached carefully.
2. Inventory states: available → held → sold.
3. Hold: soft lock with short TTL (2–10 min) via Redis or conditional row update.
4. Checkout: create hold → payment intent → on success commit seats + ticket IDs; on fail/expiry release hold.
5. Idempotency: keys on payment webhooks — no double charge / double sell.
6. Consistency: strong on inventory (CAS / UPDATE … WHERE status='available').
7. Scale: shard by event_id; waiting rooms / queues for mega on-sales.

Design a cloud file storage and sync service: upload/download files, sync across devices, share folders, and handle large files efficiently.

Asked at: Meta, Amazon, Google, Microsoft — top file-storage design · Difficulty: Hard · Pattern: Chunked upload · sync · metadata vs blob

• Max file size? Concurrent editors?
• Version history? Offline sync?
• Sharing ACLs / links?

1. Split metadata and bytes: metadata DB (file_id, path, versions, ACL); blobs in object storage.
2. Chunk files (e.g. 4MB); content-hash chunks for dedupe; upload only missing chunks.
3. Sync protocol: client keeps local revision; pull delta since last sync; conflict → last-write-wins or branch versions.
4. Notifications: long-poll / websocket for file-change events to other devices.
5. Large uploads: multipart / resumable; commit metadata only when all chunks ACK'd.
6. Sharing: ACL on folder nodes; link tokens with expiry.

• Namespace tree sharding by owner_id.
• CDC from metadata → search index.
• Client block-level sync (rsync-like) for huge files.

Design a distributed web crawler that discovers and fetches pages at large scale while respecting robots.txt and politeness limits.

Asked at: Google, Amazon — classic distributed systems question · Difficulty: Hard · Pattern: URL frontier · politeness · dedupe

1. URL frontier: prioritized queue of URLs to fetch (BFS / priority by PageRank estimate).
2. Dedupe: seen URL set (Bloom + store); canonicalize URLs.
3. Politeness: per-host rate limits; respect robots.txt (cache rules).
4. Workers: fetch → extract links → enqueue new URLs; store raw HTML / parse text.
5. Distributed: shard frontier by host hash so one host stays on one worker (politeness).
6. Failure: retries, crawl budget, blacklist bad hosts.

Design a payment service that charges cards, handles retries safely, supports refunds, and keeps an accurate ledger under failures.

Asked at: Stripe, PayPal, Amazon, Square — money-moving design · Difficulty: Hard · Pattern: Idempotency · ledger · saga / outbox

1. Idempotency keys on every charge from the client — retries must not double-charge.
2. API: create PaymentIntent → confirm → capture (or auth+capture).
3. Ledger: append-only double-entry journal; balances derived — never overwrite money rows.
4. Provider calls: stripe/processor behind adapter; store provider refs; reconcile webhooks with signature verify.
5. Distributed tx: transactional outbox or saga for order ↔ payment; compensating refunds on failure.
6. PCI: never store raw PAN; use tokens; isolate network.

Design a game leaderboard that supports updating a player's score and fetching top-K and a player's rank with low latency.

Asked at: Amazon, Meta, gaming companies — realtime ranking · Difficulty: Medium · Pattern: Sorted sets · sharding · top-k

1. Redis ZSET (score → member) for one board: ZADD update, ZREVRANGE top-K, ZREVRANK for rank — O(log n).
2. Scale: shard by competition/season; or by player hash with aggregation for global top-K (harder).
3. Ties: use score + timestamp composite.
4. Historical boards: snapshot immutable ZSET per season.
5. Fan-out reads with cache; writes go to primary.

Design a Dynamo-style distributed key-value store with put/get, high availability, and horizontal scale.

Asked at: Amazon (Dynamo), Google — fundamentals of distributed DBs · Difficulty: Hard · Pattern: Consistent hashing · quorum · replication

1. Consistent hashing ring + virtual nodes for partition.
2. N replicas on successor nodes; client or coordinator uses quorum R/W (e.g. N=3, R=2, W=2).
3. Versioning: vector clocks / version numbers; reconcile conflicts (last-write-wins or client merge).
4. Hinted handoff + anti-entropy (Merkle trees) for temporary failures.
5. Tunable consistency: CAP — prefer AP with eventual consistency for shopping-cart style.

Different from a cache: durability, replication, conflict resolution, and anti-entropy are first-class.

Design a pub/sub log that supports high-throughput producers, consumer groups, and durable retention.

Asked at: LinkedIn, Amazon, Uber, Confluent-style interviews · Difficulty: Hard · Pattern: Partitions · consumer groups · retention

1. Topics split into partitions (ordered append logs).
2. Producers pick partition by key (ordering per key) or round-robin.
3. Replicas: leader + followers; ack on ISR.
4. Consumer groups: each partition → one consumer in the group; commit offsets.
5. Retention by time/size; consumers are pull-based.
6. Scale: more partitions; rebalance on membership change.

Design a pastebin: users paste text, get a unique URL, optional expiry and syntax highlighting.

Asked at: Amazon, Meta — easier SD warmup after URL shortener · Difficulty: Medium · Pattern: Object storage · short IDs · expiry

1. Similar to URL shortener: generate short id; store content in object store or DB (small pastes in DB, large in blob).
2. Metadata: id, expiry, visibility, user.
3. CDN/cache for public pastes; rate-limit create.
4. GC expired pastes with TTL sweeper.
5. Optional: raw vs HTML view; password-protected pastes.

Design the core of a maps/navigation product: show maps, find places, and compute routes with ETA.

Asked at: Google, Uber — geo + routing · Difficulty: Hard · Pattern: Map tiles · graph routing · ETA

1. Tiles: pre-render / vector tiles by zoom; CDN heavily.
2. Places search: geospatial index + text (similar to typeahead + geo filter).
3. Road graph: nodes/edges with travel times; Dijkstra / A* / contraction hierarchies for speed.
4. ETA: traffic-aware edge weights updated nearline.
5. Client: request route → server returns polyline + steps; reroute on deviation.

Shares geo indexing ideas with Uber matching (Q5) but routing graph is the heart.