# Design a URL Shortener — System Design Interview Prep

Source: https://www.skillbyai.com/en/system-design-interview/c-short

> IDs, storage and redirects.

## Read-heavy key-value lookups

Requirements: create short codes, redirect quickly, optional custom aliases and expiry. Design: a write service obtains a unique numeric ID (from a range allocator or Snowflake-style generator) and **base62-encodes** it, avoiding collisions without checking; the code-to-URL mapping lives in a key-value store or partitioned relational table; redirects go through a cache and return **301** (cacheable by browsers) or **302** (when every click must be counted). Click analytics are sent asynchronously to a queue.

## Apply the framework

Classic problems combine the building blocks in different ways.

![Three ideas: URL shortener, news feed, web crawler.](assets/figures/system-design-interview/section-6-map.svg) — Figure 6.1 — Shortener, feed and crawler.

## Base62 codes and capacity, run

I ran this with Python 3.12.3 using only the standard library; inputs are fixed or seeded, so the output is reproducible. The 18.25 billion links estimated for five years fit in six characters (jV58GI); seven characters give about 3.5 trillion codes.

```python
# Short codes for a URL shortener: base62-encode a unique numeric ID
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(n):
    s = ""
    while True:
        n, r = divmod(n, 62)
        s = ALPHABET[r] + s
        if n == 0:
            return s

def decode(s):
    n = 0
    for ch in s:
        n = n * 62 + ALPHABET.index(ch)
    return n

for i in (0, 61, 62, 125, 18_250_000_000):
    code = encode(i)
    print(f"{i:>14,} -> {code:8} -> {decode(code):,}")
for length in (6, 7, 8):
    print(f"{length} chars: {62 ** length:,} codes")
```

Output:

```
             0 -> 0        -> 0
            61 -> Z        -> 61
            62 -> 10       -> 62
           125 -> 21       -> 125
18,250,000,000 -> jV58GI   -> 18,250,000,000
6 chars: 56,800,235,584 codes
7 chars: 3,521,614,606,208 codes
8 chars: 218,340,105,584,896 codes
```

## Avoid guessable codes if needed

Sequential IDs give sequential codes; shuffle or encrypt IDs if links must not be enumerable.

**Quiz:** Why prefer 302 over 301 in some shorteners?

- [ ] 301 is not supported by browsers
- [ ] 302 is faster
- [x] Browsers do not cache 302 permanently, so every click reaches the service for analytics
- [ ] 302 needs no server

*Answer:* Browsers do not cache 302 permanently, so every click reaches the service for analytics. Caching versus counting.