URL Shortener Codes (Base62)

URL shorteners map a database ID to a short code like /r/3D7. Implement Base62 encoding with the alphabet

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

encode(id) returns the code for a non-negative integer (encode(0) == "0", encode(61) == "Z", encode(62) == "10").
decode(code) returns the original id.

IDs fit in 53 bits (safe in JavaScript numbers).

Example 1

Input: ["Base62","encode","encode","decode"]
[[],[125],[0],["21"]]
Output: [null,"21","0",125]

Solution and explanation

Show the solution

Time O(log₆₂ id) · Space O(log₆₂ id)

Base conversion: emit id % 62 digits from least to most significant and reverse; decode by multiplying the accumulator by 62 and adding each character's index. Codes stay short — 7 characters cover 62⁷ ≈ 3.5 trillion IDs.

In a system-design follow-up, discuss where IDs come from (database sequence, Snowflake-style IDs, or pre-allocated ranges per server), why sequential codes are guessable (add a bijective shuffle or random IDs), and caching hot redirects.

Reference solution

const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

class Base62 {
  encode(id) {
    if (id === 0) return "0";
    let out = "";
    while (id > 0) {
      out = ALPHABET[id % 62] + out;
      id = Math.floor(id / 62);
    }
    return out;
  }

  decode(code) {
    let id = 0;
    for (const c of code) id = id * 62 + ALPHABET.indexOf(c);
    return id;
  }
}

class Base62 {
  private static readonly ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

  encode(id: number): string {
    let out = "";
    do {
      out = Base62.ALPHABET[id % 62] + out;
      id = Math.floor(id / 62);
    } while (id > 0);
    return out;
  }

  decode(code: string): number {
    return [...code].reduce((acc, c) => acc * 62 + Base62.ALPHABET.indexOf(c), 0);
  }
}

import string

ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase

class Base62:
    def encode(self, id: int) -> str:
        if id == 0:
            return "0"
        digits = []
        while id:
            id, r = divmod(id, 62)
            digits.append(ALPHABET[r])
        return "".join(reversed(digits))

    def decode(self, code: str) -> int:
        value = 0
        for c in code:
            value = value * 62 + ALPHABET.index(c)
        return value

<?php

class Base62
{
    private const ALPHABET = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';

    public function encode(int $id): string
    {
        $out = '';
        do {
            $out = self::ALPHABET[$id % 62] . $out;
            $id = intdiv($id, 62);
        } while ($id > 0);
        return $out;
    }

    public function decode(string $code): int
    {
        $id = 0;
        foreach (str_split($code) as $c) {
            $id = $id * 62 + strpos(self::ALPHABET, $c);
        }
        return $id;
    }
}

class Base62 {
    private static final String ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public Base62() {}

    public String encode(long id) {
        StringBuilder out = new StringBuilder();
        do {
            out.append(ALPHABET.charAt((int) (id % 62)));
            id /= 62;
        } while (id > 0);
        return out.reverse().toString();
    }

    public long decode(String code) {
        long id = 0;
        for (char c : code.toCharArray()) id = id * 62 + ALPHABET.indexOf(c);
        return id;
    }
}

Common mistakes

Returning an empty string for 0.
Floating-point division in JavaScript — use Math.floor (or BigInt beyond 2⁵³).

Follow-up questions

Make codes non-sequential without collisions.
Design the full URL shortener: storage, redirects (301 vs 302), analytics, abuse.

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

More Design & Data Structures problems