URL Shortener

Link Shortening and Redirection Service

Design the classes of a URL shortener: generate unique short codes, accept custom aliases safely, resolve codes with expiry and disabling, and count clicks, with swappable code generation.

Overview

A URL shortener turns a long address into a short code, such as https://sho.rt/1a2B, and sends anyone who opens the short link to the original address. The low-level design question is about the objects inside one service: how codes are made, how two writers are kept from taking the same code, and what happens when a link expires or its owner turns it off. The distributed version (many servers, a database, caches) is a system design question; here it appears only in the follow-ups.

The interviewer listens for: a code generator you can swap (counter or random), one atomic 'insert if absent' that every writer goes through, a clear answer on 301 versus 302, and the arithmetic of how many codes a given length gives you.

Scoping the problem

Must codes be hard to guess? — Counter codes are sequential and guessable — Ask; offer both behind one interface
Custom aliases? — A second way to claim a code; must not race — Yes, validated, reserved words refused
Same URL shortened twice: same code or a new one? — A reverse index, per owner or global — A new code; dedupe is a follow-up
Expiry and disabling? — resolve() needs more than found or not found — Yes: expired or disabled means gone
Analytics? — Writes on the hot read path — A click count per code
Which redirect status? — 301 responses may be cached by browsers — 302 when clicks must be counted

Base62 and how long a code must be

Base62 writes a number with the digits 0-9, a-z and A-Z, which are all safe in a URL path. Each extra character multiplies the number of codes by 62.

6 — 56,800,235,584 (about 57 billion) — Yes, 1.8% used
7 — 3,521,614,606,208 (about 3.5 trillion) — Yes, 0.03% used
8 — about 218 trillion — Yes

A counter code has no collisions at all: number n becomes one code and is never reused. A random 7-character code collides with an existing one with probability (links stored) ÷ 62^7, about 0.03 percent per attempt at 1 billion links, so one retry almost always succeeds. The code retries up to five times and then fails loudly.

Shortening and resolving

Code never existed — NotFound — 404 Not Found
Expired, or disabled by its owner — Gone — 410 Gone
Active — none; returns the URL — 302 Found with a Location header

The demo starts the counter at 3843, which is ZZ, the last two-character code. The next number, 3844, is 1 × 62², so the first code issued is 100.

One atomic insert

Two users can ask for the alias 'launch' in the same instant. If the code checked 'is launch free?' and then wrote, both could pass the check. Instead every writer calls LinkStore.put_if_absent, which checks and inserts under one lock and returns false if the code exists. The generated-code path uses the same call, so a random collision and an alias clash are handled by one mechanism. The demo races 8 threads for one alias (exactly one wins) and 8 threads creating 200 counter codes each (all 1,600 are distinct).

In a database, the same step is a primary key on the code column: the second insert fails with a unique violation.

What you will be able to do

Encode and decode base62 and size the code length with the arithmetic shown.
Put code generation behind an interface and compare counter and random generators.
Route every write through one atomic insert-if-absent, and explain why check-then-write fails.
Map resolve outcomes to 404, 410 and 302, and defend 302 over 301 when clicks are counted.
Validate URLs and aliases, including reserved words.

Functional requirements

shorten(url, owner, now, alias=None, ttl=None) returns a new code; only http and https URLs are accepted
Custom aliases: 3 to 30 characters from letters, digits, dash and underscore; reserved words refused; a taken alias raises AliasTaken
resolve(code, now) returns the URL and counts a click; unknown codes raise NotFound; expired or disabled links raise Gone
disable(code, owner) turns a link off; only its owner may do it
clicks(code) returns the number of successful resolves

Non-functional requirements

No two links ever share a code, even under concurrent writes
resolve is an O(1) dictionary lookup
Code generation is swappable (counter or random) without changing Shortener
Time is injected, so expiry is exact in tests

Interview questions

Counter, random or hash of the URL: which generator would you use?
301 or 302 for the redirect?
How would you generate unique counter codes across many servers?
Suppose redirects far outnumber new links. Where does the time go and what do you change?