Design a URL shortener (class level)

01The design, in the six-step framework

1. Requirements and use cases

At class level, the question is not about sharding but about clean seams: how a code is generated, where mappings live, and how expiry and caching stay out of the core logic. The scaled version is the system design problem.

• A user shortens a long URL and gets a code.
• A user chooses a custom alias; a taken alias is refused.
• A visitor resolves a code to its URL, and the hit is counted.
• A link expires at an optional time; an expired code resolves to nothing.
• An owner reads stats and deletes a link.

Out of scope: multi-node storage, analytics beyond a counter, and malicious URL scanning, though reported interviews asked about both collisions and malicious links, so leave a place for a validator. Non-functional constraints: the code generator and the storage are both swappable; resolve is a dictionary lookup in the common case; tests run with a fake clock and an in-memory repository.

2. Core entities and relationships

• ShortLink: code, long URL, owner, created and expiry times, and a hit count.
• CodeGenerator: an interface; counter-based Base62 and random implementations.
• LinkRepository: an interface for save-if-absent, find and delete.
• InMemoryRepository: the implementation used here.
• CachingRepository: a decorator that keeps recent lookups in an LRU.
• UrlValidator: rejects malformed or blocked URLs.
• ShortenerService: the use cases, depending only on interfaces.
• Clock: injected time.

The service owns nothing concrete: it uses interfaces handed to it. CachingRepository both implements and wraps a repository, which is what lets it slide in without the service noticing.

3. Interfaces and key methods

class CodeGenerator(Protocol):
    def next_code(self, url: str) -> str: ...

class LinkRepository(Protocol):
    def save_if_absent(self, link: ShortLink) -> bool:
        """Atomic: False if the code exists. This is the uniqueness guarantee."""
    def find(self, code: str) -> Optional[ShortLink]: ...
    def delete(self, code: str) -> None: ...

class Clock(Protocol):
    def now(self) -> float: ...

class ShortenerService:
    def shorten(self, url: str, owner: str, alias: Optional[str] = None,
                ttl: Optional[float] = None) -> ShortLink:
        """Validate, generate or take the alias, save; raise AliasTaken."""
    def resolve(self, code: str) -> Optional[str]:
        """The URL, or None if unknown or expired; counts a hit."""
    def stats(self, code: str) -> int: ...
    def delete(self, code: str, owner: str) -> None: ...

Invariants: a code maps to one link for that link's whole life; an expired link never resolves even if it is still stored; only the owner deletes. Uniqueness is the repository's job, enforced in one atomic call, not by a find followed by a save.

4. Design patterns and the choices behind them

Code generation as a strategy

A counter in Base62 is short, collision-free and guessable. Random codes are unguessable and need a collision retry. A hash of the URL deduplicates but collides on truncation. Each is a strategy behind next_code, and the service retries on a failed save for all of them, so swapping costs one line at construction.

Repository and dependency inversion

The service depends on the LinkRepository interface, not on a dictionary or a database. That is dependency inversion and it draws the layer line: domain rules above, storage below. The test double is the real in-memory class.

Cache as a decorator

Reads outnumber writes heavily. Wrapping the repository means the service has no cache code at all, and the eviction logic stays in one small class. The alternative, a cache check inside resolve, mixes two concerns and forgets invalidation on delete.

Lazy expiry

Expiry is checked at read time with an injected clock, which is simple and exact; a background sweep only reclaims memory. Doing just this much is YAGNI applied: no scheduler until memory is a stated problem.

5. Core flow and code

1. shorten validates the URL and builds a ShortLink using the alias or gen.next_code.
2. repo.save_if_absent stores it atomically; on a collision an alias raises and a generated code retries.
3. resolve finds the link, checks expired(clock.now()), increments the hit counter and returns the URL.
4. delete checks the owner and removes it through the repository, so the cache layer invalidates too.

from __future__ import annotations
import itertools, secrets, string, threading, time
from collections import OrderedDict
from dataclasses import dataclass
from typing import Optional, Protocol
from urllib.parse import urlparse

ALPHABET = string.digits + string.ascii_letters


class AliasTaken(Exception): ...
class InvalidUrl(Exception): ...
class NotOwner(Exception): ...


@dataclass
class ShortLink:
    code: str
    url: str
    owner: str
    created_at: float
    expires_at: Optional[float] = None
    hits: int = 0

    def expired(self, now: float) -> bool:
        return self.expires_at is not None and now >= self.expires_at


class Clock(Protocol):
    def now(self) -> float: ...


class SystemClock:
    def now(self) -> float: return time.time()


class CodeGenerator(Protocol):
    def next_code(self, url: str) -> str: ...


class Base62Counter:
    def __init__(self, start: int = 100_000) -> None:
        self.counter = itertools.count(start)     # next() on count is atomic in CPython
    def next_code(self, url: str) -> str:
        n, out = next(self.counter), []
        while n:
            n, r = divmod(n, 62)
            out.append(ALPHABET[r])
        return "".join(reversed(out))


class RandomCode:
    def __init__(self, length: int = 7) -> None:
        self.length = length
    def next_code(self, url: str) -> str:
        return "".join(secrets.choice(ALPHABET) for _ in range(self.length))


class LinkRepository(Protocol):
    def save_if_absent(self, link: ShortLink) -> bool: ...
    def find(self, code: str) -> Optional[ShortLink]: ...
    def delete(self, code: str) -> None: ...


class InMemoryRepository:
    def __init__(self) -> None:
        self.links: dict[str, ShortLink] = {}
        self.lock = threading.Lock()

    def save_if_absent(self, link: ShortLink) -> bool:
        with self.lock:
            if link.code in self.links:
                return False
            self.links[link.code] = link
            return True

    def find(self, code: str) -> Optional[ShortLink]:
        return self.links.get(code)

    def delete(self, code: str) -> None:
        with self.lock:
            self.links.pop(code, None)


class CachingRepository:
    """Decorator: an LRU of recent lookups in front of any repository."""
    def __init__(self, inner: LinkRepository, capacity: int = 10_000) -> None:
        self.inner, self.capacity = inner, capacity
        self.lru: OrderedDict[str, ShortLink] = OrderedDict()
        self.lock = threading.Lock()

    def save_if_absent(self, link: ShortLink) -> bool:
        return self.inner.save_if_absent(link)

    def find(self, code: str) -> Optional[ShortLink]:
        with self.lock:
            if code in self.lru:
                self.lru.move_to_end(code)
                return self.lru[code]
        link = self.inner.find(code)
        if link is not None:
            with self.lock:
                self.lru[code] = link
                if len(self.lru) > self.capacity:
                    self.lru.popitem(last=False)
        return link

    def delete(self, code: str) -> None:
        self.inner.delete(code)
        with self.lock:
            self.lru.pop(code, None)


class UrlValidator:
    def __init__(self, blocked_hosts: frozenset[str] = frozenset()) -> None:
        self.blocked = blocked_hosts
    def validate(self, url: str) -> None:
        parsed = urlparse(url)
        if parsed.scheme not in ("http", "https") or not parsed.netloc:
            raise InvalidUrl(url)
        if parsed.netloc in self.blocked:
            raise InvalidUrl("blocked host")


class ShortenerService:
    def __init__(self, repo: LinkRepository, gen: CodeGenerator, clock: Clock, validator: UrlValidator) -> None:
        self.repo, self.gen, self.clock, self.validator = repo, gen, clock, validator

    def shorten(self, url: str, owner: str, alias: Optional[str] = None, ttl: Optional[float] = None) -> ShortLink:
        self.validator.validate(url)
        now = self.clock.now()
        expires = now + ttl if ttl is not None else None
        if alias:
            link = ShortLink(alias, url, owner, now, expires)
            if not self.repo.save_if_absent(link):
                raise AliasTaken(alias)
            return link
        while True:                               # a collision just draws again
            link = ShortLink(self.gen.next_code(url), url, owner, now, expires)
            if self.repo.save_if_absent(link):
                return link

    def resolve(self, code: str) -> Optional[str]:
        link = self.repo.find(code)
        if link is None or link.expired(self.clock.now()):
            return None
        link.hits += 1
        return link.url

    def stats(self, code: str) -> int:
        link = self.repo.find(code)
        return link.hits if link else 0

    def delete(self, code: str, owner: str) -> None:
        link = self.repo.find(code)
        if link is None:
            return
        if link.owner != owner:
            raise NotOwner(code)
        self.repo.delete(code)

6. Extensions, concurrency and what interviewers probe

• Same URL twice: return the existing code or a new one? Per-owner dedup needs a reverse index from (owner, URL) to code; state which you chose, since analytics usually wants separate links.
• Collisions: the retry loop covers random codes, and save_if_absent is the atomic step that makes the check-then-write race impossible. A counter code can still collide with a custom alias, which is why the loop applies to counter codes too.
• Guessable codes: sequential Base62 exposes volume and lets scraping walk every link; a random strategy or a shuffled counter fixes it with a one-line swap.
• Hit counter races: link.hits += 1 is not atomic. Under threads, count in a sharded counter or per-link lock, and accept approximate stats if the interviewer allows it.
• Malicious links go in UrlValidator; re-checking at resolve time catches URLs that turned bad after creation.
• Pairing with LRU: one report paired this with an LRU that expires entries. With CachingRepository, an expired link in the cache is still caught because resolve checks expiry on the returned link.
• Test first: alias taken raises; a fake clock past expiry resolves to None; delete by a non-owner raises; deleting clears the cached copy; a generator forced to collide retries.
• Common mistake: find then save as two steps, which is exactly the race two users make for the same alias.

02Where this question was reported

• LLD Mastery · Google-tagged (Medium); encoding, redirection
• LLD Mastery · Google-tagged with Microsoft/Amazon/Meta/Twitter/LinkedIn; ID generation strategies
• Exponent / Aced · Aced Google-tagged 'Build TinyURL'
• DesignGurus · DesignGurus: class design, schema, hashing
• javarevisited.blogspot.com · javarevisited: creation, stats, concurrency, auditing
• 1point3acres · Google L4 pairing with LRU-with-expiry (snippet only)