Design URL Shortener (TinyURL) — Hashing and Encoding

Problem Statement#

Design TinyURL with two methods: encode(longUrl) returns a shortened URL; decode(shortUrl) returns the original long URL. The system should handle duplicate long URLs efficiently and produce unique short codes.

Constraints:

• 1 <= longUrl.length <= 10^4
• longUrl is a valid URL
• All encoded short URLs follow the format http://tinyurl.com/<code>
• decode will only receive URLs previously encoded by encode

Input:  encode("https://leetcode.com/problems/design-tinyurl"), decode(shortUrl)
Output: "http://tinyurl.com/f7c9d2", "https://leetcode.com/problems/design-tinyurl"

Input:  encode("https://example.com"), encode("https://example.com")
Output: same short URL (idempotent for duplicate inputs)

Why This Problem Matters#

URL shorteners like Bitly process billions of redirects per day. The encoding strategy—base-62 with a counter vs. random key generation—has direct implications for URL predictability, collision probability, and database storage design. Amazon uses short links internally for product URLs, campaign tracking, and affiliate links.

This problem appears in system design coding rounds because it combines two important concepts: bijective encoding (counter to base-62 string) and bidirectional hashmap lookups. It also opens rich follow-up discussions about scaling to billions of URLs, distributed counters, and preventing enumeration attacks.

Understanding the base-62 encoding algorithm is also foundational to understanding how URL parameters, session tokens, and UUID encoding work in production web services.

The Core Insight#

Two strategies work: counter-based base-62 encoding and random key generation.

Counter-based: Assign incrementing IDs (1, 2, 3...) and encode each as a base-62 string using the 62-character alphabet (a-z, A-Z, 0-9). Six characters can encode up to 62^6 = 56.8 billion unique URLs. Decode by reversing the base-62 decoding. This is deterministic and compact.

Random key: Generate a random 6-character string from the 62-character alphabet. Store in a map. Retry on collision. With 62^6 possible keys and only millions of URLs, collision probability is negligible. This is non-deterministic but prevents URL enumeration.

Both use two hashmaps: url_to_code for idempotent encoding of duplicate long URLs, and code_to_url for O(1) decoding.

Visual Dry Run#

Solution (Optimal)#

import string
 
class Codec:
    CHARS = string.ascii_letters + string.digits  # 62 characters
 
    def __init__(self):
        self.id = 0
        self.url_to_code = {}
        self.code_to_url = {}
 
    def _to_base62(self, n: int) -> str:
        s = []
        while n:
            s.append(self.CHARS[n % 62])
            n //= 62
        return ''.join(reversed(s)) or self.CHARS[0]
 
    def encode(self, longUrl: str) -> str:
        if longUrl not in self.url_to_code:
            self.id += 1
            code = self._to_base62(self.id)
            self.url_to_code[longUrl] = code
            self.code_to_url[code] = longUrl
        return "http://tinyurl.com/" + self.url_to_code[longUrl]
 
    def decode(self, shortUrl: str) -> str:
        return self.code_to_url[shortUrl.split("/")[-1]]

class Codec {
    constructor() {
        this.store = new Map();
        this.reverse = new Map();
        this.id = 0;
    }
 
    encode(longUrl) {
        if (!this.reverse.has(longUrl)) {
            const key = (this.id++).toString(36);
            this.store.set(key, longUrl);
            this.reverse.set(longUrl, key);
        }
        return "http://tinyurl.com/" + this.reverse.get(longUrl);
    }
 
    decode(shortUrl) {
        return this.store.get(shortUrl.split("/").pop());
    }
}

Time: O(L) for encode and decode where L is URL length (for hashmap key hashing)
Space: O(N * L) — N unique URL entries each with average length L

Common Mistakes#

• Not caching duplicate long URLs—calling encode twice on the same URL should return the same short code (idempotent)
• Returning the code itself rather than the full http://tinyurl.com/<code> URL from encode
• Extracting the key from the short URL: use split("/")[-1] or split("/").pop(), not a fixed substring offset (which breaks on different prefix lengths)
• In the base-62 encoding, not handling n=0—the result is an empty string; return the first character of CHARS as the base case
• Using id = 0 as the first ID causes base-62 encoding to return "" or CHARS[0]—start from 1

Interview Tips#

• Present both approaches (counter + base-62 vs. random key) and their trade-offs before coding
• Mention that the counter approach is predictable (users can enumerate URLs), while random keys prevent this
• For the system design follow-up, discuss distributed counter approaches: use a centralised counter service (Zookeeper), pre-allocate ID ranges to each server, or use UUIDs + hash
• Always mention that decode must be O(1)—this is why you store both url_to_code and code_to_url maps

Follow-up Questions#

• How would you scale to 100M URLs/day across 100 servers? (Pre-allocate ID ranges to each server; counter server like Zookeeper for global ordering)
• How would you prevent URL enumeration attacks? (Use random keys; add authentication to encode; rate-limit decode calls)
• How would you add TTL expiry to short links? (Store expiry timestamp with each entry; background cleanup or lazy deletion on decode)
• How would you handle a custom alias (user-defined short code)? (Check if alias is free; store in the same maps with the alias as the code)
• How would you track click analytics per short URL? (Increment a counter per code on each decode; use a time-series DB for hourly/daily aggregation)

Key Takeaways#

• Counter + base-62 encoding is deterministic and compact: 6 characters encode 56.8 billion unique URLs
• Random key generation prevents enumeration but requires collision detection and retry
• Two hashmaps are required: url_to_code for idempotent encoding, code_to_url for O(1) decoding
• Always cache duplicate long URLs so multiple encode calls return the same short code
• Extract the code from the short URL using split("/")[-1] for robustness against prefix changes
• Handle the base case in base-62 encoding: n=0 should return "0" or the first character, not an empty string
• The distributed scaling challenge is the global unique counter—solved with pre-allocated ID ranges or Zookeeper