Question Banks
HLD System Design (25 Systems)
25 system design problems with architecture diagrams, trade-offs, and scaling strategies
Systems List
- URL Shortener (TinyURL)
- Twitter / News Feed
- WhatsApp / Chat System
- YouTube / Video Streaming
- Uber / Ride Sharing
- Instagram / Photo Sharing
- Notification System
- Distributed Rate Limiter
- Search Autocomplete / Typeahead
- Distributed Cache (Redis-like)
- Payment System (Stripe-like)
- Google Maps / Navigation
- Dropbox / File Storage & Sync
- Web Crawler
- E-commerce (Amazon-scale)
- Ticket Booking (Concurrency)
- Logging & Monitoring (ELK)
- Content Delivery Network
- Collaborative Editor (Google Docs)
- Distributed Job Scheduler
1. URL Shortener (TinyURL) Full Design
Requirements
Functional:
- Given a long URL, generate a short unique URL
- Redirect short URL → original URL
- Custom short links (optional)
- Link expiration (configurable TTL)
- Analytics: click count, geographic data
Non-Functional:
- Highly available (read-heavy system)
- Low latency redirection (< 100ms)
- Short URLs should not be predictable (security)
Back-of-Envelope Estimation
Write: 100M new URLs/month = ~40 URLs/sec
Read:Write ratio = 100:1 → 4000 reads/sec
Storage: 100M × 12 months × 5 years = 6B records
Each record ~500 bytes → 6B × 500B = 3TB
Cache: 20% of daily reads → ~170GB (fits in memory cluster)API Design
POST /api/v1/shorten
Body: { "long_url": "https://...", "custom_alias": "my-link", "expires_at": "2025-12-31" }
Response: { "short_url": "https://tiny.url/abc123", "expires_at": "..." }
GET /:shortCode
Response: 301 Redirect (permanent) or 302 (temporary, better for analytics)
Header: Location: https://original-long-url.com
GET /api/v1/stats/:shortCode
Response: { "clicks": 15420, "created_at": "...", "top_countries": [...] }Database Schema
urls table:
┌─────────────┬──────────────────────────────────────────┐
│ short_code │ VARCHAR(7) PRIMARY KEY │
│ long_url │ TEXT NOT NULL │
│ user_id │ BIGINT (nullable) │
│ created_at │ TIMESTAMP │
│ expires_at │ TIMESTAMP (nullable) │
│ click_count │ BIGINT DEFAULT 0 │
└─────────────┴──────────────────────────────────────────┘
Index: idx_long_url (long_url) for deduplication lookupEncoding Algorithm: Base62
Characters: [a-z, A-Z, 0-9] = 62 chars
7 chars → 62^7 = 3.5 trillion unique URLs
Approach 1: Counter-based (distributed counter via ZooKeeper ranges)
Approach 2: MD5/SHA256 hash → take first 7 chars of base62 encoding
Approach 3: Pre-generate keys (Key Generation Service - KGS)
KGS approach (recommended):
- Pre-generate all 7-char keys, store in DB
- Two tables: unused_keys, used_keys
- App server fetches batch (e.g., 1000 keys) into memory
- No collision, no coordination neededHigh-Level Architecture
┌──────────┐ ┌──────────────┐ ┌──────────┐
│ Client │────▶│ Load Balancer│────▶│ App Server│
└──────────┘ └──────────────┘ └─────┬────┘
│
┌─────────────────────┼─────────────────┐
▼ ▼ ▼
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ Cache (Redis)│ │ Database │ │ KGS │
│ (read path) │ │ (write path) │ │(Key Gen Svc) │
└──────────────┘ └──────────────┘ └──────────────┘
Read Path: Client → LB → App → Cache (hit?) → DB (miss) → 301 Redirect
Write Path: Client → LB → App → KGS (get key) → DB (store mapping)Scaling Considerations
- Cache: Redis cluster for hot URLs. Cache eviction: LRU. Hit ratio expected ~80%
- Database: Partition by first char of short_code (range-based sharding)
- Read replicas: Read-heavy → multiple read replicas behind LB
- CDN: For extremely popular URLs, CDN can cache 301 redirects
- Rate limiting: Prevent abuse on write endpoint
Interviewer Evaluation Points
- Does candidate discuss collision handling in hash-based approach?
- 301 vs 302: trade-off between caching and analytics
- How to handle expired URLs (lazy deletion vs cron job)
- Custom alias: race condition on uniqueness check
2. Twitter News Feed Full Design
Requirements
Functional:
- Post tweets (text, images, video links)
- Follow/unfollow users
- News feed: personalized timeline from followed users
- Like, retweet, reply
Non-Functional:
- News feed generation < 200ms
- Eventual consistency acceptable for feed
- Handle celebrity accounts (millions of followers)
Back-of-Envelope Estimation
DAU: 300M users
Tweets/day: 500M
Avg follows: 200
Feed reads: 300M × 5 reads/day = 1.5B reads/day = 17K reads/sec
Tweet writes: 500M/day = 6K writes/secAPI Design
POST /api/v1/tweet
Body: { "content": "Hello world", "media_ids": [...] }
GET /api/v1/feed?page_token=xxx&limit=20
Response: { "tweets": [...], "next_page_token": "..." }
POST /api/v1/follow
Body: { "followee_id": 12345 }Fan-out Strategies
Fan-out-on-WRITE (Push model):
- When user tweets, push to ALL followers' feed caches
- Pro: Feed read is O(1) just read pre-built cache
- Con: Celebrity with 50M followers → 50M writes per tweet (slow)
Fan-out-on-READ (Pull model):
- When user requests feed, fetch latest from each followee
- Pro: No write amplification
- Con: Slow feed generation (merge K sorted lists at read time)
HYBRID (Twitter's actual approach):
- Normal users (<10K followers): fan-out-on-write
- Celebrities (>10K followers): fan-out-on-read
- Feed = pre-built cache + real-time merge of celebrity tweetsHigh-Level Architecture
┌──────────┐ ┌─────────────┐ ┌──────────────────┐
│ Client │────▶│ API Gateway │────▶│ Tweet Service │
└──────────┘ └─────────────┘ │ (write to DB + │
│ fan-out queue) │
└────────┬─────────┘
│
┌──────────────────────┼────────────────┐
▼ ▼ ▼
┌────────────────┐ ┌─────────────────┐ ┌──────────┐
│ Fan-out Service│ │ Tweet Store │ │ Graph │
│ (push to feed │ │ (tweets table) │ │ Service │
│ caches) │ └─────────────────┘ │(follows) │
└───────┬────────┘ └──────────┘
▼
┌────────────────┐
│ Feed Cache │
│ (Redis sorted │
│ sets per user)│
└────────────────┘
Feed Read Path:
Client → API → Feed Service → Redis (pre-built feed) + Celebrity tweets mergeDatabase Schema
tweets: (tweet_id PK, user_id, content, media_urls, created_at)
users: (user_id PK, username, follower_count, is_celebrity)
follows: (follower_id, followee_id, created_at) indexed both ways
feed_cache: Redis Sorted Set per user_id, score=timestamp, value=tweet_idScaling Considerations
- Celebrity problem: Hybrid fan-out avoids write storms
- Feed cache: Only store last 800 tweet IDs per user (Redis sorted set with ZREMRANGEBYRANK)
- Sharding: Tweets by user_id, feed cache by user_id
- Ranking: ML model scores tweets for relevance (not just chronological)
Interviewer Evaluation Points
- Fan-out trade-off discussion (push vs pull vs hybrid)
- How to handle user unfollowing (remove from feed cache?)
- Thundering herd on celebrity tweet
- Feed pagination: cursor-based vs offset-based
3. WhatsApp Chat System Full Design
Requirements
Functional:
- 1:1 messaging and group messaging (up to 256 members)
- Message delivery statuses: sent, delivered, read
- Online/offline presence indicators
- Media sharing (images, video, documents)
- End-to-end encryption
Non-Functional:
- Real-time delivery (< 100ms for online users)
- At-least-once delivery guarantee
- Support 2B+ users, 100B messages/day
- Message ordering within a conversation
Back-of-Envelope Estimation
Users: 2B total, 500M DAU
Messages: 100B/day = 1.15M messages/sec
Avg message size: 100 bytes text → 10TB/day text
Media: 20% messages have media, avg 200KB → 4PB/day
WebSocket connections: 500M concurrentAPI Design
WebSocket Connection:
ws://chat.app/ws?token=jwt_token
Send Message:
{ "type": "message", "to": "user_id", "content": "hello", "msg_id": "uuid" }
Delivery Ack:
{ "type": "ack", "msg_id": "uuid", "status": "delivered" }
Presence Update:
{ "type": "presence", "status": "online", "last_seen": "2024-01-01T..." }
REST (offline/fallback):
GET /api/v1/messages?conversation_id=xxx&since=timestamp
POST /api/v1/messages (for offline queue)High-Level Architecture
┌──────────┐ ┌─────────────┐ ┌──────────────────────────┐
│ Client │◀───▶│ WebSocket │◀───▶│ Chat Service │
│ (App) │ │ Gateway │ │ (routing + delivery) │
└──────────┘ └─────────────┘ └────────────┬─────────────┘
│
┌───────────────────────────────────┼──────────────────┐
▼ ▼ ▼ ▼
┌──────────────┐ ┌──────────────┐ ┌──────────────┐ ┌────────────┐
│ Session Store│ │ Message Queue│ │ Message DB │ │ Presence │
│ (userId→ │ │ (Kafka for │ │ (Cassandra/ │ │ Service │
│ serverId) │ │ offline) │ │ HBase) │ │ (Redis) │
└──────────────┘ └──────────────┘ └──────────────┘ └────────────┘
Message Flow:
1. User A sends msg via WebSocket to their connected gateway
2. Chat Service looks up User B's gateway in Session Store
3. If B online: route directly to B's WebSocket gateway
4. If B offline: store in Message Queue + DB, deliver on reconnectMessage Delivery Guarantees
Sent (✓): Server received and persisted message
Delivered (✓✓): Recipient's device received the message
Read (✓✓ blue): Recipient opened the conversation
Implementation:
- Client generates msg_id (UUID) for idempotency
- Server ACKs with "sent" status
- Recipient device sends "delivered" ACK back through WebSocket
- "Read" ACK sent when user opens chat
- Retries: client retries if no ACK within timeout (exponential backoff)Group Messaging
- Group members stored in DB with group_id
- On group message: fan-out to all member WebSocket connections
- Optimization: only fan-out to online members, offline get from queue
- Ordering: server assigns monotonic sequence number per group
- Large groups: shard delivery across multiple workersScaling Considerations
- WebSocket servers: 500M connections / 1M per server = 500 servers minimum
- Session routing: Consistent hashing for user→server mapping in Redis
- Message storage: Cassandra (write-heavy, partition by conversation_id)
- E2E encryption: Signal Protocol (Double Ratchet). Server never sees plaintext
- Presence: Heartbeat-based. Batch presence updates to reduce fan-out
Interviewer Evaluation Points
- WebSocket vs long polling vs SSE: trade-offs
- How to handle network partitions (message ordering)
- Group message fan-out efficiency
- End-to-end encryption key exchange mechanism
4. YouTube Video Streaming Full Design
Requirements
Functional:
- Upload videos (support multiple formats)
- Stream videos with adaptive bitrate
- Search and discover videos
- Like, comment, subscribe
- View count and recommendations
Non-Functional:
- Smooth playback (buffer < 200ms at start)
- Support 1B+ DAU
- Global delivery via CDN
- Upload processing within minutes
Back-of-Envelope Estimation
DAU: 1B users watching avg 5 videos/day = 5B video views/day
Uploads: 500 hours of video uploaded per minute
Storage: 500hrs × 60min × 5 resolutions × 3Mbps = ~56TB/day new content
Bandwidth: 5B views × 10 min avg × 4Mbps = 2.5 Exabytes/day outbound
CDN: Must serve from edge locations close to usersAPI Design
POST /api/v1/videos/upload
Headers: Content-Type: multipart/form-data
Body: video file + metadata (title, description, tags)
Response: { "video_id": "abc", "status": "processing" }
GET /api/v1/videos/:id/manifest
Response: HLS/DASH manifest with multiple quality levels
GET /api/v1/videos/:id/stream?quality=720p&segment=5
Response: Video segment (served from CDN)
GET /api/v1/feed/recommendations?user_id=xxx
Response: { "videos": [...] }High-Level Architecture
UPLOAD PATH:
┌────────┐ ┌───────────┐ ┌────────────────┐ ┌──────────────┐
│ Client │───▶│ Upload │───▶│ Message Queue │───▶│ Transcoding │
│ │ │ Service │ │ (processing │ │ Workers │
└────────┘ └───────────┘ │ pipeline) │ │ (720p,1080p, │
└────────────────┘ │ 480p,360p) │
└──────┬───────┘
▼
┌──────────────┐
│ Object Store │
│ (S3/GCS) │
└──────┬───────┘
▼
┌──────────────┐
│ CDN │
└──────────────┘
STREAMING PATH:
┌────────┐ ┌──────────┐ ┌──────────────┐
│ Client │───▶│ CDN │───▶│ Origin Store │
│(player)│ │ (Edge) │ │ (cache miss) │
└────────┘ └──────────┘ └──────────────┘
METADATA PATH:
┌────────┐ ┌────────────┐ ┌─────────────────┐
│ Client │───▶│ API Server │───▶│ Video Metadata │
└────────┘ └────────────┘ │ DB (MySQL shard) │
└─────────────────┘Upload Pipeline (Transcoding)
1. Client uploads raw video → Upload Service → Object Store (raw)
2. Upload Service publishes event to Message Queue
3. Transcoding workers:
- Split video into segments (10s each)
- Encode each segment into multiple resolutions: 360p, 480p, 720p, 1080p, 4K
- Generate thumbnails at key frames
- Create HLS/DASH manifest file
4. Store processed segments in Object Store
5. Push to CDN for edge caching
6. Update video metadata: status = "ready"View Counting at Scale
Challenge: 5B views/day = 58K writes/sec (too much for single counter)
Approach:
1. Batch counting: aggregate views in memory, flush every 30s
2. Use Kafka to decouple: view events → Kafka → counter service
3. Redis INCR for real-time approximate count
4. Periodic reconciliation with DB for accurate count
5. Deduplication: per-user cooldown (don't count rapid refreshes)Scaling Considerations
- CDN: Cache popular videos at edge. Long-tail videos served from origin
- Adaptive bitrate: Client switches quality based on bandwidth (HLS/DASH protocol)
- Transcoding: Parallelized per segment. Spot instances for cost optimization
- Storage tiering: Hot (SSD) → Warm (HDD) → Cold (Glacier) based on view frequency
- Recommendations: Collaborative filtering + content-based, served from ML model
Interviewer Evaluation Points
- Upload pipeline: async processing, failure handling, resumable uploads
- CDN cache invalidation strategy
- Copyright detection (Content ID system)
- View count consistency vs availability trade-off
5. Uber Ride Sharing Full Design
Requirements
Functional:
- Riders request rides with pickup and dropoff locations
- Match riders with nearby available drivers
- Real-time driver location tracking
- ETA calculation
- Dynamic/surge pricing
- Trip history and payments
Non-Functional:
- Match within 10 seconds
- Location updates every 3-5 seconds from drivers
- Support millions of concurrent drivers
- High availability in all regions
Back-of-Envelope Estimation
Active drivers: 5M concurrent (sending location every 4s)
Location updates: 5M / 4s = 1.25M writes/sec
Ride requests: 20M trips/day = 230 requests/sec (peak: 5x = 1150/sec)
Storage per location update: ~50 bytes (lat, lng, timestamp, driver_id)
Daily location data: 1.25M × 86400 × 50B = 5.4TB/dayAPI Design
POST /api/v1/rides/request
Body: { "pickup": {"lat": 37.7, "lng": -122.4}, "dropoff": {"lat": 37.8, "lng": -122.3}, "ride_type": "uberX" }
Response: { "ride_id": "uuid", "estimated_fare": 25.50, "eta_minutes": 4 }
PUT /api/v1/drivers/:id/location
Body: { "lat": 37.7749, "lng": -122.4194, "heading": 90, "speed": 30 }
GET /api/v1/rides/:id/track
Response: { "driver_location": {"lat":..., "lng":...}, "eta_minutes": 3, "status": "en_route" }
WebSocket: /ws/ride/:ride_id (real-time updates for rider)
WebSocket: /ws/driver/:driver_id (new ride requests for driver)Geospatial Indexing
Challenge: Find nearest K drivers to a given point efficiently
Option 1: QuadTree
- Recursively divide space into 4 quadrants
- Each leaf holds ≤ N drivers
- Search: traverse from root, check neighboring cells
- Dynamic: need to rebalance as drivers move
Option 2: Geohash
- Encode lat/lng into string (e.g., "9q8yy")
- Nearby points share common prefixes
- Use Redis with geohash keys for fast lookup
- Limitation: boundary issues (adjacent cells have different prefixes)
Option 3: H3 (Uber's choice)
- Hexagonal hierarchical spatial index
- Consistent neighbors (no edge/corner issues)
- Resolution levels: city → block → street
- Used for: driver matching, surge pricing zones, ETA calculation
Implementation with Redis:
GEOADD drivers lng lat driver_id
GEORADIUS drivers lng lat 5 km COUNT 20 ASCHigh-Level Architecture
┌──────────┐ ┌─────────────┐ ┌─────────────────┐
│ Rider │─────▶│ API Gateway │─────▶│ Trip Service │
│ App │ │ + LB │ │ (ride lifecycle)│
└──────────┘ └─────────────┘ └────────┬────────┘
│
┌──────────┐ ┌─────────────┐ │
│ Driver │─────▶│ Location │ │
│ App │ │ Service │ │
└──────────┘ └──────┬──────┘ │
▼ ▼
┌──────────────────┐ ┌──────────────────┐
│ Geospatial Index │ │ Matching Service │
│ (Redis/H3 cells) │◀──▶│ (find drivers, │
└──────────────────┘ │ assign rides) │
└────────┬─────────┘
│
┌──────────────────────────┼──────────────────┐
▼ ▼ ▼
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ ETA Service │ │ Pricing Svc │ │ Payment │
│ (route calc) │ │ (surge algo) │ │ Service │
└──────────────┘ └──────────────┘ └──────────────┘Matching Algorithm
1. Rider requests ride → Trip Service
2. Query geospatial index: find drivers within 5km radius
3. Filter: available, correct vehicle type, heading towards rider
4. Rank candidates by:
- Distance (primary)
- ETA (considering traffic, not just straight-line)
- Driver rating
- Acceptance rate
5. Send request to top driver → wait 15s for acceptance
6. If rejected/timeout → try next driver
7. If matched → transition ride to "DRIVER_EN_ROUTE"Surge Pricing
Trigger: demand/supply ratio per H3 cell (hexagonal zone)
- If ratio > threshold → apply multiplier (1.2x - 3.0x)
- Calculated every 2 minutes per zone
- Smoothing: gradual increase/decrease to avoid oscillation
- Display to rider before confirming (transparency)
Factors:
- Number of ride requests in zone (demand)
- Number of available drivers in zone (supply)
- Historical patterns (events, weather, time of day)
- Queue depth (pending unmatched requests)Scaling Considerations
- Location ingestion: Kafka for 1.25M writes/sec, partitioned by city
- Geospatial: Sharded by city/region. Each city fits in single Redis cluster
- ETA: Pre-computed road graph + real-time traffic overlay. Dijkstra with traffic weights
- Consistency: Ride assignment must be strongly consistent (avoid double-booking driver)
- Regional deployment: Each city/country has local infrastructure for latency
Interviewer Evaluation Points
- Geospatial index choice and trade-offs (QuadTree vs Geohash vs H3)
- Real-time location at scale (1M+ updates/sec)
- Matching algorithm fairness and efficiency
- Surge pricing: economic model + technical implementation
- Handling driver going offline mid-trip (reassignment)
6. Instagram / Photo Sharing Full Design
Requirements
Functional: Upload photos, follow users, news feed, likes/comments, stories (24hr expiry), explore/discover.
Non-Functional: 500M DAU, feed generation <200ms, image upload <5s globally, 99.9% availability.
Estimation
DAU: 500M, 2 uploads/day per active uploader (10% upload) = 100M photos/day
Storage: 100M × 2MB avg = 200TB/day raw (+ thumbnails = 250TB/day)
Feed reads: 500M × 10 feed loads/day = 5B reads/day = 58K reads/sec
Write:Read ratio ≈ 1:50API
POST /api/v1/posts upload photo + caption + tags
GET /api/v1/feed paginated home feed (cursor-based)
GET /api/v1/users/:id profile + posts grid
POST /api/v1/posts/:id/like
GET /api/v1/explore ML-ranked discovery feedArchitecture
Client → CDN (static) + API Gateway → Post Service → Object Store (S3)
→ Feed Service → Feed Cache (Redis)
→ User Service → User DB (MySQL)
→ Media Processing → Thumbnails + CDN push
Fan-out-on-write for normal users, fan-out-on-read for celebrities.Key Components
- Media Processing Pipeline: Resize to 5 sizes, strip EXIF, generate BlurHash placeholder
- Feed Generation: Redis Sorted Set per user (score=timestamp), max 500 posts cached
- Stories: Separate TTL-based storage, Redis with EXPIRE per story
- Explore: Collaborative filtering + engagement signals, served from ML ranking service
Evaluation Points
- Fan-out strategy for feed (push vs pull vs hybrid)
- Image storage tiering (hot/warm/cold)
- Stories TTL implementation without full-table scans
- CDN invalidation when post is deleted
7. Notification System Full Design
Requirements
Functional: Push (mobile), email, SMS, in-app notifications. Priority levels. User preferences (opt-out per channel). Rate limiting per user. Template management.
Non-Functional: 10B notifications/day, <1s delivery for push, exactly-once semantics, graceful degradation.
Estimation
10B/day = 115K notifications/sec
Channels: 60% push, 25% email, 10% in-app, 5% SMS
Peak: 3x average = 350K/sec during eventsArchitecture
Trigger Sources (services) → Notification Service API → Kafka (priority queues)
→ High Priority Queue → Push Worker → APNs / FCM
→ Medium Priority Queue → Email Worker → SES / SendGrid
→ Low Priority Queue → SMS Worker → Twilio
→ In-App Worker → WebSocket / SSE
Cross-cutting: User Preference DB, Template Engine, Rate Limiter, AnalyticsKey Design Decisions
- Priority queues: Separate Kafka topics for P0 (transactional), P1 (engagement), P2 (marketing)
- Deduplication: Idempotency key (user_id + event_type + entity_id) with TTL in Redis
- Rate limiting: Max 5 push/hour per user, batch digest for low-priority
- Retry: Exponential backoff with dead-letter queue after 3 failures
Evaluation Points
- How to handle provider failures (APNs down) without losing notifications
- User timezone-aware delivery (don't wake people at 3am)
- Template versioning and A/B testing
- Analytics pipeline for delivery/open/click rates
8. Distributed Rate Limiter Full Design
Requirements
Functional: Limit requests per client/IP/endpoint. Multiple algorithms (token bucket, sliding window, fixed window). Configurable per route. Return 429 + Retry-After header.
Non-Functional: <1ms latency overhead, works across multiple API servers, eventual consistency acceptable.
API
Internal API (called by gateway middleware):
POST /ratelimit/check
Body: { "client_id": "user-123", "endpoint": "/api/search", "weight": 1 }
Response: { "allowed": true, "remaining": 47, "reset_at": "..." }
OR { "allowed": false, "retry_after_seconds": 30 }Architecture
API Gateway (middleware) → Rate Limit Service → Redis Cluster
→ Config Store (rules per endpoint)
Algorithms in Redis:
- Token Bucket: key=user:endpoint, DECR + EXPIRE
- Sliding Window: Sorted Set with timestamp scores, ZRANGEBYSCORE to count
- Fixed Window: INCR + EXPIRE on window key
Sync: Each API server has local cache (races acceptable for ~1% over-limit)Evaluation Points
- Race condition: two servers both allow the 100th request simultaneously → accept ~1% overage or use Redis Lua scripts for atomicity
- Clock skew in distributed sliding window
- Hierarchical limits: per-user AND per-IP AND global
- Graceful degradation: if Redis is down, fail-open or fail-closed?
9. Search Autocomplete / Typeahead Full Design
Requirements
Functional: Return top 5 suggestions as user types, ranked by popularity. Handle typos (fuzzy). Personalized (recent searches). Real-time trending updates.
Non-Functional: <50ms response, 10B queries/day, handle multiple languages.
Architecture
Client (debounced, after 2 chars) → API Gateway → Suggestion Service
→ Trie/Prefix Store (in-memory)
→ Popularity Aggregator (offline)
→ Personalization Layer (Redis per user)
Data Pipeline:
Search logs → Kafka → Spark aggregation (hourly) → Update Trie snapshots → Deploy to nodesData Structure: Trie with Top-K
Each Trie node stores:
- children: Map<char, TrieNode>
- top5: List<(query, score)> ← precomputed top 5 for this prefix
On query "app":
Traverse: root → 'a' → 'p' → 'p' → return node.top5
Update (offline):
Every hour, rebuild top5 at each node from aggregated query counts
Swap in new Trie atomically (blue-green deployment of data structure)Evaluation Points
- Trie vs inverted index vs prefix hash map trade-offs
- How to handle "trending now" (real-time updates vs batch)
- Multi-language support (CJK tokenization)
- Data freshness vs serving latency (stale reads during rebuild)
10. Distributed Cache (Redis-like) Full Design
Requirements
Functional: GET/SET/DELETE with TTL. Support data types (string, hash, list, set). Pub/Sub. Atomic operations. Eviction policies (LRU, LFU, TTL).
Non-Functional: Sub-millisecond reads, 1M+ ops/sec per node, horizontal scaling, persistence options.
Architecture
Client → Consistent Hashing Router → Cache Node (in-memory hash table)
→ Replication (async to replicas)
→ Persistence: AOF (append-only file) + RDB snapshots
Cluster:
- Consistent hashing with virtual nodes (150 vnodes per physical node)
- Each key maps to a primary + 2 replicas
- Gossip protocol for membership and failure detection
- Client-side routing (smart client) or proxy-based routingKey Design Decisions
- Eviction: LRU approximation (sample 5 random keys, evict least recent)
- Persistence: AOF for durability (fsync every second), RDB for backup
- Cluster rebalancing: Move slots between nodes on add/remove
- Hot key problem: Read replicas + local client-side caching with short TTL
Evaluation Points
- Consistent hashing vs hash slot approach (Redis Cluster uses 16384 slots)
- Cache invalidation strategies (TTL, write-through, write-behind)
- Thundering herd on cache miss (singleflight / request coalescing)
- Split-brain during network partition
11. Payment System (Stripe-like) Full Design
Requirements
Functional: Process payments (credit card, bank transfer). Refunds. Subscription billing. Multi-currency. Webhooks for status updates. Idempotent operations.
Non-Functional: 99.999% availability, exactly-once processing, PCI DSS compliant, <2s processing time.
Architecture
Merchant → API Gateway (TLS + API Key auth) → Payment Service → Payment Router
→ Acquirer/Processor (Visa/MC)
→ Ledger Service (double-entry)
→ Fraud Detection (ML)
→ Webhook Dispatcher
State machine: CREATED → PROCESSING → AUTHORIZED → CAPTURED → SETTLED
→ DECLINED
→ REFUND_REQUESTED → REFUNDEDKey Design Decisions
- Idempotency: Client provides idempotency_key. Server stores result in Redis (24hr TTL). Same key → same response.
- Double-entry ledger: Every transaction creates two entries (debit + credit). Enables reconciliation.
- Retry with PSP: If no response from processor within 30s, query status before retrying (avoid double-charge).
- PCI compliance: Tokenize card data immediately. Core system never sees raw card numbers.
Evaluation Points
- Exactly-once semantics in payment processing
- Handling partial failures (charged but webhook failed)
- Reconciliation between ledger and bank statements
- Multi-currency: when to convert (at charge time vs settlement)
12. Google Maps / Navigation Full Design
Requirements
Functional: Map tile rendering, search places, route calculation (driving/walking/transit), real-time traffic, ETA, turn-by-turn navigation.
Non-Functional: <200ms route calculation, handle 1B+ daily map loads, offline support.
Architecture
Client → CDN (map tiles, pre-rendered) → Map Tile Service
→ API Gateway → Routing Service (Dijkstra/A* on road graph)
→ Geocoding Service (address ↔ lat/lng)
→ Places Service (search + details)
→ Traffic Service (real-time road speeds)
→ ETA Service (routing + traffic + ML prediction)
Map Data Pipeline:
Raw map data (OSM) → Processing → Road Graph (adjacency list)
→ Tile Generation (vector tiles at zoom levels 0-22)
→ Search Index (places + addresses)Route Calculation
Graph: Nodes = intersections, Edges = road segments with weights (distance × traffic_factor)
Algorithm: Contraction Hierarchies (preprocessed) + A* for real-time queries
- Precompute shortcuts between important nodes → reduces graph size 1000x
- Real-time: overlay live traffic speeds on edge weights
- Multi-modal: separate graphs for driving, walking, transit (transfers as edges)Evaluation Points
- How to update routing when traffic changes (partial graph refresh vs full recompute)
- Map tile caching strategy (zoom level priority, geographic popularity)
- Offline navigation: download region graph subset to device
- ETA accuracy: ML model trained on historical trip data
13. Dropbox / File Storage & Sync Full Design
Requirements
Functional: Upload/download files, sync across devices, file versioning, sharing (links + permissions), conflict resolution.
Non-Functional: Minimize bandwidth (delta sync), handle 1B+ files, low-latency sync (<5s for small files).
Architecture
Desktop Client (file watcher) → Block Server (chunked upload)
→ Metadata Service → Metadata DB (MySQL)
→ Notification Service (long-poll/WebSocket)
→ Sync Queue → Other connected clients
Storage: File → split into 4MB chunks → deduplicate by content hash → store in S3
Sync: Only upload changed chunks (rsync-like delta sync)Block-Level Deduplication
1. Split file into 4MB blocks
2. Hash each block (SHA-256)
3. Check if hash exists in block store
4. Only upload new/changed blocks
5. File = ordered list of block hashes (manifest)
Result: Uploading a 1GB file with 1 byte changed → upload only 1 block (4MB)Evaluation Points
- Conflict resolution: last-writer-wins vs manual merge vs branching
- Delta sync algorithm (rolling checksum like rsync)
- Notification fan-out to connected devices (not polling)
- Storage cost optimization (dedup ratio, compression, cold storage tiering)
14. Web Crawler Full Design
Requirements
Functional: Crawl 1B web pages, extract content + links, respect robots.txt, handle duplicates, re-crawl on schedule.
Non-Functional: Politeness (don't DDoS sites), 1000 pages/sec throughput, distributed across regions.
Architecture
Seed URLs → URL Frontier (priority queue) → Fetcher Workers (HTTP)
→ DNS Resolver (cached)
→ Content Parser → Link Extractor → URL Frontier (loop)
→ Content Store (S3)
→ Dedup Service (SimHash / fingerprint)
Politeness: Per-domain rate limiter (max 1 req/sec per domain)
Priority: PageRank-based, freshness-based, or breadth-firstKey Components
- URL Frontier: Priority queue (important pages first) + politeness queue (per-host delay)
- Deduplication: URL-level (normalized) + Content-level (SimHash for near-duplicates)
- Robots.txt cache: Fetch and cache per domain, respect Crawl-delay directive
- Re-crawl scheduler: Pages that change often get shorter re-crawl intervals
Evaluation Points
- How to handle spider traps (infinite URLs from dynamic sites)
- Consistent hashing for distributing URLs to crawler instances
- Handling JavaScript-rendered pages (headless browser vs API)
- Incremental crawling (HTTP If-Modified-Since, ETags)
15. E-commerce Platform (Amazon-scale) Full Design
Requirements
Functional: Product catalog, search, cart, checkout, order processing, inventory management, reviews, recommendations.
Non-Functional: Handle flash sales (100x traffic spikes), 99.99% checkout availability, eventual consistency for catalog.
Architecture
Client → CDN (product images) → API Gateway → Microservices:
- Product Service → Product DB (NoSQL) + Search Index (Elasticsearch)
- Cart Service → Redis (session-based cart)
- Order Service → Order DB (MySQL, strong consistency)
- Inventory Service → Redis (real-time stock) + DB (source of truth)
- Payment Service → External PSP
- Recommendation Service → ML model + feature store
Event Bus (Kafka): order.placed → inventory.reserved → payment.charged → shipping.initiatedInventory Management (Flash Sales)
Problem: 10K items, 1M users clicking "Buy" simultaneously
Solution:
1. Pre-warm inventory count in Redis (DECR is atomic)
2. DECR returns remaining. If < 0, item sold out → reject
3. If ≥ 0, place order in queue, process asynchronously
4. Payment failure → INCR to restore inventory
5. Timeout (5 min) → INCR to release reserved item
This avoids DB contention entirely. Redis handles 100K+ DECR/sec.Evaluation Points
- Inventory overselling prevention under concurrency
- Saga pattern for distributed transactions (order → inventory → payment)
- Search: Elasticsearch vs dedicated product search service
- Cart: session-based (Redis) vs persistent (DB) trade-offs
16. Ticket Booking (Concurrency) Full Design
Requirements
Functional: Browse events/shows, select seats, hold temporarily (5 min), checkout, confirmation. Seat map visualization.
Non-Functional: No double-booking (exactly-once seat assignment), handle 100K concurrent bookers for popular events.
Concurrency Solution
Approach: Optimistic Locking + Temporary Hold
1. User selects seat → POST /api/hold { "seat_id": "A-12", "event_id": "..." }
2. Server: SET seat:A-12 user_id EX 300 NX (Redis SET if Not eXists, 5min expiry)
- NX ensures only ONE user can hold a seat
- EX auto-releases if user abandons
3. If SET succeeds → seat held, show checkout page
4. If SET fails → "Seat already taken, pick another"
5. On payment success → UPDATE seats SET status='BOOKED' WHERE id='A-12' AND status='HELD'
6. On timeout → key expires, seat becomes available
Zero race conditions. Redis NX is atomic. No distributed locks needed.Architecture
Client → API Gateway → Booking Service → Redis (seat holds, atomic NX)
→ Seat DB (PostgreSQL, source of truth)
→ Payment Service
→ Notification Service (confirmation email)Evaluation Points
- Why Redis NX beats database row locking for this use case
- Handling payment failure after hold (release seat, retry)
- Waitlist for sold-out events (queue with priority)
- Scalability during on-sale moments (queue + virtual waiting room)
17. Logging & Monitoring System Full Design
Requirements
Functional: Collect logs from 1000+ services, structured search, dashboards, alerting, log retention policies.
Non-Functional: Ingest 1TB logs/day, search latency <2s, 30-day hot retention, 1-year cold archive.
Architecture (ELK-like)
Services (stdout JSON) → Log Agent (Filebeat/Fluentd) → Kafka (buffer)
→ Stream Processor (filter, enrich, parse) → Elasticsearch (indexing)
→ Kibana / Grafana (visualization)
→ Alertmanager (threshold + anomaly detection)
Cold path: Kafka → S3 (Parquet format, partitioned by date + service)
Metrics path (separate):
Services → Prometheus (scrape) → Grafana dashboards → AlertManagerKey Design Decisions
- Kafka as buffer: Decouples producers from indexing speed. Handles burst without data loss.
- Index lifecycle: Hot (SSD, 7 days) → Warm (HDD, 30 days) → Cold (S3, 1 year) → Delete
- Structured logging: Enforce JSON schema at agent level. Reject malformed logs.
- Sampling: Debug logs sampled at 1% in production, 100% for errors.
Evaluation Points
- How to handle log explosion during incidents (backpressure, sampling)
- Correlation IDs for distributed tracing across services
- Alert fatigue prevention (grouping, dedup, escalation policies)
- Cost optimization: what to index vs what to archive raw
18. Content Delivery Network Full Design
Requirements
Functional: Cache and serve static content from edge locations worldwide. Cache invalidation. HTTPS termination. DDoS protection.
Non-Functional: <50ms latency globally, 99.99% cache hit rate for popular content, handle 100Tbps aggregate bandwidth.
Architecture
User → DNS (GeoDNS routes to nearest PoP) → Edge Server (cache check)
→ Cache HIT: serve directly (fastest)
→ Cache MISS: fetch from Origin Shield → Origin Server
(Origin Shield = second-level cache, reduces origin load)
Edge PoPs: 200+ locations worldwide
Each PoP: Nginx/Varnish cache, TLS termination, WAF, load balancers
Origin Shield: Regional caches (5-10 locations) between edge and originCache Invalidation
1. TTL-based: Cache-Control headers (max-age, s-maxage)
2. Purge API: POST /purge { "url": "..." } → fan-out to all PoPs
3. Versioned URLs: style.v3.css (cache forever, new version = new URL)
4. Stale-while-revalidate: Serve stale, refresh in background
5. Tag-based: Surrogate-Key header, purge by tag (e.g., purge all product images)Evaluation Points
- Cache consistency vs performance (aggressive TTL vs real-time purge)
- Hot content vs long-tail distribution (what to cache at edge)
- Origin protection during cache stampede (request coalescing)
- Multi-CDN strategy for resilience
19. Collaborative Editor (Google Docs) Full Design
Requirements
Functional: Real-time collaborative text editing, multiple cursors, conflict resolution, version history, comments, offline support.
Non-Functional: <100ms sync between collaborators, handle 100 simultaneous editors per document, no data loss.
Conflict Resolution: OT vs CRDT
Operational Transformation (OT) Google Docs approach:
- Each edit is an "operation" (insert char at pos 5, delete range 3-7)
- Server transforms concurrent operations against each other
- Guarantees convergence even with concurrent edits
- Complex to implement, requires central server
CRDT (Conflict-free Replicated Data Types) newer approach:
- Each character has a unique ID (fractional indexing)
- Operations are commutative order doesn't matter
- No central server needed (P2P possible)
- Higher memory overhead (IDs per character)Architecture
Client (editor) → WebSocket → Collaboration Service → OT Engine
→ Document Store (versioned)
→ Presence Service (cursors)
→ Pub/Sub (Redis) → Other clients
On edit:
1. Client applies edit locally (optimistic)
2. Sends operation to server via WebSocket
3. Server transforms against any concurrent ops
4. Broadcasts transformed op to all other clients
5. Clients apply received ops (already transformed)Evaluation Points
- OT vs CRDT: trade-offs in complexity, latency, memory
- Undo/redo in collaborative context (local undo vs global undo)
- Offline editing and merge on reconnect
- Rich text: how to represent formatting as operations
20. Distributed Job Scheduler Full Design
Requirements
Functional: Schedule recurring jobs (cron syntax), one-time delayed jobs, job dependencies (DAG), retry on failure, priority queues.
Non-Functional: Exactly-once execution (no duplicate runs), handle 10M scheduled jobs, <1s scheduling accuracy, fault-tolerant.
Architecture
Job Submission API → Job Store (PostgreSQL schedule definitions)
→ Scheduler Service (picks due jobs every second)
→ Job Queue (Redis Sorted Set, score=next_run_timestamp)
→ Worker Pool (execute jobs, report status)
→ Dead Letter Queue (failed after max retries)
Scheduler (leader-elected):
1. Every second: ZRANGEBYSCORE jobs 0 NOW → get due jobs
2. For each due job: ZREM (claim it) → publish to worker queue
3. Worker executes, reports success/failure
4. On success: compute next_run, ZADD back with new timestamp
5. On failure: retry with exponential backoff, DLQ after 3 attemptsExactly-Once Execution
Problem: Two scheduler instances might pick the same job
Solution 1: Leader election (only one scheduler runs at a time)
Solution 2: Redis ZREM is atomic first to ZREM "owns" the job
Solution 3: Database row lock with "CLAIMED" status + TTL
Chosen: ZREM atomicity. If ZREM returns 1 (removed), you own it. If 0, someone else got it.Job Dependencies (DAG)
Jobs can depend on other jobs (like CI pipelines):
Build → Test → Deploy
Implementation:
- Store DAG in job metadata (depends_on: [job_id_1, job_id_2])
- When job completes, check dependents
- If all dependencies met, enqueue dependent
- Cycle detection at submission time (topological sort validation)Evaluation Points
- Exactly-once guarantee across distributed workers
- Time zone handling for cron schedules (DST transitions)
- Starvation prevention (low-priority jobs never run if high-priority queue is full)
- Observability: how to debug a job that silently failed