System Design · Chapter SD4

Design patterns

Patterns as shared vocabulary: creational, structural & behavioral in real Python (with Pythonic shortcuts), climbing to two full machine-coding rounds — a rate limiter and an LRU cache.

⏱️ ~3 hours🧪 5 labs🎯 Beginner→Expert

Learning objectives

Explain what patterns are and when NOT to use them.
Implement patterns from all three families in runnable Python.
Give the Pythonic shortcut where the language makes a pattern trivial.
Complete two machine-coding rounds end-to-end.

▶ Runnable companionEvery code block here is also saved under code/sd4-design-patterns/ — pure Python / sqlite3, runs with no setup.

1 · What patterns are (and aren't) essential

A design pattern is a named, reusable solution to a recurring design problem — shared vocabulary more than code to copy. Three families. Caution: patterns are tools, not goals; Python's first-class functions make several patterns nearly free.

Family	Solves	Examples
Creational	how objects are made	Factory, Singleton, Builder
Structural	how objects compose	Adapter, Decorator, Facade
Behavioral	how objects interact	Strategy, Observer, State

2 · Creational — Factory & Singleton essential

Example code for learning — review, test, and adapt it before running against real or production systems. Commands can create, change, or delete resources. See the Terms & Disclaimer.

Step 1 · Factory + Singleton

creational.pyfrom abc import ABC, abstractmethod

class Storage(ABC):
    @abstractmethod
    def save(self, key): ...
class S3(Storage):
    def save(self, key): return f"S3:{key}"
class Local(Storage):
    def save(self, key): return f"local:{key}"

def make_storage(kind) -> Storage:            # FACTORY: callers don't name classes
    return {"s3": S3, "local": Local}[kind]()

class Config:                                 # SINGLETON: one shared instance
    _instance = None
    def __new__(cls):
        if cls._instance is None:
            cls._instance = super().__new__(cls); cls._instance.data = {}
        return cls._instance

print(make_storage("s3").save("a"), make_storage("local").save("b"))
print("same config:", Config() is Config())

S3:a local:b
same config: True

▶ How this works

Two creational patterns in one file — they answer the question "how do I make objects?" without hard-coding class names everywhere. Factory hides which class to build behind one function; Singleton guarantees there is only ever one shared object of a kind (handy for config, a database connection, a logger).

class Storage(ABC) with @abstractmethod def save is a contract: any storage must have a save method. S3 and Local are two real implementations that fill in that method differently.
make_storage(kind) is the Factory. You ask for "s3" or "local" by name; it looks the name up in a little dictionary {"s3": S3, "local": Local} and the trailing () builds one. The caller never writes S3() directly, so swapping storage means changing one string.
class Config is the Singleton. The special __new__ method runs before an object is created. It checks if cls._instance is None — the first time it builds and remembers one instance; every later Config() returns that same stored object instead of a fresh one.
Config() is Config() uses is (same object in memory, not just equal values). It prints True, proving both calls handed back the one shared instance.

What the output means: S3:a local:b shows the factory built two different storages from strings; same config: True confirms the Singleton returned one and the same object twice.

Try this: Add a third backend — e.g. class Memory(Storage) — and one entry "mem": Memory to the factory dictionary. Notice you extend the system without touching make_storage's callers. That is the whole point of a Factory.

3 · Structural — Decorator & Adapter intermediate

Decorator wraps an object to add behavior; Adapter makes an incompatible interface fit. Both let you extend without editing the original (Open/Closed, SD3).

Step 2 · Decorator adds caching to any fetcher

structural.pyclass DataSource:
    def get(self, key):
        print(f"  fetch {key}"); return f"value:{key}"

class Caching:                                 # wraps another DataSource
    def __init__(self, inner): self.inner, self._c = inner, {}
    def get(self, key):
        if key not in self._c: self._c[key] = self.inner.get(key)
        return self._c[key]

ds = Caching(DataSource())
print(ds.get("x")); print(ds.get("x"))         # 2nd call: no fetch

  fetch x
value:x
value:x

▶ How this works

The Decorator pattern adds new behaviour to an object by wrapping it, instead of editing the original class. Here we bolt caching onto any data source so a repeated lookup is served from memory rather than fetched again. The original DataSource is never changed — this is the Open/Closed idea from SD3 (open to extend, closed to edit).

DataSource.get(key) is the real (slow) worker: it prints fetch key every time it runs, so you can see when an actual fetch happens.
class Caching takes another data source in its __init__ (self.inner) and keeps an empty dictionary self._c as its cache. It has the same get method, so callers can't tell it apart from the real thing.
Inside get: if key not in self._c — only when the answer is missing does it call self.inner.get(key) and store the result. Otherwise it returns the saved value.
ds = Caching(DataSource()) wraps the real source. The first ds.get("x") triggers a fetch; the second finds "x" already cached and skips it.

What the output means: fetch x prints only once even though we called get("x") twice; both calls return value:x. The single fetch line is proof the cache worked.

Try this: Call ds.get("y") — you'll see a new fetch y. Then call it again and the fetch disappears. You just added caching to a class you never modified.

4 · Behavioral — Strategy & Observer (the Pythonic way) advanced

Strategy swaps an algorithm; Observer notifies subscribers of events. In Python both are often just functions/callables — no class hierarchy needed.

Step 3 · Strategy + Observer, Pythonic

behavioral.py# STRATEGY: a strategy is just a callable
def by_price(i): return i["price"]
def by_name(i):  return i["name"]
def sort_items(items, key): return sorted(items, key=key)

items = [{"name": "pen", "price": 3}, {"name": "book", "price": 1}]
print([i["name"] for i in sort_items(items, by_price)])   # cheapest first

# OBSERVER: subscribers are just functions in a list
class Event:
    def __init__(self): self._subs = []
    def subscribe(self, fn): self._subs.append(fn)
    def fire(self, data):
        for fn in self._subs: fn(data)

order_placed = Event()
order_placed.subscribe(lambda o: print(f"email: order {o}"))
order_placed.subscribe(lambda o: print(f"analytics: {o}"))
order_placed.fire("A1")

['book', 'pen']
email: order A1
analytics: A1

▶ How this works

Two behavioral patterns — how objects interact. Strategy lets you swap the algorithm a piece of code uses (here, how to sort) without rewriting it. Observer lets many listeners react to an event without the event knowing who they are. In Python both are usually just functions, so you rarely need the heavy class hierarchies other languages use.

Strategy: by_price and by_name are tiny functions that each pull one field out of an item. sort_items(items, key) takes one of them as its key and hands it to Python's built-in sorted. Passing a different function = a different sorting strategy, with no change to sort_items.
The list comprehension [i["name"] for i in sort_items(items, by_price)] sorts the items cheapest-first, then keeps just their names to print.
Observer: class Event holds a list self._subs of subscriber functions. subscribe(fn) adds one; fire(data) loops over them all and calls each with the data.
order_placed.subscribe(lambda o: ...) registers two one-line functions (a lambda is a function with no name). order_placed.fire("A1") then notifies both — the event never needs to know what they do.

What the output means: ['book', 'pen'] is the price-sorted order (book £1 before pen £3). Then firing the event runs both subscribers: email: order A1 and analytics: A1.

Try this: Add print([i["name"] for i in sort_items(items, by_name)]) to sort alphabetically instead — same function, new strategy. Or subscribe a third listener and fire again; it prints too, no other code touched.

Don't cargo-cult patternsIn Java you'd write a Strategy interface + N classes. In Python, pass a function. Know the pattern to recognize the problem — then use the simplest Python that solves it.

5 · Machine-coding round #1 — rate limiter advanced

Interviews include a machine-coding round: a small, clean, working component in ~45 min. Approach: clarify the interface, pick the algorithm, write SOLID classes, self-test.

How to run a machine-coding round

Clarify requirements + the exact interface (methods, inputs, outputs).
Pick the core algorithm/data structure.
Write clean, single-responsibility, testable code (inject the clock!).
Add a self-test that proves it; mention thread-safety + extensions.

Step 4 · Token-bucket rate limiter

rate_limiter.pyimport threading

class RateLimiter:
    """Allow `rate` req/sec, bursting up to `capacity` tokens. Clock injected -> testable."""
    def __init__(self, rate, capacity):
        self.rate, self.capacity = rate, capacity
        self.tokens = capacity; self.updated = None
        self._lock = threading.Lock()
    def allow(self, now):
        with self._lock:
            if self.updated is None: self.updated = now
            self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate)
            self.updated = now
            if self.tokens >= 1:
                self.tokens -= 1; return True
            return False

rl = RateLimiter(rate=2, capacity=2)
print([rl.allow(1000.0) for _ in range(3)])   # [True, True, False]
print(rl.allow(1001.0))                        # True — refilled after 1s

[True, True, False]
True

▶ How this works

A rate limiter decides whether a request is allowed right now so a service isn't flooded. This is the classic token-bucket design: imagine a bucket that refills with tokens over time; each request spends one token, and when the bucket is empty requests are refused. It allows short bursts but caps the long-run rate.

__init__ stores the rate (tokens added per second) and capacity (the most tokens the bucket can hold). It starts full (self.tokens = capacity) and takes a threading.Lock() so two threads can't corrupt the count at once.
allow(now) receives the current time as an argument (the "clock" is injected, not read inside) — that makes the class easy to test with fake times.
The refill line self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate) adds tokens for the time elapsed since last checked, but never above capacity. Then it records self.updated = now.
if self.tokens >= 1: spend one token (self.tokens -= 1) and return True (allowed); otherwise return False (rejected).

What the output means: [True, True, False]: at time 1000 the bucket holds 2 tokens, so the first two requests pass and the third is refused (empty). At time 1001, one second later, rate=2 has refilled tokens, so the next allow returns True.

Try this: Change capacity=2 to capacity=5 and re-run the burst — more requests now pass instantly. The rate controls the steady speed; capacity controls how big a burst you tolerate.

6 · Machine-coding round #2 — LRU cache expert

A second, harder round: an LRU cache with O(1) get/put. The trick is combining a hash map (for lookup) with a doubly-linked order (for eviction) — Python's OrderedDict gives both. This exact component powers SD5's caching.

Step 5 · LRU cache with a self-test

lru_cache.pyfrom collections import OrderedDict

class LRUCache:
    """O(1) get/put; evicts least-recently-used when full."""
    def __init__(self, capacity):
        self.cap = capacity; self._d = OrderedDict()
    def get(self, key):
        if key not in self._d: return -1
        self._d.move_to_end(key); return self._d[key]
    def put(self, key, value):
        if key in self._d: self._d.move_to_end(key)
        self._d[key] = value
        if len(self._d) > self.cap: self._d.popitem(last=False)

c = LRUCache(2)
c.put(1, "a"); c.put(2, "b")
assert c.get(1) == "a"          # 1 is now most-recent
c.put(3, "c")                    # evicts 2 (least-recent)
assert c.get(2) == -1
assert c.get(3) == "c"
print("LRU cache passes its self-test")

LRU cache passes its self-test

▶ How this works

An LRU (Least-Recently-Used) cache keeps only the most recently used items and throws away the one untouched longest when it runs out of room. It's how real caches stay small yet useful. The hard part is doing both get and put in O(1) (constant, instant) time — Python's OrderedDict remembers insertion order and gives us that for free.

__init__ stores the max size self.cap and an empty OrderedDict(). In this dict, the front is the least-recently-used item and the end is the most-recently-used.
get(key): if the key isn't there, return -1 (a "miss"). If it is, self._d.move_to_end(key) marks it as freshly used, then returns its value.
put(key, value): if the key already exists, move it to the end first; then store the value. If the dict is now bigger than self.cap, self._d.popitem(last=False) removes the item at the front — the least-recently-used one.
The assert lines are a built-in self-test: each one crashes loudly if the cache misbehaves, so running the file with no error is the proof it works.

What the output means: After put(1,"a") and put(2,"b"), reading key 1 makes it most-recent; adding key 3 then evicts key 2. So get(2) returns -1 (gone) and get(3) returns "c". All asserts pass, so it prints LRU cache passes its self-test.

Try this: Change LRUCache(2) to LRUCache(3) and re-run. Now key 2 is not evicted, so assert c.get(2) == -1 fails — proof that capacity is what forces eviction.

Why inject the clock / self-testPassing now in (not calling time.time() inside) makes the limiter deterministically testable — Dependency Inversion (SD3) paying off. A self-test that asserts the behavior is exactly what interviewers want to see.

Exercise SD4.1 — Your own machine-coding round

Context: Running your own timed machine-coding round is how you rehearse the real thing: clarify the interface, choose a data structure, write SOLID classes, and back it with self-tests — all in about 45 minutes.

Your task: In 45 minutes, build one of a parking-lot allocator, an in-memory KV store with TTL, or a connection pool, with a clear interface, an intentional data-structure choice, SOLID classes, and assert-based self-tests.

Requirements:

State the public interface before writing any implementation
Justify the chosen data structure for the core operations
Design the classes along SOLID lines (single responsibility, injectable dependencies)
Include assert-based self-tests that exercise the main paths
Name one design pattern you used and one concrete extension you'd add next

💡 Hint: Model time or capacity explicitly (pass now, cap the pool) so the tests are deterministic; the pattern you name should fall out of the design, not be bolted on.

🪜 Practice ladder beginner → industry

Six graded exercises, easy to real-world. Try each before opening its solution.

Exercise 1 · FactoryBeginner

Context: A factory centralizes the knowledge of how to build objects so callers don't hard-code constructors all over the codebase. When creation logic changes, you edit one place.

Your task: Write a shape_factory(kind) that returns the correct shape instance for a given name, so callers ask for a "circle" or "square" without naming the class.

Requirements:

Provide at least two shape classes exposing a common method (e.g. area())
Map the kind string to the right class in a single lookup
Return a constructed instance, not the class itself
Show that adding a new shape means editing one map, not every call site

💡 Hint: A dict from name to class, indexed and immediately called, is the whole factory; the payoff is that call sites stay ignorant of concrete constructors.

Show solution

The factory is the single place that knows how to build things:

class Circle:  area = lambda self: 3.14159
class Square:  area = lambda self: 4.0

def shape_factory(kind):
    return {"circle": Circle, "square": Square}[kind]()

print(round(shape_factory("circle").area(), 2))   # 3.14
print(shape_factory("square").area())             # 4.0

Adding a shape means editing one map, not every call site — the classic reason to reach for a factory.

Exercise 2 · Singleton (the Pythonic way)Intermediate

Context: Singletons enforce exactly one instance — a shared config, say. Python makes the textbook version look heavy, because a module-level object already is a singleton, so knowing when to skip the ceremony matters.

Your task: Show the naive class-based singleton (overriding __new__) alongside the Pythonic shortcut of a shared module-level object, and note when each is appropriate.

Requirements:

Implement a class that returns the same instance on every construction via __new__
Prove two constructions are the same object (is comparison)
Contrast it with a plain module-level object imported and shared everywhere
Mutate the shared object and show all references see the change
Conclude that the module-level object is the first choice; the class ceremony is rarely worth it

💡 Hint: Cache the single instance on a class attribute inside __new__; then observe that a module global gives you the same guarantee for free.

Show solution

Python often makes a pattern trivial — a module is a singleton:

# Class-based (works, but verbose):
class Config:
    _instance = None
    def __new__(cls):
        if cls._instance is None:
            cls._instance = super().__new__(cls)
        return cls._instance

print(Config() is Config())   # True

# Pythonic shortcut: just use a module-level object.
CONFIG = {"env": "prod"}       # import it anywhere; one shared object
CONFIG["env"] = "staging"
print(CONFIG)                  # {'env': 'staging'}

The lesson's caution applies: reach for the module-level object first; the class ceremony is rarely worth it in Python.

Exercise 3 · Decorator (wrap behavior)Advanced

Context: Decorators add behavior around a function without editing it — the structural pattern Python built into the language. Wrapping is how you bolt on cross-cutting concerns like counting, timing, or logging.

Your task: Write a counted decorator that tracks how many times the wrapped function was called, wrapping any function without altering its body, and keeping the call-count deterministic (no real clock).

Requirements:

Wrap the target function and forward arbitrary *args, **kwargs
Track a call counter that survives across calls (e.g. on the wrapper)
Preserve the wrapped function's name and docstring with functools.wraps
Show the count incrementing and the original return value still coming through
Keep it deterministic — count calls rather than measuring wall-clock time

💡 Hint: functools.wraps is the production-safety detail that keeps the wrapped function's identity intact; store the counter as an attribute of the wrapper.

Show solution

Decorators wrap — the structural pattern Python builds into the language:

import functools

def counted(fn):
    @functools.wraps(fn)
    def wrapper(*a, **k):
        wrapper.calls += 1
        return fn(*a, **k)
    wrapper.calls = 0
    return wrapper

@counted
def add(a, b): return a + b

add(1, 2); add(3, 4)
print(add.calls)          # 2
print(add(5, 6))          # 11

functools.wraps preserves the wrapped function's name/doc — the detail that makes decorators production-safe.

Exercise 4 · AdapterExpert

Context: An adapter makes an incompatible interface fit the one your code already speaks. It is how you integrate a third-party class you can't change without leaking its quirks everywhere.

Your task: Adapt a third-party CelsiusSensor (which reads Celsius) to the TemperatureReader interface your app expects (which reads Fahrenheit).

Requirements:

Treat the third-party sensor as unchangeable
Define the interface your application actually depends on (Fahrenheit)
Implement an adapter that wraps the sensor and translates its output
Have your code depend only on the target interface, never the sensor directly
Show the adapter absorbing the mismatch (the correct converted reading)

💡 Hint: The adapter holds the foreign object and does the unit conversion inside the method your interface promises; nothing downstream knows the source was in Celsius.

Show solution

The adapter translates one interface into another your code already speaks:

class CelsiusSensor:                  # third-party, can't change
    def read_c(self): return 25.0

class TemperatureReader:              # what our app expects
    def read_f(self): raise NotImplementedError

class CelsiusAdapter(TemperatureReader):
    def __init__(self, sensor): self.sensor = sensor
    def read_f(self): return self.sensor.read_c() * 9 / 5 + 32

reader = CelsiusAdapter(CelsiusSensor())
print(reader.read_f())   # 77.0

Our code depends only on read_f(); the adapter absorbs the mismatch so the third-party class needs no changes.

Exercise 5 · Machine-coding: a rate limiterProfessional

Context: Machine-coding rounds test whether you can build a small, correct, testable system under time pressure. A fixed-window rate limiter is a canonical prompt, and injecting the clock is what makes it deterministic and offline-testable.

Your task: Implement a fixed-window rate limiter that allows at most N calls per time window, modelling time explicitly by passing now into each call so results are reproducible.

Requirements:

Track the current window's start time and the count of calls within it
Reset the count when a call arrives in a new window
Allow a call only while the count is below the limit, otherwise reject it
Accept now as a parameter rather than reading the system clock
Demonstrate the limit blocking the surplus call and a new window re-allowing calls

💡 Hint: Passing now in (instead of calling time.time()) is what makes every window boundary reproducible in a test; compare now - window_start against the window size.

Show solution

Injecting the clock keeps it testable — a machine-coding staple:

class RateLimiter:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.count, self.window_start = 0, 0
    def allow(self, now):
        if now - self.window_start >= self.window:   # new window
            self.window_start, self.count = now, 0
        if self.count < self.limit:
            self.count += 1
            return True
        return False

rl = RateLimiter(limit=2, window=10)
print([rl.allow(t) for t in (0, 1, 2)])   # [True, True, False]  (3rd in window blocked)
print(rl.allow(11))                        # True  (new window at t=11)

Passing now in (rather than calling time.time()) makes every window boundary reproducible in a test.

Exercise 6 · Machine-coding: an LRU cacheIndustry scenario

Context: The LRU cache is the second machine-coding staple: constant-time get and put with least-recently-used eviction. An ordered dict gives you the ordering for free instead of hand-rolling a doubly linked list.

Your task: Implement an LRU cache with O(1) get and put using collections.OrderedDict, evicting the least-recently-used key when the cache is at capacity.

Requirements:

Back the cache with an OrderedDict and a capacity
On get, mark the key most-recently-used with move_to_end (or return a miss sentinel)
On put, insert/update and mark the key most-recently-used
When over capacity, evict the least-recently-used entry with popitem(last=False)
Demonstrate an access promoting a key and a subsequent insert evicting the stale one

💡 Hint: move_to_end on every access plus popitem(last=False) on overflow implements true LRU with clean O(1) operations — no linked list needed.

Show solution

Ordered-dict move-to-end gives O(1) LRU without a hand-rolled linked list:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.d = OrderedDict()
    def get(self, key):
        if key not in self.d: return -1
        self.d.move_to_end(key)          # mark as recently used
        return self.d[key]
    def put(self, key, value):
        if key in self.d: self.d.move_to_end(key)
        self.d[key] = value
        if len(self.d) > self.cap:
            self.d.popitem(last=False)   # evict least-recently-used

c = LRUCache(2)
c.put(1, "a"); c.put(2, "b")
print(c.get(1))       # a  (now 1 is most-recent)
c.put(3, "c")         # evicts key 2 (least-recent)
print(c.get(2))       # -1 (evicted)
print(c.get(3))       # c

move_to_end on access and popitem(last=False) on overflow implement true LRU with clean O(1) operations.

✓ Checkpoint — you can move on when you can…

Explain the three families and when NOT to use a pattern.
Implement creational, structural, and behavioral patterns in Python.
Give the Pythonic shortcut for Strategy/Observer.
Complete a machine-coding round with clean, self-tested code.

Knowledge check check yourself

✓ Knowledge check

The lesson groups design patterns into three families. Name each family, what it solves, and give one example pattern from each.

Show answer

Creational patterns solve how objects are made (e.g. Factory, Singleton, Builder). Structural patterns solve how objects compose (e.g. Adapter, Decorator, Facade). Behavioral patterns solve how objects interact (e.g. Strategy, Observer, State).

✓ Knowledge check

Why does the lesson inject the clock (passing now into allow) in the token-bucket rate limiter instead of calling time.time() inside it?

Show answer

Passing the current time in as an argument makes the limiter deterministically testable — you can feed fixed/fake times to assert exact behavior. It's an application of Dependency Inversion (SD3), and pairing it with an assert-based self-test is exactly what interviewers want to see in a machine-coding round.

Educational content, provided as-is and without warranty. Code samples are examples — review, test, and adapt them before using in production. See the Terms of Use & Disclaimer. Use at your own risk.

Learning objectives

1 · What patterns are (and aren't) essential

2 · Creational — Factory & Singleton essential

3 · Structural — Decorator & Adapter intermediate

4 · Behavioral — Strategy & Observer (the Pythonic way) advanced

5 · Machine-coding round #1 — rate limiter advanced

6 · Machine-coding round #2 — LRU cache expert

Exercise SD4.1 — Your own machine-coding round

🪜 Practice ladder beginner → industry

✓ Checkpoint — you can move on when you can…

Knowledge check check yourself

More in System design