URL Shortener
medium · hashing / encoding, idempotency, expiry
Brief-reported interview attribution (unverified): a standard LLD question at Amazon, Microsoft, Google (the class-level version, not the distributed system)
How to approach an LLD roundRequirements
- Functional: shorten a URL to a short code, redirect a code, count clicks, support custom aliases and optional expiry.
- Non-functional: codes must be unique (an alias collision is rejected); a repeated shorten of the same URL returns the same code; the code scheme must be replaceable.
- Out of scope: analytics, user accounts, rate limiting, persistence.
Statement
Design the core of a URL shortener as a single class. Short codes are
base62 encodings of a counter starting at 1 (1, 2, …, 9, A, …, Z, a, …,
z, 10, …). Shortening the same URL twice returns the same code. A custom alias
may be requested; a taken alias returns None. A link may have a TTL in seconds;
after it expires, redirect returns None. Time comes from a clock callable
passed to the constructor (default: time.time), so tests can use a fake clock.
class URLShortener:
def __init__(self, clock=None):
# clock: callable returning the current time in seconds
def shorten(self, long_url, custom_alias=None, ttl_seconds=None):
# -> short code (str), or None if the custom alias is taken
def redirect(self, code):
# -> the long URL, or None for an unknown or expired code
def clicks(self, code):
# -> number of successful redirects for the code (0 for an unknown code)Rules. Base62 alphabet is 0-9A-Za-z in that order. The counter starts at 1,
so the first generated code is "1". An expired code may be reused (shortening
the same URL again after expiry creates a fresh code; a custom alias equal to an
expired code is free again). redirect counts a click only on success. Expiry is
checked as now >= created_at + ttl_seconds.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
CodeGenerator (ABC interface) + SequentialCodeGenerator (counter → base62 code; OCP — a hash-based generator swaps in). UrlStore (the code → entry maps and the expiry rule; SRP). URLShortener orchestrates and takes the code generator and the clock as constructor arguments (DIP) — the clock is what makes the tests deterministic. Pattern: Strategy (code generation).
Optional constructor collaborators: clock, code_generator, and store. Inject them to test expiry, code generation, or storage independently.
Public demo
# Public demo: run after implementing the class API above.
now = [1000.0]
u = URLShortener(clock=lambda: now[0])
print(u.shorten('https://example.com/a'))
print(u.redirect('1'))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
Two shortens of the same URL must not create two codes. The lookup-then-insert step must be atomic (one lock on the store, or a unique constraint on the URL). The reference is single-threaded; the lock is described here.
Trade-offs & extensions
A counter plus base62 is simple and collision-free but leaks the count of URLs; a pre-allocated key-generation service (KGS) can issue unique opaque codes; HMAC-based codes obscure the input but truncated outputs still need collision detection and resolution. Extending: a Cache in front of the store, and a ClickAnalytics sink behind an interface.
Starter code
import time
from abc import ABC, abstractmethod
class CodeGenerator(ABC):
@abstractmethod
def generate(self):
"""Implement the return value and rules in the API contract."""
pass
class SequentialCodeGenerator(CodeGenerator):
def __init__(self):
"""clock: callable returning the current time in seconds"""
pass
def generate(self):
"""Implement the return value and rules in the API contract."""
pass
class UrlStore:
def __init__(self):
"""clock: callable returning the current time in seconds"""
pass
def put(self, code, url, alias, expiry):
"""Implement the return value and rules in the API contract."""
pass
def lookup_code(self, url, alias, now):
"""Implement the return value and rules in the API contract."""
pass
def get(self, code):
"""Implement the return value and rules in the API contract."""
pass
def is_live(self, code, now):
"""Implement the return value and rules in the API contract."""
pass
def release(self, code):
"""Implement the return value and rules in the API contract."""
pass
def record_click(self, code, now):
"""Implement the return value and rules in the API contract."""
pass
def clicks(self, code):
"""-> number of successful redirects for the code (0 for an unknown code)"""
pass
class URLShortener:
def __init__(self, clock=None, code_generator=None, store=None):
"""clock: callable returning the current time in seconds"""
pass
def shorten(self, long_url, custom_alias=None, ttl_seconds=None):
"""-> short code (str), or None if the custom alias is taken"""
pass
def redirect(self, code):
"""-> the long URL, or None for an unknown or expired code"""
pass
def clicks(self, code):
"""-> number of successful redirects for the code (0 for an unknown code)"""
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter