System Design Problems Interview Questions

Summary

Generate short unique codes mapped to long URLs, serve redirects with very low latency from a cache, and record click analytics asynchronously. Reads dominate writes (~100:1), so the redirect path is cache-first.

Requirements

• Create a short link for a long URL (optional custom alias, expiry)
• Redirect short → long with low latency (p99 < 50 ms)
• Click analytics per link
• Non-functional: highly available reads, links never collide, 100M new links/month

Back-of-the-envelope

• 100M links/month ≈ 40 writes/s; 100:1 reads ≈ 4,000 redirects/s (peaks 10×)
• ~500 bytes/link → ~600 GB over 10 years
• 7-character base62 codes give 62^7 ≈ 3.5 trillion combinations

API

POST /api/links        {"url": "https://...", "alias": "optional", "expires_at": "optional"}
→ 201 {"code": "aZ3kP9q", "short_url": "https://sho.rt/aZ3kP9q"}
GET  /{code}           → 301/302 Location: https://...
GET  /api/links/{code}/stats → {"clicks": 1234, "by_day": [...]}

Data Model

links(code PK varchar(10), long_url text, owner_id bigint, created_at, expires_at)
clicks(code, ts, country, referrer, ua_family)   -- append-only, in an analytics store

Architecture

Clients hit a CDN/edge, then stateless API servers. Redirects read from Redis (code → URL) with a database fallback (a key-value store or Postgres keyed by code). Link creation obtains a unique ID and encodes it in base62. Click events are pushed to a queue (Kafka) and aggregated by stream processors into an analytics store (ClickHouse).

Deep Dives

• Code generation: a counter-based ID (range allocation per server from a sequence/ZooKeeper/DB) encoded in base62 avoids collisions; random codes need a uniqueness check; hashing the URL needs collision handling
• 301 vs 302: 301 is cached by browsers (less load, fewer analytics); 302 keeps every click visible
• Custom aliases: reserved words, uniqueness via unique constraint
• Abuse: malware URL scanning, rate limits per user/IP

Scaling

• Cache hot codes in Redis and at the edge; hit ratios above 90% are typical
• Shard the links store by code
• Analytics writes go through a queue, never in the redirect path
• Multi-region read replicas for global latency

Comparison / Tradeoffs

Summary

Count requests per key (user, API key, IP) in a shared fast store like Redis using a token bucket or sliding-window algorithm executed atomically, enforce it in a gateway or middleware, and return 429 with Retry-After when limits are exceeded.

Requirements

• Limit requests per client per time window with configurable rules (per endpoint/plan)
• Low added latency (< 2 ms)
• Works across many API servers
• Return limit headers and 429s; fail-open or fail-closed configurable

API

# Middleware decision
allow(key="user:42:POST /orders", limit=100, window=60s) → {allowed: true, remaining: 57, reset: 23s}
# Response headers
RateLimit-Limit: 100   RateLimit-Remaining: 57   Retry-After: 23

Data Model

-- Redis keys (token bucket)
rl:{key} → hash {tokens: float, updated_at: ms}   TTL = window
-- Rules (config DB or file)
rate_rules(id, match_route, match_plan, limit, window_s, burst)

Architecture

Requests pass through an API gateway or middleware that builds the key, loads the matching rule (cached locally), and executes an atomic Lua script in Redis that refills and consumes tokens. Redis is clustered and sharded by key. Rules are distributed via config with hot reload.

Deep Dives

• Algorithms: fixed window (simple, bursty at edges), sliding log (accurate, memory heavy), sliding window counter (good approximation), token bucket (allows bursts, smooth refill)
• Atomicity: a Lua script or Redis functions avoid race conditions between read and write
• Local + global: in-process pre-limiting reduces Redis load for very hot keys
• Failure mode: if Redis is down, fail open for most traffic but fail closed for sensitive endpoints like login

Scaling

• Shard keys across a Redis cluster
• Keep Redis close to gateways (same region)
• Use approximate local counters synchronized periodically for extreme throughput

Comparison / Tradeoffs

Summary

Clients keep persistent WebSocket connections to gateway servers; messages are persisted to a partitioned store, then fanned out to online recipients through a pub/sub layer that knows which gateway holds each user's connection, with push notifications for offline users.

Requirements

• 1:1 and group chats (up to ~1,000 members)
• Real-time delivery, message history, delivery/read receipts
• Online presence
• Offline push notifications
• Non-functional: low latency, ordered messages per conversation, durability

Back-of-the-envelope

• 50M daily users × 40 messages ≈ 2B messages/day ≈ 23K/s average
• ~10M concurrent connections → ~200 gateway servers at 50K connections each

API

WS  /connect   (auth token)  → server pushes {type: "message"|"receipt"|"presence", ...}
WS  send {"type":"message","conversation_id":"c1","client_msg_id":"uuid","body":"hi"}
GET /api/conversations/{id}/messages?before=<message_id>&limit=50

Data Model

messages(conversation_id, message_id /* time-ordered, e.g. Snowflake */, sender_id, body, created_at,
         PRIMARY KEY (conversation_id, message_id))      -- Cassandra/ScyllaDB style
conversation_members(conversation_id, user_id, last_read_message_id)
user_sessions: Redis user_id → gateway_id (with TTL heartbeats)

Architecture

Load balancer → WebSocket gateways (stateful connections only). A gateway forwards incoming messages to a chat service, which assigns a message ID, persists it, and publishes to the recipients via a pub/sub bus (Redis pub/sub or Kafka keyed by user/gateway). Gateways deliver to connected recipients; a notification service sends APNs/FCM pushes to offline ones. Presence uses heartbeats stored in Redis with TTLs.

Deep Dives

• Ordering: per-conversation monotonic IDs; clients sort and dedupe by client_msg_id
• Delivery guarantee: at-least-once with client acks; idempotent storage via client_msg_id
• Group fan-out: fan-out on write for small groups; for large channels, fan-out on read (clients fetch)
• Presence: heartbeat every ~30 s; publish changes only to interested contacts to avoid storms
• E2E encryption: Signal protocol means server stores ciphertext only

Scaling

• Partition messages by conversation_id
• Scale gateways horizontally; route via the session registry
• Rate limit sends; batch receipts
• Multi-region with users homed to a region

Comparison / Tradeoffs

Summary

Precompute feeds by fanning out new posts to followers' timelines in a cache (fan-out on write) for normal users, merge posts from celebrities at read time (fan-out on read), and rank the merged candidates before returning a paginated feed.

Requirements

• Users post content and follow others
• Home feed of followed users' posts, newest or ranked
• Feed loads fast (< 200 ms)
• Scale: 300M daily users, some accounts with 100M followers

Back-of-the-envelope

• Feed reads ≫ posts (~100:1)
• Fan-out on write for an average 200 followers is cheap; for 100M followers it's not

API

POST /api/posts                 {"text": "...", "media_ids": [...]}
GET  /api/feed?cursor=<opaque>&limit=20
POST /api/users/{id}/follow

Data Model

posts(post_id PK, author_id, body, media, created_at)          -- sharded by post_id
follows(follower_id, followee_id, created_at)                   -- both directions indexed
timeline cache: Redis list feed:{user_id} → [post_id, ...] (capped ~800)

Architecture

The post service writes posts and emits an event. Fan-out workers read the author's followers and push post IDs into each follower's timeline cache (skipping inactive users). At read time the feed service loads the cached IDs, merges recent posts from followed celebrities, hydrates posts and authors from caches, applies ranking, and returns a cursor page.

Deep Dives

• Hybrid fan-out: push for accounts below a follower threshold, pull for celebrities
• Ranking: candidate generation then a scoring model (engagement prediction, recency, diversity)
• Pagination: cursors based on post IDs/scores, not offsets
• Deletes/privacy: filter at hydration time so deleted or blocked content never shows

Scaling

• Shard timelines by user_id
• Only maintain timelines for active users; rebuild on demand
• Media via CDN
• Hydration via batched multi-get from caches

Comparison / Tradeoffs

Summary

Services publish notification requests to a queue; a notification service applies user preferences, templates, deduplication and rate limits, then routes to per-channel workers that call providers (SES, Twilio, APNs/FCM) with retries, recording delivery status.

Requirements

• Send email, SMS, push and in-app notifications
• Respect user preferences and quiet hours
• Templates and localization
• Retries, no duplicates, delivery tracking
• Handle spikes (marketing blasts) without delaying transactional messages

API

POST /api/notifications {"user_id": 42, "type": "order_shipped", "data": {...}, "idempotency_key": "..."}
GET  /api/users/{id}/notifications?unread=true          -- in-app inbox
PUT  /api/users/{id}/notification-preferences

Data Model

notification_requests(id, idempotency_key UNIQUE, user_id, type, payload jsonb, created_at)
deliveries(id, request_id, channel, status, provider_id, attempts, last_error, updated_at)
preferences(user_id, type, channel, enabled, quiet_hours)
device_tokens(user_id, platform, token, last_seen)

Architecture

Producers → API/queue → notification service (validate, dedupe by idempotency key, load preferences, render templates) → per-channel queues with priority (transactional vs bulk) → channel workers calling providers → delivery status updates via provider webhooks. In-app notifications are written to an inbox table and pushed over WebSockets.

Deep Dives

• Priority isolation: separate queues/workers for transactional and marketing traffic
• Retries: exponential backoff; switch providers on sustained failures
• Dedup: idempotency keys and per-user/type rate limits (no 10 identical pushes)
• Token hygiene: remove invalid device tokens reported by APNs/FCM
• Compliance: unsubscribe links, opt-outs, data retention

Scaling

• Horizontal channel workers driven by queue depth
• Batch provider calls where supported
• Throttle to provider rate limits

Comparison / Tradeoffs

Summary

Accept payment intents with idempotency keys, orchestrate charges through payment providers with a state machine, record every money movement in a double-entry ledger, process provider webhooks reliably, and reconcile daily against provider reports.

Requirements

• Charge customers, refunds, payouts to merchants
• No double charges, no lost payments
• Auditability and reconciliation
• PCI-DSS compliance; high correctness over raw throughput

API

POST /api/payments   Idempotency-Key: <uuid>
     {"amount": 4999, "currency": "USD", "customer_id": "c1", "payment_method": "pm_..."}
→ 201 {"id": "pay_123", "status": "processing"}
POST /api/payments/{id}/refunds  {"amount": 1000}
POST /webhooks/provider          (signed)

Data Model

payments(id, idempotency_key UNIQUE, amount_minor bigint, currency, status, provider_ref, created_at)
payment_events(id, payment_id, from_status, to_status, data, created_at)   -- append-only
ledger_entries(id, txn_id, account_id, amount_minor, direction /* debit|credit */, created_at)
-- invariant: sum(debits) = sum(credits) per txn_id

Architecture

The payment API stores the intent with its idempotency key in one transaction, then the payment orchestrator calls the provider (tokenized card data only, via provider SDKs, so card numbers never touch your servers). State transitions are persisted and published via an outbox. Provider webhooks are verified, deduplicated and applied to the state machine. A ledger service records double-entry transactions; a reconciliation job compares ledger, payments and provider settlement files.

Deep Dives

• Idempotency: replaying a request with the same key returns the original result
• Unknown outcomes: on timeouts, query the provider by your reference before retrying
• Money types: integers in minor units with currency, never floats
• State machine: created → processing → succeeded/failed → refunded (partial)
• Security: tokenization keeps you in a lighter PCI scope

Scaling

• Correctness first: strongly consistent relational DB
• Partition by merchant for large scale
• Async processing for payouts and reconciliation

Comparison / Tradeoffs

Summary

Hold seats with short-lived reservations (atomic seat-state transitions or Redis locks with TTL), complete payment within the hold window, and protect hot on-sales with a virtual waiting room that admits users at a controlled rate.

Requirements

• Browse events and seat maps
• Reserve specific seats; no double booking
• Payment within a hold window (e.g., 10 min)
• Huge spikes for popular events

API

GET  /api/events/{id}/seats            → seat map with availability
POST /api/events/{id}/holds  {"seat_ids": ["A1","A2"]} → {hold_id, expires_at}
POST /api/holds/{id}/purchase  Idempotency-Key: ...

Data Model

seats(event_id, seat_id, status /* available|held|sold */, hold_id, hold_expires_at, version,
      PRIMARY KEY (event_id, seat_id))
holds(id, user_id, event_id, expires_at, status)
orders(id, hold_id UNIQUE, user_id, total_minor, status)

Architecture

A waiting room service issues signed admission tokens at a controlled rate. Admitted users load cached seat maps (refreshed frequently) and request holds; the booking service atomically transitions seats from available to held with a conditional update (WHERE status='available') for all requested seats in one transaction. Payment completes the purchase; a sweeper or TTL releases expired holds.

Deep Dives

• Double booking: conditional updates or optimistic locking per seat
• Waiting room: queue position, fairness, bot protection
• Seat map reads: cached and pushed via SSE; holds are the source of truth
• General admission: decrement a counter instead of seats

Scaling

• Partition by event
• Cache event and seat-map reads heavily
• Throttle writes via admission control

Comparison / Tradeoffs

Summary

Generate 64-bit, roughly time-ordered IDs without coordination using the Snowflake layout (timestamp + machine ID + per-millisecond sequence), assigning machine IDs at startup and handling clock drift.

Requirements

• Unique across many nodes
• Roughly sortable by time
• High throughput (100K+/s per node), low latency
• 64-bit for DB friendliness

API

next_id() → 1849204391029383168

Data Model

bits: 1 unused | 41 ms timestamp (custom epoch, ~69 years) | 10 machine id | 12 sequence (4096/ms)

Architecture

Each service instance (or an ID service) gets a machine ID from configuration, a coordinator (ZooKeeper/etcd lease) or a database row. IDs are generated in process: the current milliseconds since a custom epoch, the machine ID, and a sequence that resets each millisecond; if the sequence overflows, wait for the next millisecond.

Deep Dives

• Clock moving backwards: refuse or wait until the clock catches up; monitor NTP
• Alternatives: UUIDv7 (128-bit, time-ordered, no coordination), DB sequences with range allocation, ULID
• Predictability: sequential IDs leak volume; don't use as secrets

Scaling

• No coordination per ID; scales linearly
• 1,024 machine IDs per layout; adjust bits as needed

Comparison / Tradeoffs

Summary

Record events durably, enqueue one delivery per subscribed endpoint, send signed HTTP requests from workers with timeouts, retry failures with exponential backoff over hours/days, and isolate slow endpoints so they don't delay others.

Requirements

• Customers register endpoints for event types
• At-least-once delivery with retries
• Signature verification, replay protection
• Visibility: delivery logs, manual redelivery

API

POST /api/webhook-endpoints {"url": "https://customer/hook", "events": ["order.paid"]}
# Outbound
POST https://customer/hook  Webhook-Id: evt_1  Webhook-Timestamp: ...  Webhook-Signature: v1,...

Data Model

endpoints(id, customer_id, url, secret, events text[], status)
events(id, type, payload, created_at)
deliveries(id, event_id, endpoint_id, status, attempts, next_attempt_at, last_status_code)

Architecture

Domain services publish events via an outbox. A dispatcher fans out deliveries per matching endpoint into a queue partitioned by endpoint. Workers send requests (HMAC signature with timestamp), record results, and schedule retries. Endpoints failing continuously are disabled and the customer notified.

Deep Dives

• Isolation: per-endpoint concurrency limits so one slow customer doesn't block others
• Security: HMAC signatures, timestamps to prevent replay, SSRF protection for URLs
• Idempotency: event IDs let receivers dedupe

Scaling

• Partition by endpoint
• Autoscale workers
• Archive old delivery logs

Comparison / Tradeoffs

Summary

Run a central identity provider implementing OpenID Connect: apps redirect users to it (Authorization Code + PKCE), it authenticates (passwords with MFA, social or enterprise IdPs), issues short-lived ID/access tokens and refresh tokens, and maintains a central session for single sign-on and logout.

Requirements

• Login once, access many apps
• MFA, social login, enterprise SAML/OIDC federation
• Token-based API access
• Revocation, audit logs, account recovery

API

GET  /authorize?response_type=code&client_id=...&code_challenge=...&redirect_uri=...
POST /token   (code + code_verifier → access_token, id_token, refresh_token)
GET  /.well-known/openid-configuration    GET /jwks.json
POST /logout

Data Model

users(id, email UNIQUE, password_hash /* argon2id */, mfa_secret, status)
sessions(id, user_id, created_at, last_seen, ip, user_agent)
clients(id, redirect_uris, allowed_scopes)
refresh_tokens(id_hash, user_id, client_id, family_id, expires_at, revoked)

Architecture

Apps delegate login to the IdP; the IdP sets its own session cookie so subsequent app logins are silent. Access tokens are signed JWTs verified by APIs using JWKS; refresh tokens rotate with reuse detection. Brute-force protection, risk-based MFA and audit events are built in. Most teams adopt an existing product (Keycloak, Auth0, Cognito, Entra ID) rather than building one.

Deep Dives

• Token lifetimes: short access tokens (5–15 min), rotating refresh tokens
• Logout: front/back-channel logout, revoke sessions
• Key rotation: multiple keys in JWKS with kid

Scaling

• Stateless token verification at APIs
• Session store replicated (Redis/DB)

Comparison / Tradeoffs