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 round

Requirements

  • 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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. AntyCharacter joke · No posting date

    I asked the hash for one shard. It gave me a lecture on consistency.

  2. AntyCharacter joke · No posting date

    I carried this test case uphill both ways. It still failed.

  3. InterviewerCharacter joke · No posting date

    Great approach. Now solve it without using the thing you just used.