Design URL Shortener (TinyURL) — Hashing and Encoding

Problem

Design TinyURL:

encode(longUrl) — return a short URL
decode(shortUrl) — return the original long URL

Key Insight — Two Strategies

Strategy 1 — Counter + Base62: Assign incrementing IDs, encode as base-62 string. Deterministic, compact (log₆₂(n) chars).

Strategy 2 — Random Key: Generate random 6-char alphanumeric key, store in map. Simple, no collision with retry.

Solutions

Python — Base62

import string

class Codec:
    CHARS = string.ascii_letters + string.digits
    def __init__(self):
        self.id = 0
        self.url_to_code = {}
        self.code_to_url = {}

    def _encode_id(self, n):
        s = []
        while n:
            s.append(self.CHARS[n % 62])
            n //= 62
        return ''.join(reversed(s)) or '0'

    def encode(self, longUrl: str) -> str:
        if longUrl not in self.url_to_code:
            self.id += 1
            code = self._encode_id(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]]

Python — Random Key

import random
import string

class Codec:
    def __init__(self):
        self.store = {}

    def encode(self, longUrl):
        chars = string.ascii_letters + string.digits
        while True:
            key = ''.join(random.choices(chars, k=6))
            if key not in self.store:
                self.store[key] = longUrl
                return "http://tinyurl.com/" + key

    def decode(self, shortUrl):
        return self.store[shortUrl.split("/")[-1]]

JavaScript

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

Java

import java.util.*;
public class Codec {
    Map<String, String> store = new HashMap<>();
    int id = 0;
    public String encode(String longUrl) {
        String key = Integer.toString(id++, 36);
        store.put(key, longUrl);
        return "http://tinyurl.com/" + key;
    }
    public String decode(String shortUrl) {
        return store.get(shortUrl.substring(shortUrl.lastIndexOf('/')+1));
    }
}

C++

#include <unordered_map>
#include <string>
using namespace std;
class Solution {
    unordered_map<string,string> store;
    int id = 0;
public:
    string encode(string longUrl) {
        string key = to_string(id++);
        store[key] = longUrl;
        return "http://tinyurl.com/" + key;
    }
    string decode(string shortUrl) {
        return store[shortUrl.substr(shortUrl.rfind('/')+1)];
    }
};

C

/* C: hash table mapping short codes to long URLs, linear probing */