System Design Interview Deep Dive

Focus on HOW to design and WHY we make each decision

1. Design a URL Shortener (bit.ly)

This is often the first system design question you'll encounter. It seems simple but tests fundamental concepts: hashing, database design, caching, and scale estimation.

Step 1: Clarify Requirements

Step 2: Back-of-Envelope Estimation

Step 3: High-Level Design

Step 4: Deep Dive - The Core Problem

How do we generate unique short URLs?

This is THE key design decision. There are three main approaches:

MD5(longUrl) = "5d41402abc4b2a76b9719d911017c592"
Take first 7 chars = "5d41402"
Convert to base62 = "aB3x9Kp"

Database auto-increment ID: 123456789
Convert to base62: 123456789 → "8M0kX"

Server 1: IDs 0, 2, 4, 6, 8...     (even numbers)
Server 2: IDs 1, 3, 5, 7, 9...     (odd numbers)

Or use ranges:
Server 1: 0 - 1 billion
Server 2: 1 billion - 2 billion
...

Key Generation Service (KGS):
- Pre-generate millions of unique 7-char keys
- Store in database (used/unused columns)
- API servers request batch of keys from KGS
- Mark keys as used when assigned

Database Schema

CREATE TABLE urls (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_url VARCHAR(7) UNIQUE NOT NULL,
    long_url VARCHAR(2048) NOT NULL,
    user_id BIGINT,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    expires_at TIMESTAMP,
    click_count BIGINT DEFAULT 0,

    INDEX idx_short_url (short_url),  -- For redirect lookups
    INDEX idx_user_id (user_id)       -- For user's URL list
);

Caching Strategy

def redirect(short_url):
    # Try cache first
    long_url = redis.get(short_url)
    if long_url:
        return redirect_301(long_url)

    # Cache miss - hit database
    long_url = db.query("SELECT long_url FROM urls WHERE short_url = ?", short_url)
    if not long_url:
        return 404

    # Populate cache (TTL 24 hours)
    redis.setex(short_url, 86400, long_url)

    # Increment click count async (don't block redirect)
    async_queue.push({"type": "click", "short_url": short_url})

    return redirect_301(long_url)

Final Architecture

2. Design a Rate Limiter

Rate limiting protects services from abuse, ensures fair usage, and prevents cascading failures. This tests your understanding of algorithms and distributed systems.

Step 1: Clarify Requirements

Step 2: Algorithm Deep Dive

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity        # Max tokens
        self.tokens = capacity          # Current tokens
        self.refill_rate = refill_rate  # Tokens per second
        self.last_refill = time.time()

    def allow_request(self):
        self._refill()

        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

    def _refill(self):
        now = time.time()
        elapsed = now - self.last_refill
        tokens_to_add = elapsed * self.refill_rate
        self.tokens = min(self.capacity, self.tokens + tokens_to_add)
        self.last_refill = now

class SlidingWindowLog:
    def __init__(self, window_size, max_requests):
        self.window_size = window_size  # e.g., 60 seconds
        self.max_requests = max_requests
        self.request_log = []  # List of timestamps

    def allow_request(self):
        now = time.time()
        window_start = now - self.window_size

        # Remove old entries outside window
        self.request_log = [ts for ts in self.request_log if ts > window_start]

        if len(self.request_log) < self.max_requests:
            self.request_log.append(now)
            return True
        return False

class SlidingWindowCounter:
    def __init__(self, window_size, max_requests):
        self.window_size = window_size
        self.max_requests = max_requests
        self.current_window_count = 0
        self.previous_window_count = 0
        self.current_window_start = self._get_window_start()

    def allow_request(self):
        now = time.time()
        window_start = self._get_window_start()

        # Roll over to new window if needed
        if window_start != self.current_window_start:
            self.previous_window_count = self.current_window_count
            self.current_window_count = 0
            self.current_window_start = window_start

        # Calculate weighted count
        window_progress = (now - window_start) / self.window_size
        weighted_count = (
            self.previous_window_count * (1 - window_progress) +
            self.current_window_count
        )

        if weighted_count < self.max_requests:
            self.current_window_count += 1
            return True
        return False

Step 3: Distributed Rate Limiting

Solution: Centralized Counter with Redis

# Redis Lua script for atomic rate limiting (Token Bucket)
RATE_LIMIT_SCRIPT = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now

-- Calculate tokens to add
local elapsed = now - last_refill
local tokens_to_add = elapsed * refill_rate
tokens = math.min(capacity, tokens + tokens_to_add)

-- Check if request allowed
if tokens >= requested then
    tokens = tokens - requested
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, 60)  -- TTL for cleanup
    return 1  -- Allowed
else
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, 60)
    return 0  -- Denied
end
"""

def check_rate_limit(user_id, capacity=100, refill_rate=1.67):
    key = f"ratelimit:{user_id}"
    now = time.time()
    result = redis.eval(RATE_LIMIT_SCRIPT, 1, key, capacity, refill_rate, now, 1)
    return result == 1

Response Headers

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1699999260
Retry-After: 30

3. Design Twitter Timeline

The Twitter timeline is a classic example of the "fan-out" problem. This tests understanding of trade-offs between read and write optimization.

Step 1: Understand the Scale

Step 2: The Core Problem - Fan-Out

When user A posts a tweet, how do we show it to all followers?

def get_timeline(user_id):
    # Get who this user follows
    following = db.query("""
        SELECT followed_id FROM follows
        WHERE follower_id = ?
    """, user_id)  # Returns ~200 IDs

    # Get recent tweets from all followed users
    tweets = db.query("""
        SELECT * FROM tweets
        WHERE user_id IN (?, ?, ?, ...)  -- 200 IDs
        ORDER BY created_at DESC
        LIMIT 100
    """, following)

    return tweets

def post_tweet(user_id, content):
    # 1. Save tweet to database
    tweet_id = db.insert("INSERT INTO tweets (user_id, content) VALUES (?, ?)",
                         user_id, content)

    # 2. Async: Push to all followers' timelines
    followers = db.query("SELECT follower_id FROM follows WHERE followed_id = ?", user_id)

    for follower_id in followers:
        # Each user's timeline is a Redis sorted set (score = timestamp)
        redis.zadd(f"timeline:{follower_id}", {tweet_id: timestamp})
        redis.zremrangebyrank(f"timeline:{follower_id}", 0, -801)  # Keep only 800 tweets

def get_timeline(user_id):
    # Just read from cache - O(1)!
    tweet_ids = redis.zrevrange(f"timeline:{user_id}", 0, 100)
    tweets = db.query("SELECT * FROM tweets WHERE id IN (?)", tweet_ids)
    return tweets

def get_timeline(user_id):
    # 1. Get pre-computed timeline from cache
    cached_timeline = redis.zrevrange(f"timeline:{user_id}", 0, 100)

    # 2. Get list of celebrities this user follows
    celebrities = redis.smembers(f"follows_celebrities:{user_id}")

    # 3. Fetch recent tweets from celebrities
    celebrity_tweets = []
    for celeb_id in celebrities:
        tweets = redis.zrevrange(f"user_tweets:{celeb_id}", 0, 10)
        celebrity_tweets.extend(tweets)

    # 4. Merge and sort
    all_tweets = merge_sorted(cached_timeline, celebrity_tweets)
    return all_tweets[:100]

Complete Architecture

4. Design a Chat System (WhatsApp)

Chat systems require real-time delivery, guaranteed message ordering, and offline support. This tests WebSockets, message queuing, and consistency.

Step 1: Requirements

Step 2: Real-Time Communication

Step 3: Message Flow

Message States

enum MessageStatus {
    SENDING,    // Client sent, not yet acknowledged
    SENT,       // Server received and stored
    DELIVERED,  // Recipient's device received
    READ        // Recipient opened conversation
}

Step 4: How to Route Messages

class WebSocketServer:
    def on_connect(self, user_id, connection):
        # Register this user's connection
        redis.hset("connections", user_id, self.server_id)
        self.local_connections[user_id] = connection

    def on_disconnect(self, user_id):
        redis.hdel("connections", user_id)
        del self.local_connections[user_id]

    def send_message(self, from_user, to_user, message):
        # Store message in database
        msg_id = db.insert("""
            INSERT INTO messages (from_user, to_user, content, status)
            VALUES (?, ?, ?, 'sent')
        """, from_user, to_user, message)

        # Publish to Kafka (partitioned by recipient)
        kafka.produce(
            topic="messages",
            key=to_user,  # Partition by recipient
            value={"msg_id": msg_id, "from": from_user, "content": message}
        )

    def consume_messages(self):
        for message in kafka.consume("messages"):
            recipient = message.key
            if recipient in self.local_connections:
                # User is connected to THIS server
                self.local_connections[recipient].send(message.value)
            # If not connected here, another server will handle it

Step 5: Database Schema

-- Messages table (partitioned by time for scaling)
CREATE TABLE messages (
    message_id BIGINT PRIMARY KEY,  -- Snowflake ID (contains timestamp)
    conversation_id BIGINT NOT NULL,
    sender_id BIGINT NOT NULL,
    content TEXT,
    media_url VARCHAR(500),
    status ENUM('sent', 'delivered', 'read'),
    created_at TIMESTAMP,

    INDEX idx_conversation (conversation_id, created_at)
) PARTITION BY RANGE (created_at);

-- Conversations (1:1 and groups)
CREATE TABLE conversations (
    conversation_id BIGINT PRIMARY KEY,
    type ENUM('direct', 'group'),
    created_at TIMESTAMP
);

-- Conversation members
CREATE TABLE conversation_members (
    conversation_id BIGINT,
    user_id BIGINT,
    joined_at TIMESTAMP,
    last_read_message_id BIGINT,  -- For read receipts
    PRIMARY KEY (conversation_id, user_id)
);

-- Option 1: Canonical ID (smaller user_id first)
conversation_id = hash(min(user_a, user_b), max(user_a, user_b))

-- Option 2: Lookup table
SELECT conversation_id FROM conversation_members
WHERE user_id IN (user_a, user_b)
GROUP BY conversation_id
HAVING COUNT(*) = 2;

Step 6: Group Chat

5. Design Uber (Location-Based Matching)

Uber's core challenge is efficiently matching riders with nearby drivers in real-time. This tests geospatial indexing and real-time systems.

Step 1: Core Requirements

Step 2: The Geospatial Problem

import geohash

def find_nearby_drivers(rider_lat, rider_lng, radius_km):
    # 1. Get geohash of rider's location (precision 6 ≈ 1.2km cells)
    rider_hash = geohash.encode(rider_lat, rider_lng, precision=6)  # "dr5ru7"

    # 2. Get neighboring geohash cells (handles edge cases)
    neighbors = geohash.neighbors(rider_hash)  # 8 surrounding cells
    cells_to_search = [rider_hash] + neighbors  # 9 cells total

    # 3. Query drivers in these cells
    drivers = redis.sunion([f"drivers:{cell}" for cell in cells_to_search])

    # 4. Filter by exact distance (geohash is approximate)
    nearby = []
    for driver_id in drivers:
        driver_loc = redis.hget(f"driver:{driver_id}", "location")
        distance = haversine(rider_lat, rider_lng, driver_loc.lat, driver_loc.lng)
        if distance <= radius_km:
            nearby.append((driver_id, distance))

    return sorted(nearby, key=lambda x: x[1])  # Sort by distance

Step 3: Driver Location Updates

def update_driver_location(driver_id, lat, lng, status):
    new_geohash = geohash.encode(lat, lng, precision=6)

    # Get previous location
    prev = redis.hgetall(f"driver:{driver_id}")
    prev_geohash = prev.get("geohash")

    # Update driver's location
    redis.hset(f"driver:{driver_id}", mapping={
        "lat": lat,
        "lng": lng,
        "geohash": new_geohash,
        "status": status,  # available, busy, offline
        "updated_at": time.time()
    })

    # Update geohash index if cell changed
    if prev_geohash != new_geohash:
        if prev_geohash:
            redis.srem(f"drivers:{prev_geohash}", driver_id)
        if status == "available":
            redis.sadd(f"drivers:{new_geohash}", driver_id)

    # Publish for real-time tracking (active rides)
    if driver_has_active_ride(driver_id):
        kafka.produce("driver_locations", key=driver_id, value={
            "lat": lat, "lng": lng, "timestamp": time.time()
        })

Step 4: Ride Matching Flow

Complete Architecture

6. Design YouTube (Video Streaming)

Video streaming involves massive storage, transcoding pipelines, and CDN optimization. The key insight: optimize for the common case (watching videos) over the rare case (uploading).

Step 1: Scale Estimation

Step 2: Video Upload Pipeline

def upload_video(user_id, video_file, metadata):
    # 1. Generate unique video ID
    video_id = generate_snowflake_id()

    # 2. Upload original to blob storage (resumable, chunked)
    original_url = s3.upload(
        bucket="originals",
        key=f"{video_id}/original",
        file=video_file,
        multipart=True  # Support resume on failure
    )

    # 3. Save metadata
    db.insert("""
        INSERT INTO videos (id, user_id, title, description, status)
        VALUES (?, ?, ?, ?, 'processing')
    """, video_id, user_id, metadata.title, metadata.description)

    # 4. Queue transcoding job
    kafka.produce("transcode_jobs", {
        "video_id": video_id,
        "source_url": original_url,
        "resolutions": ["360p", "720p", "1080p", "4k"]
    })

    return video_id  # Client polls for status

Step 3: Video Streaming (Adaptive Bitrate)

# HLS Manifest Example (master.m3u8)
#EXTM3U
#EXT-X-STREAM-INF:BANDWIDTH=800000,RESOLUTION=640x360
360p/playlist.m3u8
#EXT-X-STREAM-INF:BANDWIDTH=2800000,RESOLUTION=1280x720
720p/playlist.m3u8
#EXT-X-STREAM-INF:BANDWIDTH=5000000,RESOLUTION=1920x1080
1080p/playlist.m3u8

# Quality-specific playlist (720p/playlist.m3u8)
#EXTM3U
#EXT-X-TARGETDURATION:10
#EXTINF:10.0,
segment_001.ts
#EXTINF:10.0,
segment_002.ts
...

Step 4: CDN Architecture

7. Design a Notification System

Notification systems must handle multiple channels (push, email, SMS), user preferences, rate limiting, and guaranteed delivery. This tests queue design and third-party integrations.

Step 1: Requirements

Step 2: High-Level Design

Step 3: Notification Flow

def send_notification(user_id, notification_type, data):
    # 1. Get user preferences
    prefs = get_user_preferences(user_id)

    # 2. Check if user wants this type of notification
    if not prefs.allows(notification_type):
        return "suppressed"

    # 3. Rate limit check
    if is_rate_limited(user_id, notification_type):
        return "rate_limited"

    # 4. Get user's devices and contact info
    devices = get_user_devices(user_id)  # For push
    email = get_user_email(user_id)
    phone = get_user_phone(user_id)

    # 5. Determine channels based on preferences
    channels = []
    if prefs.push_enabled and devices:
        channels.append("push")
    if prefs.email_enabled and email:
        channels.append("email")
    if prefs.sms_enabled and phone:
        channels.append("sms")

    # 6. Render notification from template
    notification = render_template(notification_type, data)

    # 7. Queue for each channel
    for channel in channels:
        kafka.produce(f"notifications_{channel}", {
            "notification_id": generate_id(),
            "user_id": user_id,
            "channel": channel,
            "content": notification,
            "created_at": time.time()
        })

User Preferences Schema

CREATE TABLE notification_preferences (
    user_id BIGINT PRIMARY KEY,
    push_enabled BOOLEAN DEFAULT true,
    email_enabled BOOLEAN DEFAULT true,
    sms_enabled BOOLEAN DEFAULT false,

    -- Granular preferences
    marketing_push BOOLEAN DEFAULT false,
    marketing_email BOOLEAN DEFAULT true,
    order_updates_push BOOLEAN DEFAULT true,
    order_updates_email BOOLEAN DEFAULT true,
    order_updates_sms BOOLEAN DEFAULT true,
    social_push BOOLEAN DEFAULT true,
    social_email BOOLEAN DEFAULT false,

    -- Quiet hours
    quiet_hours_start TIME,
    quiet_hours_end TIME,
    timezone VARCHAR(50)
);

Step 4: Handling Failures

class NotificationWorker:
    def process(self, notification):
        try:
            result = self.send(notification)
            self.mark_delivered(notification.id)
            return result
        except TemporaryError as e:
            # Retry with exponential backoff
            retry_count = notification.retry_count + 1
            if retry_count < MAX_RETRIES:
                delay = min(2 ** retry_count, 3600)  # Max 1 hour
                self.schedule_retry(notification, delay)
            else:
                self.move_to_dead_letter_queue(notification)
        except PermanentError as e:
            # Don't retry (invalid token, unsubscribed, etc.)
            self.mark_failed(notification.id, str(e))

            # If push token invalid, remove from user's devices
            if isinstance(e, InvalidTokenError):
                remove_device_token(notification.user_id, notification.token)

Key Takeaways

← Back to Index