Encode and Decode TinyURL — Bidirectional Hashmaps for URL Shorteners

Problem Statement#

Design two methods, encode(longUrl) and decode(shortUrl), so that any URL passed to encode can be recovered exactly by calling decode on the short URL it returned.

Constraints:

• The implementation should be deterministic for a given session.
• Encoded URLs should be short and unique per long URL.
• Both operations must run in O(1) average time.

Input:  encode("https://leetcode.com/problems/design-tinyurl")
Output: "http://tinyurl.com/0"

Input:  decode("http://tinyurl.com/0")
Output: "https://leetcode.com/problems/design-tinyurl"

Why This Problem Matters#

LeetCode 535 sits at the bridge between coding interviews and system design interviews. Google, Amazon, and Microsoft use it as a warm-up before scaling discussions: how would you handle billions of URLs, distributed counters, collision detection, and persistence?

The coding portion is a hash table FAANG classic: two hashmaps, one mapping long-to-short and one mapping short-to-long, plus a monotonic counter or a base62 generator. The discussion that follows is the real interview, not the code.

Strong candidates write the simplest correct implementation in 60 seconds, then talk for the next 20 minutes about scaling, collisions, expiry, and security.

The Core Insight#

A URL shortener needs two operations: insert (long to short) and lookup (short to long). Both are pure dictionary operations, so two hashmaps cover it. To generate unique short codes, use a counter and base62-encode it; this guarantees uniqueness without collision detection.

Visual Dry Run#

Solution (Optimal)#

class Codec:
    def __init__(self):
        self.long_to_short: dict[str, str] = {}
        self.short_to_long: dict[str, str] = {}
        self.counter = 0
        self.alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
        self.base = "http://tinyurl.com/"
 
    def _encode_int(self, n: int) -> str:
        if n == 0:
            return self.alphabet[0]
        chars = []
        while n > 0:
            chars.append(self.alphabet[n % 62])
            n //= 62
        return "".join(reversed(chars))
 
    def encode(self, longUrl: str) -> str:
        if longUrl in self.long_to_short:
            return self.long_to_short[longUrl]
        code = self._encode_int(self.counter)
        self.counter += 1
        short_url = self.base + code
        self.long_to_short[longUrl] = short_url
        self.short_to_long[short_url] = longUrl
        return short_url
 
    def decode(self, shortUrl: str) -> str:
        return self.short_to_long[shortUrl]

const Codec = function() {
    this.longToShort = new Map();
    this.shortToLong = new Map();
    this.counter = 0;
    this.alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    this.base = "http://tinyurl.com/";
};
 
Codec.prototype.encodeInt = function(n) {
    if (n === 0) return this.alphabet[0];
    let chars = "";
    while (n > 0) {
        chars = this.alphabet[n % 62] + chars;
        n = Math.floor(n / 62);
    }
    return chars;
};
 
Codec.prototype.encode = function(longUrl) {
    if (this.longToShort.has(longUrl)) return this.longToShort.get(longUrl);
    const code = this.encodeInt(this.counter++);
    const shortUrl = this.base + code;
    this.longToShort.set(longUrl, shortUrl);
    this.shortToLong.set(shortUrl, longUrl);
    return shortUrl;
};
 
Codec.prototype.decode = function(shortUrl) {
    return this.shortToLong.get(shortUrl);
};

Time: O(1) average for both encode and decode. Space: O(N) where N is the number of unique URLs encoded.

Common Mistakes#

• Using hash(longUrl) and hoping for no collisions; with billions of URLs collisions are inevitable.
• Forgetting to deduplicate: if encode is called twice with the same URL, return the same code.
• Storing only one direction (long-to-short), making decode impossible without scanning.
• Generating random codes without checking uniqueness, leading to silent overwrites.
• Returning bare integers as short URLs, missing the base62 step that keeps codes compact.

Interview Tips#

• Verbalize the trade-off: "Counter-based generation is collision-free; random generation needs collision retries."
• Mention that base62 gives 62^6 ~ 56 billion codes for six characters, which is enough for most services.
• Anticipate the system-design follow-up: distributed counters, sharding, persistence, expiry, and analytics.
• Note that in production you would store mappings in a key-value store like DynamoDB or Redis, not in process memory.

Follow-up Questions#

• How would you handle billions of URLs across multiple servers? Hint: distributed counters with epoch + node-id.
• How would you support expiry of old short URLs? Hint: TTL in the underlying store plus a sweeper.
• How would you handle malicious URLs? Hint: maintain a blocklist and check on encode.
• How would you allow custom aliases? Hint: pre-check uniqueness, fall back to generated code on conflict.
• How would you make decode return a redirect with metrics? Hint: middleware that logs before serving the 301 or 302.

Key Takeaways#

• LeetCode 535 is the gateway from coding to system design at Google, Amazon, and Microsoft.
• Use two hashmaps: long-to-short and short-to-long.
• A counter plus base62 produces unique, compact codes without collision retries.
• Both operations are O(1) average using hashmap lookups.
• Deduplicate identical inputs before generating new codes.
• Real services replace in-memory hashmaps with key-value stores like DynamoDB or Redis.
• The follow-up scaling discussion is where senior signals are demonstrated.