Object-Oriented Programming & Low-Level Design

Encapsulation

Encapsulation bundles state (fields) and the behavior that operates on that state (methods) inside a single unit, and controls access through a narrow public interface. The goal is to make illegal states unrepresentable and illegal transitions unreachable from outside the object.

Two independent ideas, often conflated

• Bundling: data + behavior live together in the class.
• Information hiding: internal representation is private; clients depend only on the interface. Swapping ArrayList for LinkedList in a private field should break nothing.

Java example — BankAccount

public final class BankAccount {
    private long balanceCents;         // invariant: >= 0
    private final String owner;

    public BankAccount(String owner, long openingCents) {
        if (openingCents < 0) throw new IllegalArgumentException("negative opening");
        this.owner = Objects.requireNonNull(owner);
        this.balanceCents = openingCents;
    }
    public long balanceCents() { return balanceCents; }
    public synchronized void deposit(long cents) {
        if (cents <= 0) throw new IllegalArgumentException();
        balanceCents += cents;                      // invariant preserved
    }
    public synchronized void withdraw(long cents) {
        if (cents <= 0 || cents > balanceCents) throw new IllegalStateException();
        balanceCents -= cents;
    }
}

Python equivalent

class BankAccount:
    def __init__(self, owner: str, opening_cents: int) -> None:
        if opening_cents < 0: raise ValueError("negative opening")
        self._owner = owner                 # leading underscore = "private by convention"
        self._balance_cents = opening_cents
    @property
    def balance_cents(self) -> int: return self._balance_cents
    def deposit(self, cents: int) -> None:
        if cents <= 0: raise ValueError
        self._balance_cents += cents
    def withdraw(self, cents: int) -> None:
        if cents <= 0 or cents > self._balance_cents: raise RuntimeError
        self._balance_cents -= cents

Inheritance

Inheritance models "is-a" — a subclass specializes a superclass and inherits its members. It exists to enable subtype polymorphism (the subclass can be used wherever the superclass is expected) and to reuse implementation.

The two axes

• Subtyping (interface): Dog is-a Animal at the type level; the compiler lets you pass a Dog where Animal is required.
• Subclassing (implementation): fields and method bodies of the superclass are re-used by the subclass.

Java bundles both; Go separates them (interfaces provide subtyping; struct embedding provides implementation reuse).

Java snippet

abstract class Shape {
    abstract double area();
    public String describe() { return getClass().getSimpleName() + " area=" + area(); }
}
class Circle extends Shape {
    private final double r;
    public Circle(double r) { this.r = r; }
    @Override double area() { return Math.PI * r * r; }
}
class Rectangle extends Shape {
    private final double w, h;
    public Rectangle(double w, double h) { this.w = w; this.h = h; }
    @Override double area() { return w * h; }
}

Python snippet

from abc import ABC, abstractmethod
class Shape(ABC):
    @abstractmethod
    def area(self) -> float: ...
    def describe(self) -> str: return f"{type(self).__name__} area={self.area()}"
class Circle(Shape):
    def __init__(self, r: float): self.r = r
    def area(self) -> float: return 3.14159 * self.r ** 2
class Rectangle(Shape):
    def __init__(self, w: float, h: float): self.w, self.h = w, h
    def area(self) -> float: return self.w * self.h

Polymorphism

Polymorphism = "one interface, many implementations." Four flavors in practice:

Java — subtype polymorphism in action

public static double totalArea(List<Shape> shapes) {
    double total = 0;
    for (Shape s : shapes) total += s.area();   // dispatches on s's runtime class
    return total;
}
// callers do not know or care whether s is a Circle, Rectangle, or a type invented tomorrow.

Abstraction

Abstraction exposes essential behavior while hiding implementation. In Java it is expressed through interface and abstract class; in Python through abstract base classes (abc) or protocols (typing.Protocol).

Abstract class vs. interface

Python Protocol (structural typing)

from typing import Protocol
class Drawable(Protocol):
    def draw(self, canvas) -> None: ...

def render(items: list[Drawable], canvas) -> None:
    for item in items: item.draw(canvas)     # any object with .draw() works

Class Diagram Legend

Every LLD interview ends with you drawing UML on the whiteboard. Know the connectors.

Multiplicity notation

• 1 — exactly one
• 0..1 — zero or one (optional)
• * or 0..* — many
• 1..* — at least one
• n..m — bounded range

Static vs Dynamic Dispatch

Method dispatch is the runtime's mechanism for choosing which implementation runs when you call obj.method(). Static dispatch binds at compile time (by declared type); dynamic dispatch binds at runtime (by actual object class).

Why it matters

• Static: one assembly jump, branch predictor-friendly, inlinable.
• Dynamic: an extra indirection through the vtable (Java/C++), method resolution order (Python), or itable (Go interface).

S — Single Responsibility Principle

A class should have one, and only one, reason to change. "Responsibility" here means source of change — an actor (business role, subsystem, stakeholder) who can request modifications. Two responsibilities => two reasons to change => a class that mutates whenever either actor speaks up.

class Employee {
    double calculatePay()           { /* finance says: new bonus formula */ }
    void   save(Connection db)      { /* DBA says: switch to postgres */ }
    String reportHours()            { /* HR says: add overtime column */ }
}

class Employee { /* data + invariants only */ }
class PayCalculator  { double payFor(Employee e) { ... } }
class EmployeeRepo   { void save(Employee e)    { ... } }
class HoursReporter  { String report(Employee e)  { ... } }

class Report:
    def build(self): ...          # content team
    def to_pdf(self): ...          # typography team
    def email(self, to): ...        # ops team

class Report: ...
class PdfRenderer:
    def render(self, r: Report) -> bytes: ...
class Emailer:
    def send(self, attachment: bytes, to: str) -> None: ...

class User {
  validate() { ... }       // security concern
  save()     { ... }       // persistence concern
  toJSON()   { ... }       // serialization concern
}

class User {}
class UserValidator { validate(u: User): boolean { ... } }
class UserRepo      { save(u: User): Promise<void> { ... } }
class UserSerializer{ toJSON(u: User): string { ... } }

O — Open/Closed Principle

Software entities should be open for extension, closed for modification. Adding a new kind of shape, payment, or sensor should require adding new code, not editing an if/else chain in existing code. Achieved by dispatching through an abstraction.

class AreaCalculator {
    double area(Object s) {
        if (s instanceof Circle c)     return Math.PI * c.r * c.r;
        if (s instanceof Rectangle r)  return r.w * r.h;
        throw new IllegalArgumentException();
    }
}

interface Shape { double area(); }
class Circle    implements Shape { ... }
class Rectangle implements Shape { ... }
class Triangle  implements Shape { ... }   // added, nothing else changed
class AreaCalculator { double area(Shape s) { return s.area(); } }

def pay(account, method):
    if method == "card": charge_card(account)
    elif method == "paypal": charge_paypal(account)
    elif method == "wire": charge_wire(account)

class PaymentMethod(Protocol):
    def charge(self, account: Account, cents: int) -> Receipt: ...
def pay(account: Account, method: PaymentMethod, cents: int) -> Receipt:
    return method.charge(account, cents)       # adds new methods without touching pay()

function discount(order: Order): number {
  if (order.kind === "student") return order.total * 0.9;
  if (order.kind === "vip")     return order.total * 0.8;
  return order.total;
}

interface DiscountPolicy { apply(total: number): number; }
const Student: DiscountPolicy = { apply: t => t * 0.9 };
const Vip:     DiscountPolicy = { apply: t => t * 0.8 };
const None:    DiscountPolicy = { apply: t => t };
function discount(order: Order, p: DiscountPolicy) { return p.apply(order.total); }

L — Liskov Substitution Principle

If S is a subtype of T, any T in a program can be replaced with an S without altering correctness. Expressed as the "square/rectangle" trap: a Square that inherits from Rectangle violates LSP because setting width independently breaks the parent's contract.

class Rectangle { int w, h; void setW(int v){w=v;} void setH(int v){h=v;} int area(){return w*h;} }
class Square extends Rectangle {
    @Override void setW(int v) { w = h = v; }
    @Override void setH(int v) { w = h = v; }
}
// Caller expects Rectangle contract: setW(5);setH(4); -> area=20. Square breaks it.

interface Shape { int area(); }
record Rectangle(int w, int h) implements Shape { public int area() { return w*h; } }
record Square(int side)        implements Shape { public int area() { return side*side; } }

class Bird:
    def fly(self): ...
class Ostrich(Bird):
    def fly(self): raise NotImplementedError      # shouts at callers

class Bird: ...
class FlyingBird(Bird):
    def fly(self): ...
class Ostrich(Bird): ...     # simply has no fly() — no broken promise

function contractTest(s: Stack<number>) {
  s.push(1); s.push(2);
  expect(s.pop()).toBe(2);           // LIFO invariant must hold for ALL Stack impls
  expect(s.pop()).toBe(1);
  expect(s.isEmpty()).toBe(true);
}
[new ArrayStack(), new LinkedStack()].forEach(contractTest);

I — Interface Segregation Principle

Clients should not be forced to depend on methods they do not use. Fat interfaces leak irrelevant concerns into every implementer. Split by client need.

interface Worker {
    void work();
    void eat();           // robots should not care about lunch
    void sleep();
}

interface Workable { void work(); }
interface Feedable { void eat(); }
interface Restable { void sleep(); }
class Human implements Workable, Feedable, Restable { ... }
class Robot implements Workable { ... }

class Multifunction(Protocol):
    def print(self, doc): ...
    def scan(self, page): ...
    def fax(self, number, doc): ...

class Printer(Protocol):
    def print(self, doc): ...
class Scanner(Protocol):
    def scan(self, page): ...
class Fax(Protocol):
    def fax(self, number, doc): ...

interface Readable { read(k: string): string; }
interface Writable { write(k: string, v: string): void; }
class ReadOnlyStore implements Readable  { read(k){ ... } }
class FullStore     implements Readable, Writable { ... }
function view(s: Readable) { ... }     // caller only asks for what it needs

D — Dependency Inversion Principle

High-level modules should not depend on low-level modules; both should depend on abstractions. The direction of source-code dependencies should point away from concrete details, toward policy.

class OrderService {
    private MySqlOrderRepo repo = new MySqlOrderRepo();   // bound to MySQL forever
    void place(Order o) { repo.save(o); }
}

interface OrderRepo { void save(Order o); }           // owned by the policy layer
class OrderService {
    private final OrderRepo repo;
    public OrderService(OrderRepo repo) { this.repo = repo; }
    void place(Order o) { repo.save(o); }
}
// Low-level implementations live downstream:
class MySqlOrderRepo    implements OrderRepo { ... }
class InMemoryOrderRepo implements OrderRepo { ... }  // test double

class Clock(Protocol):
    def now(self) -> datetime: ...
class TokenService:
    def __init__(self, clock: Clock): self.clock = clock
    def issue(self): return Token(expires=self.clock.now() + TTL)
# production: SystemClock.now() -> datetime.now(); tests: FakeClock

interface Logger { info(msg: string): void; }
class App {
  constructor(private log: Logger) {}
  run() { this.log.info("start"); }
}
const app = new App(new ConsoleLogger());   // wiring is the composition root's job

Singleton (Creational)

Intent: ensure a class has exactly one instance and provide a global access point. Legitimate when the resource is truly one-of-a-kind (config, logger, connection pool).

// Enum singleton — serialization/reflection-safe, thread-safe by JVM guarantee.
public enum Config {
    INSTANCE;
    private final Properties props = load();
    public String get(String k) { return props.getProperty(k); }
    private Properties load() { ... }
}
// Usage: Config.INSTANCE.get("db.url");

class Config:
    _instance = None
    _lock = threading.Lock()
    def __new__(cls):
        if cls._instance is None:
            with cls._lock:
                if cls._instance is None:
                    cls._instance = super().__new__(cls)
                    cls._instance._init()
        return cls._instance
    def _init(self): self.props = self._load()

Factory Method (Creational)

Intent: defer instantiation to subclasses — the factory method returns an abstract product, and each subclass picks the concrete variant.

abstract class Dialog {
    abstract Button createButton();           // factory method
    public void render() {
        Button b = createButton();
        b.onClick(this::close);
        b.render();
    }
}
class WindowsDialog extends Dialog {
    @Override Button createButton() { return new WindowsButton(); }
}
class WebDialog extends Dialog {
    @Override Button createButton() { return new HtmlButton(); }
}

class Dialog(ABC):
    @abstractmethod
    def create_button(self) -> Button: ...
    def render(self):
        btn = self.create_button()
        btn.on_click(self.close); btn.render()

class WindowsDialog(Dialog):
    def create_button(self): return WindowsButton()
class WebDialog(Dialog):
    def create_button(self): return HtmlButton()

Abstract Factory (Creational)

Intent: provide an interface for creating families of related objects without specifying their concrete classes. Classic example: cross-platform UI kit where Button and Checkbox must come from the same family (Windows or Mac).

interface GuiFactory {
    Button   createButton();
    Checkbox createCheckbox();
}
class WinFactory implements GuiFactory {
    public Button createButton()    { return new WinButton(); }
    public Checkbox createCheckbox(){ return new WinCheckbox(); }
}
class MacFactory implements GuiFactory {
    public Button createButton()    { return new MacButton(); }
    public Checkbox createCheckbox(){ return new MacCheckbox(); }
}
class App {
    private final GuiFactory f;
    App(GuiFactory f) { this.f = f; }
    void render() { f.createButton().render(); f.createCheckbox().render(); }
}

class GuiFactory(Protocol):
    def create_button(self) -> Button: ...
    def create_checkbox(self) -> Checkbox: ...

class WinFactory:
    def create_button(self): return WinButton()
    def create_checkbox(self): return WinCheckbox()
class MacFactory:
    def create_button(self): return MacButton()
    def create_checkbox(self): return MacCheckbox()

Builder (Creational)

Intent: separate construction of a complex object from its representation, so the same construction process can yield different outcomes and long constructors vanish. Use when an object has 4+ optional fields.

public final class HttpRequest {
    private final String url; private final String method;
    private final Map<String,String> headers; private final byte[] body;
    private HttpRequest(Builder b) {
        this.url=b.url; this.method=b.method;
        this.headers=Map.copyOf(b.headers); this.body=b.body;
    }
    public static Builder get(String url)  { return new Builder(url, "GET"); }
    public static Builder post(String url) { return new Builder(url, "POST"); }
    public static class Builder {
        private final String url, method;
        private Map<String,String> headers = new LinkedHashMap<>();
        private byte[] body;
        Builder(String u, String m){ url=u; method=m; }
        public Builder header(String k, String v){ headers.put(k,v); return this; }
        public Builder body(byte[] b){ body=b; return this; }
        public HttpRequest build(){ return new HttpRequest(this); }
    }
}
// Usage: HttpRequest.post("/api").header("X","1").body(bytes).build();

from dataclasses import dataclass, field
@dataclass(frozen=True)
class HttpRequest:
    url: str; method: str = "GET"
    headers: tuple = ()
    body: bytes = b""

class HttpRequestBuilder:
    def __init__(self, url: str, method: str = "GET"):
        self._url, self._method = url, method
        self._headers: list[tuple[str,str]] = []; self._body = b""
    def header(self, k, v): self._headers.append((k,v)); return self
    def body(self, b):      self._body = b; return self
    def build(self):        return HttpRequest(self._url, self._method, tuple(self._headers), self._body)

Prototype (Creational)

Intent: create new objects by copying a prototype instance. Useful when construction is expensive (e.g., heavy initialization, complex state graphs) or when the class of objects to create is decided at runtime.

interface Shape extends Cloneable { Shape deepCopy(); }
class Circle implements Shape {
    double cx, cy, r; Color fill;
    public Circle deepCopy() {
        Circle c = new Circle();
        c.cx = cx; c.cy = cy; c.r = r;
        c.fill = new Color(fill.rgb);     // deep copy mutable fields
        return c;
    }
}
class ShapeRegistry {
    private final Map<String,Shape> map = new HashMap<>();
    public void register(String name, Shape proto) { map.put(name, proto); }
    public Shape create(String name) { return map.get(name).deepCopy(); }
}

import copy
class Tree:
    def __init__(self): self.nodes = [...]
    def clone(self): return copy.deepcopy(self)   # rely on std lib

registry: dict[str, Tree] = {"template": Tree()}
t = registry["template"].clone()

Adapter (Structural)

Intent: convert the interface of a class into another interface clients expect. The "shape of a plug" problem: you have a legacy library you cannot change but your callers speak a different protocol.

interface Logger {                                // Target — what we want
    void info(String msg);
}
class LegacyLog {                                  // Adaptee — what we have
    public void write(int level, String text) { ... }
}
class LegacyLogAdapter implements Logger {         // Adapter
    private final LegacyLog legacy;
    public LegacyLogAdapter(LegacyLog l){ legacy = l; }
    public void info(String msg){ legacy.write(1, msg); }
}

class LegacyLog:
    def write(self, level: int, text: str): ...

class LegacyLogAdapter:                  # duck-typed Logger
    def __init__(self, legacy: LegacyLog): self.legacy = legacy
    def info(self, msg: str): self.legacy.write(1, msg)

Decorator (Structural)

Intent: attach new responsibilities to an object dynamically by wrapping it in another object with the same interface. Good for cross-cutting concerns — caching, logging, auth, retries — without subclass explosions.

interface Notifier { void send(String msg); }
class EmailNotifier implements Notifier { public void send(String m){ ... } }
abstract class NotifierDecorator implements Notifier {
    protected final Notifier wrappee;
    NotifierDecorator(Notifier w){ wrappee = w; }
    public void send(String m){ wrappee.send(m); }
}
class SmsNotifier extends NotifierDecorator {
    SmsNotifier(Notifier w){ super(w); }
    @Override public void send(String m){ super.send(m); sendSms(m); }
}
// new SmsNotifier(new EmailNotifier()).send("hi")  sends both.

class Notifier(Protocol):
    def send(self, msg: str) -> None: ...

class EmailNotifier:
    def send(self, msg): ...

class SmsDecorator:
    def __init__(self, inner: Notifier): self.inner = inner
    def send(self, msg):
        self.inner.send(msg); send_sms(msg)

Proxy (Structural)

Intent: provide a surrogate that controls access to the real subject. Types: virtual (lazy-load), remote (RPC stub), protection (auth), caching.

interface ImageService { Image load(String url); }
class RealImageService implements ImageService {
    public Image load(String url) { /* expensive HTTP + decode */ }
}
class CachingImageProxy implements ImageService {
    private final ImageService inner;
    private final Map<String,Image> cache = new ConcurrentHashMap<>();
    public CachingImageProxy(ImageService i) { inner = i; }
    public Image load(String url) {
        return cache.computeIfAbsent(url, inner::load);
    }
}

class CachingImageProxy:
    def __init__(self, inner): self.inner = inner; self.cache = {}
    def load(self, url):
        if url not in self.cache:
            self.cache[url] = self.inner.load(url)
        return self.cache[url]

Observer (Behavioral)

Intent: establish a one-to-many dependency so that when one object (subject) changes state, all its dependents (observers) are notified. The backbone of pub/sub, UI event systems, reactive streams.

interface Observer<E> { void update(E event); }
class Subject<E> {
    private final List<Observer<E>> obs = new CopyOnWriteArrayList<>();
    public void subscribe(Observer<E> o)   { obs.add(o); }
    public void unsubscribe(Observer<E> o) { obs.remove(o); }
    protected void publish(E e)            { for (var o: obs) o.update(e); }
}
class PriceFeed extends Subject<Quote> {
    public void onTick(Quote q){ publish(q); }
}

class Subject:
    def __init__(self): self._subs = []
    def subscribe(self, cb): self._subs.append(cb)
    def unsubscribe(self, cb): self._subs.remove(cb)
    def publish(self, event):
        for cb in list(self._subs):   # copy to tolerate unsubscribe in handler
            cb(event)

Strategy (Behavioral)

Intent: define a family of algorithms, encapsulate each, and make them interchangeable at runtime. The Comparator you pass to Collections.sort is a Strategy.

interface CompressionStrategy { byte[] compress(byte[] data); }
class GzipStrategy  implements CompressionStrategy { ... }
class BrotliStrategy implements CompressionStrategy { ... }

class Archiver {
    private CompressionStrategy strategy;
    public void setStrategy(CompressionStrategy s){ strategy = s; }
    public byte[] archive(byte[] bytes){ return strategy.compress(bytes); }
}

CompressFn = Callable[[bytes], bytes]
def gzip_compress(b: bytes) -> bytes: ...
def brotli_compress(b: bytes) -> bytes: ...

class Archiver:
    def __init__(self, strategy: CompressFn): self.strategy = strategy
    def archive(self, data: bytes) -> bytes: return self.strategy(data)

Command (Behavioral)

Intent: encapsulate a request as an object so you can queue it, log it, undo it, or send it over the wire. Backbone of undo/redo, task queues, macro recording.

interface Command { void execute(); void undo(); }
class InsertText implements Command {
    private final Editor editor; private final int pos; private final String text;
    public InsertText(Editor e, int p, String t){ editor=e; pos=p; text=t; }
    public void execute(){ editor.insert(pos, text); }
    public void undo()   { editor.delete(pos, text.length()); }
}
class History {
    private final Deque<Command> stack = new ArrayDeque<>();
    public void run(Command c){ c.execute(); stack.push(c); }
    public void undo(){ if (!stack.isEmpty()) stack.pop().undo(); }
}

from dataclasses import dataclass
@dataclass
class InsertText:
    editor: Editor; pos: int; text: str
    def execute(self): self.editor.insert(self.pos, self.text)
    def undo(self):    self.editor.delete(self.pos, len(self.text))

class History:
    def __init__(self): self.stack = []
    def run(self, c): c.execute(); self.stack.append(c)
    def undo(self):   if self.stack: self.stack.pop().undo()

State (Behavioral)

Intent: allow an object to alter its behavior when its internal state changes — the object appears to change class. Swap giant if (state == X) ... else if (state == Y) ... chains with polymorphic state objects.

interface OrderState {
    void pay(Order o); void ship(Order o); void cancel(Order o);
}
class Created implements OrderState {
    public void pay(Order o)   { o.setState(new Paid()); }
    public void ship(Order o)  { throw new IllegalStateException(); }
    public void cancel(Order o){ o.setState(new Cancelled()); }
}
class Paid implements OrderState { /* pay -> error; ship -> Shipped; cancel -> Refunding */ }
class Order {
    private OrderState state = new Created();
    public void setState(OrderState s){ state = s; }
    public void pay(){ state.pay(this); }
    public void ship(){ state.ship(this); }
    public void cancel(){ state.cancel(this); }
}

class Created:
    def pay(self, o):   o.state = Paid()
    def ship(self, o):  raise RuntimeError
    def cancel(self, o):o.state = Cancelled()

class Order:
    def __init__(self): self.state = Created()
    def pay(self):    self.state.pay(self)
    def ship(self):   self.state.ship(self)
    def cancel(self): self.state.cancel(self)

Class Diagrams

A class box has three compartments: name / attributes / operations. Visibility markers: + public, - private, # protected, ~ package. Static members are underlined.

Notation legend

Sequence Diagrams

Time flows top to bottom; participants line up along the top. Solid arrows = synchronous call; dashed = return; open arrow = asynchronous.

State Diagrams

Circles = states; arrows = transitions labelled event [guard] / action. Solid dot = initial state; bulls-eye = terminal state.

Example: Order lifecycle
[*] --> Created
Created --> Paid       : pay() [amount==total]
Created --> Cancelled  : cancel()
Paid    --> Shipped    : ship() / decrement stock
Paid    --> Refunding  : cancel()
Shipped --> Delivered  : confirmDelivery()
Shipped --> Returning  : initiateReturn()
Delivered --> [*]
Cancelled --> [*]

Activity Diagrams

Flowchart for a process. Rounded rectangles = activities; diamonds = decisions; bars = fork/join for parallel paths. Use when a sequence of steps has branching but no object lifecycle.

Example: Checkout
Start -> validateCart -> [valid?]
  yes -> authorizePayment -> [auth?]
    yes -> reserveInventory -> shipOrder -> End
    no  -> showError -> End
  no  -> showError -> End

Parking Lot

Requirements

• Multi-floor lot; each floor has slots of types: Compact, Large, Handicapped, Motorcycle.
• Entry/exit gates; take ticket on entry, compute fee on exit.
• Hourly pricing, with different rates per slot type.
• Support multiple parking strategies (nearest, least-used-floor, random).
• Concurrent park/unpark from many gates; no double-allocation of the same slot.

// Hardest method: atomic allocation across concurrent gates.
public Optional<Ticket> park(Vehicle v) {
    for (Floor f : floors) {                     // try each floor
        Optional<Slot> s = strategy.pick(f.freeSlotsFor(v.type()));
        if (s.isEmpty()) continue;
        if (s.get().claim()) {                    // CAS isFree: true->false
            Ticket t = new Ticket(UUID.randomUUID(), v, s.get(), Instant.now());
            ticketRepo.save(t);
            return Optional.of(t);
        }
        // Lost the race — another gate got it; loop and retry.
    }
    return Optional.empty();                      // lot full
}

Elevator System

Requirements

• N elevators and M floors; both hall (outside) calls and cab (inside) requests.
• Scheduling must minimize total wait / travel; support directions (UP/DOWN/IDLE).
• Handle SCAN/LOOK-like algorithms (elevator continues in current direction, reverses only when no more pending in that direction).
• Emergency stop + maintenance mode remove an elevator from the pool.

// Hardest method: SCAN/LOOK scoring for dispatcher.
int scoreFor(Elevator e, Request r) {
    int d = Math.abs(e.floor() - r.srcFloor());
    if (e.dir() == Direction.IDLE)                   return d;
    boolean sameDir = e.dir() == r.dir();
    boolean onWay = sameDir &&
        ((e.dir() == UP   && e.floor() <= r.srcFloor()) ||
         (e.dir() == DOWN && e.floor() >= r.srcFloor()));
    return onWay ? d : (MAX_FLOOR * 2) + d;       // punish out-of-direction calls
}

Splitwise

Requirements

• Users create Groups; Groups own Expenses; Expenses split amongst members (equal, percentage, exact).
• Maintain per-pair balance sheet; simplify debts (A owes B, B owes C => A owes C).
• Settle-up records a payment that zeroes a pair's balance.
• All amounts in minor units (cents) to avoid floating-point drift.

// Hardest method: equal-split with remainder distribution (integer math).
public Map<User,Long> equalSplit(long cents, List<User> people) {
    long base = cents / people.size();
    long rem  = cents % people.size();                // leftover pennies
    Map<User,Long> shares = new LinkedHashMap<>();
    for (int i = 0; i < people.size(); i++) {
        long extra = i < rem ? 1 : 0;              // first `rem` members get 1 cent more
        shares.put(people.get(i), base + extra);
    }
    return shares;                                    // sum == cents, guaranteed
}

Tic-Tac-Toe

Requirements

• NxN board (usually 3); two players alternate placing marks.
• Detect win (row/col/diag of N), draw, illegal move.
• Extensible to other 2-player board games (pluggable Rules).

class Board {
    private final int n;
    private final Mark[][] cells;
    private final int[] rowSum, colSum;   // +1 for X, -1 for O
    private int diag, antiDiag;
    Board(int n){ this.n=n; cells = new Mark[n][n]; rowSum=new int[n]; colSum=new int[n]; }

    Mark place(int r, int c, Mark m) {
        if (cells[r][c] != null) throw new IllegalStateException("taken");
        cells[r][c] = m;
        int delta = m == Mark.X ? 1 : -1;
        rowSum[r] += delta; colSum[c] += delta;
        if (r == c)          diag     += delta;
        if (r + c == n - 1)  antiDiag += delta;
        if (Math.abs(rowSum[r]) == n || Math.abs(colSum[c]) == n
              || Math.abs(diag) == n || Math.abs(antiDiag) == n) return m;
        return Mark.EMPTY;          // EMPTY signals "no win yet"
    }
}

LRU Cache

Requirements

• Fixed capacity; evict the least-recently-used entry on overflow.
• get(k) and put(k,v) both O(1) expected.
• Thread-safe variant for concurrent workloads.

public class LRUCache<K,V> {
    private static class Node<K,V> { K k; V v; Node<K,V> prev, next; }
    private final int cap;
    private final Map<K,Node<K,V>> map = new HashMap<>();
    private final Node<K,V> head = new Node<>(), tail = new Node<>();
    public LRUCache(int cap) { this.cap = cap; head.next = tail; tail.prev = head; }

    public synchronized V get(K k) {
        Node<K,V> n = map.get(k);
        if (n == null) return null;
        moveToFront(n);
        return n.v;
    }
    public synchronized void put(K k, V v) {
        Node<K,V> n = map.get(k);
        if (n != null) { n.v = v; moveToFront(n); return; }
        if (map.size() == cap) {
            Node<K,V> lru = tail.prev;
            unlink(lru); map.remove(lru.k);
        }
        Node<K,V> nn = new Node<>(); nn.k = k; nn.v = v;
        linkFront(nn); map.put(k, nn);
    }
    private void unlink(Node<K,V> n)   { n.prev.next = n.next; n.next.prev = n.prev; }
    private void linkFront(Node<K,V> n){ n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
    private void moveToFront(Node<K,V> n){ unlink(n); linkFront(n); }
}

Rate Limiter

Requirements

• Per-key (user, API key, IP) rate ceiling. Common shapes: fixed window, sliding window, token bucket, leaky bucket.
• Allow bursts up to capacity, then smooth to the refill rate (token bucket).
• Clock must be injectable for testing.

// Token bucket — nano-time refill, no background thread.
public class TokenBucket {
    private final double capacity, refillPerNs;
    private double tokens;
    private long lastNs;
    private final LongSupplier clock;
    public TokenBucket(double cap, double rps, LongSupplier clock) {
        this.capacity = cap; this.refillPerNs = rps / 1e9;
        this.tokens = cap; this.clock = clock; this.lastNs = clock.getAsLong();
    }
    public synchronized boolean tryAcquire(double cost) {
        long now = clock.getAsLong();
        double add = (now - lastNs) * refillPerNs;
        tokens = Math.min(capacity, tokens + add);
        lastNs = now;
        if (tokens >= cost) { tokens -= cost; return true; }
        return false;
    }
}

Notification Service

Requirements

• Send notifications across Email, SMS, Push, Webhook channels.
• Per-channel throttling + retry with exponential backoff + DLQ.
• Templates parameterised by locale; formatted per channel.
• Bulk send (fan-out); idempotent by (userId, eventId, channel).

// Exponential backoff with jitter.
long backoffMs(int attempt) {
    long base = Math.min(30_000, 500L * (1L << attempt));   // 500,1000,2000,... capped
    return ThreadLocalRandom.current().nextLong(base / 2, base);  // full jitter
}

BookMyShow

Requirements

• Cities → Cinemas → Halls → Shows (movie + time + hall).
• Each show has a seat map; users can hold seats for N minutes, then confirm or release.
• Payment integration; idempotent booking.
• No two users can book the same seat (strong consistency on seat state).

// Hold N seats atomically; all-or-nothing.
public boolean hold(List<String> seatIds, String user, Duration ttl) {
    List<String> claimed = new ArrayList<>();
    try {
        for (String id : seatIds) {
            if (!redis.setIfAbsent("seat:" + id, user, ttl)) {
                throw new SeatUnavailableException(id);
            }
            claimed.add(id);
        }
        return true;
    } catch (SeatUnavailableException e) {
        for (String id : claimed) redis.deleteIfValue("seat:" + id, user);
        return false;                        // rollback partial holds
    }
}

Library Management

Requirements

• Catalog of Books; multiple physical BookItems per Book.
• Members borrow, return, reserve; max N concurrent loans per member.
• Late fees accrue per day past due.
• Search by title/author/category.

// Borrow: atomic status flip + loan creation.
public Loan borrow(Member m, BookItem item) {
    if (m.openLoans() >= MAX_LOANS) throw new LoanLimitException();
    if (!item.tryCheckout()) throw new ItemUnavailableException();
    Loan loan = new Loan(m.id(), item.barcode(), LocalDate.now().plusDays(14));
    loanRepo.save(loan);
    return loan;
}
public Money computeFine(Loan l, LocalDate today) {
    long over = ChronoUnit.DAYS.between(l.dueDate(), today);
    return over <= 0 ? Money.ZERO : Money.cents(over * FINE_CENTS_PER_DAY);
}

Thread-Safe Singleton

Three contenders; only two are correct under the Java Memory Model (JMM).

1. Enum singleton (best)

public enum Config { INSTANCE;
    private final Properties p = load();
    public String get(String k){ return p.getProperty(k); }
}
// JVM guarantees enum constants are initialized exactly once + thread-safe.

2. Initialization-on-demand holder

public class Config {
    private Config() {}
    private static class Holder { static final Config INSTANCE = new Config(); }
    public static Config get() { return Holder.INSTANCE; }
    // Class loader enforces one-time init under the JMM.
}

3. Double-checked locking (only with volatile)

public class Config {
    private static volatile Config INSTANCE;   // MUST be volatile
    public static Config get() {
        Config local = INSTANCE;                // read once
        if (local == null) {
            synchronized (Config.class) {
                local = INSTANCE;
                if (local == null) INSTANCE = local = new Config();
            }
        }
        return local;
    }
}

Producer-Consumer on a Bounded Buffer

One of the first concurrency questions asked. Producer thread(s) fill a buffer; consumer thread(s) drain it; both block when the buffer is full/empty.

public class BoundedBuffer<T> {
    private final Object[] buf;
    private int head, tail, size;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull  = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();
    public BoundedBuffer(int cap){ buf = new Object[cap]; }

    public void put(T v) throws InterruptedException {
        lock.lock();
        try {
            while (size == buf.length) notFull.await();   // spin-safe: re-check
            buf[tail] = v; tail = (tail + 1) % buf.length; size++;
            notEmpty.signal();
        } finally { lock.unlock(); }
    }
    @SuppressWarnings("unchecked")
    public T take() throws InterruptedException {
        lock.lock();
        try {
            while (size == 0) notEmpty.await();
            T v = (T) buf[head]; buf[head] = null;
            head = (head + 1) % buf.length; size--;
            notFull.signal();
            return v;
        } finally { lock.unlock(); }
    }
}

Blocking Queue API

Extends the buffer with timeouts and try-variants — the standard BlockingQueue contract.

Mocks, Stubs, Fakes, Spies

// Python fake vs stub
class FakeRepo:                     # fake: actually stores data
    def __init__(self): self.rows = []
    def save(self, r): self.rows.append(r)
    def find(self, id): return next((r for r in self.rows if r.id == id), None)

class StubClock:                    # stub: returns canned value
    def __init__(self, t): self.t = t
    def now(self): return self.t

Dependency Injection Patterns

• Constructor injection (preferred): dependencies are required, immutable, and visible in the signature.
• Setter injection: optional dependencies; avoid for core collaborators (risk of half-constructed objects).
• Method injection: pass the dependency per call; handy for short-lived contexts.
• Service locator (anti): class asks a global registry for its dependencies — hides coupling. Prefer explicit DI.

// Good — constructor injection. Test sets up doubles; production wires real ones.
public class OrderService {
    private final OrderRepo repo;
    private final PaymentGateway pg;
    private final Clock clock;
    public OrderService(OrderRepo repo, PaymentGateway pg, Clock clock) {
        this.repo = repo; this.pg = pg; this.clock = clock;
    }
}

Test Pyramid

Martin Fowler's pyramid: lots of fast unit tests, fewer integration tests, very few end-to-end tests. Inverting it ("ice-cream cone") yields slow, flaky suites.

Pattern vs Use-Case Matrix

Rapid Reference

The Remaining GoF Patterns at a Glance

The first LLD module covered the workhorses (Strategy, Factory, Observer, Singleton, Decorator, State, Adapter, Command). The 23 GoF patterns split into Creational, Structural, and Behavioral. Below are the eleven you still meet in interviews and real code, each with its one-line intent and the situation that should trigger it. Memorize the trigger, not the UML — interviewers reward "this smells like a Chain of Responsibility" far more than a diagram.

Vending Machine — State Pattern Done Right

The vending machine is the canonical State pattern problem. The mistake candidates make is a giant if (state == IDLE) … else if (state == HAS_MONEY) … switch inside every method. Instead, model each state as a class implementing a common interface; the machine delegates every event to its current state, and states decide the next state. This keeps each transition local and testable.

interface State {
    void insertCoin(Machine m, Coin c);
    void selectItem(Machine m, String code);
    void dispense(Machine m);
}

class Machine {
    private State state = new IdleState();
    final Inventory inventory;      // itemCode -> (stock, price)
    int balance = 0;
    void setState(State s) { this.state = s; }
    // events just delegate — no branching here
    void insertCoin(Coin c) { state.insertCoin(this, c); }
    void selectItem(String code) { state.selectItem(this, code); }
}

class HasMoneyState implements State {
    public void selectItem(Machine m, String code) {
        Item it = m.inventory.get(code);
        if (it.stock == 0) throw new SoldOutException(code);
        if (m.balance < it.price) return;         // wait for more coins
        m.setState(new DispenseState(code));       // enough money
        m.dispense(code);
    }
    public void insertCoin(Machine m, Coin c) { m.balance += c.value; }
    public void dispense(Machine m) { /* illegal here */ }
}

• States — Idle, HasMoney, Dispensing, SoldOut. Each is a small class; illegal events throw or no-op.
• Inventory — map of code → (Item, stock, price); decrement under lock (see concurrency section) so two buyers can't drain the last can.
• Change-making — a greedy coin-return is really a Chain of Responsibility or DP subproblem; call it out but time-box it.

ATM — State + Chain of Responsibility for Cash

An ATM combines two patterns: State for the session flow (Idle → CardInserted → Authenticated → TransactionSelected) and Chain of Responsibility for dispensing cash across denominations. Model the bank as a dependency injected behind an interface so the machine logic is testable without a real backend.

// Chain of Responsibility: each node handles its denomination, passes remainder on.
abstract class CashDispenser {
    protected CashDispenser next;
    protected final int denom;          // 2000, 500, 200, 100
    void setNext(CashDispenser n) { this.next = n; }
    void dispense(int amount) {
        if (amount >= denom) {
            int notes = amount / denom;
            int remaining = amount % denom;
            log(notes + " x " + denom);
            if (remaining != 0 && next != null) next.dispense(remaining);
        } else if (next != null) {
            next.dispense(amount);
        } else if (amount > 0) {
            throw new InsufficientDenominationException(amount);
        }
    }
}
// wiring: d2000.setNext(d500); d500.setNext(d200); d200.setNext(d100);

• Entities — Card, Account, BankService (interface), ATM, CashDispenser chain, Transaction (Withdraw/Deposit/BalanceInquiry via Command or subclassing).
• State flow — a failed PIN 3× moves to a CardBlockedState; eject card returns to IdleState.
• Invariant — validate the chain can make the amount (has enough notes) before debiting the account; otherwise you debit but can't dispense.

Chess & Snake-and-Ladder — Board Modeling

Board games test whether you can decompose a domain into cohesive classes. The trap is putting all rules in one Game god-class. Split the board/cell data, the piece movement rules (a Strategy per piece type), and the game loop (turn management, win detection).

abstract class Piece {
    final Color color;
    abstract boolean canMove(Board b, Cell from, Cell to);  // Strategy baked into subclass
}
class Knight extends Piece {
    boolean canMove(Board b, Cell from, Cell to) {
        int dx = Math.abs(from.x - to.x), dy = Math.abs(from.y - to.y);
        boolean lShape = (dx == 2 && dy == 1) || (dx == 1 && dy == 2);
        return lShape && (to.piece == null || to.piece.color != color);
    }
}
class Move { Cell from, to; Piece captured; }   // stored in a Deque for undo (Memento-lite)

Ride-Hailing Dispatch — Matching & Notifications

Uber/Lyft-style dispatch is a systems-flavored LLD: the core loop is "find nearby available drivers, offer the trip, first to accept wins." Model the matching strategy (Strategy pattern — nearest, highest-rated, surge-aware) separately from the notification mechanism (Observer — push offers to driver apps), so you can swap either without touching the other.

interface MatchingStrategy {
    List<Driver> rank(Location pickup, List<Driver> candidates);
}
class NearestDriverStrategy implements MatchingStrategy {
    public List<Driver> rank(Location p, List<Driver> c) {
        return c.stream()
                .sorted(Comparator.comparingDouble(d -> d.location.distanceTo(p)))
                .limit(5).toList();
    }
}
class DispatchService {
    final DriverLocationIndex index;    // geospatial: QuadTree / geohash / H3
    final MatchingStrategy strategy;
    Trip requestRide(Rider r, Location from, Location to) {
        var nearby = index.query(from, /*radiusKm*/ 3);
        var ranked = strategy.rank(from, nearby);
        for (Driver d : ranked) if (offer(d).accepted()) return startTrip(r, d, from, to);
        throw new NoDriverAvailableException();
    }
}

• Geo index — the make-or-break detail. A linear scan of all drivers is O(n); use a QuadTree, geohash buckets, or Uber's H3 hexagons for O(log n) / O(1)-bucket nearest-neighbor queries.
• State machine — Trip: REQUESTED → ASSIGNED → STARTED → COMPLETED / CANCELLED. Reuse the State pattern.
• Concurrency — a driver must be offered to one trip at a time; lock/CAS the driver's status to AVAILABLE→OFFERED to avoid double-assignment.

Meeting Scheduler & Deck of Cards

Two smaller staples. Meeting Scheduler is really an interval-overlap problem wrapped in objects; Deck of Cards is the textbook Iterator + Factory exercise and a common warm-up before Blackjack/Poker follow-ups.

// Meeting Scheduler — the crux is conflict detection + room allocation.
class Interval { LocalDateTime start, end;
    boolean overlaps(Interval o) { return start.isBefore(o.end) && o.start.isBefore(end); }
}
class Room { int id; TreeMap<LocalDateTime, Interval> bookings; }  // keyed by start for O(log n) neighbor lookup
class Scheduler {
    Optional<Room> book(List<User> attendees, Interval slot) {
        if (attendees.stream().anyMatch(u -> u.isBusy(slot))) return Optional.empty();
        Room free = rooms.stream().filter(r -> !conflicts(r, slot)).findFirst().orElse(null);
        if (free == null) return Optional.empty();
        free.bookings.put(slot.start, slot);
        attendees.forEach(u -> u.notify(new Invite(slot)));  // Observer
        return Optional.of(free);
    }
}
// Deck of Cards — Factory builds 52; Iterator hides the array.
class Deck implements Iterable<Card> {
    private final List<Card> cards = new ArrayList<>();
    Deck() { for (Suit s : Suit.values()) for (Rank r : Rank.values()) cards.add(new Card(s, r)); }
    void shuffle() { Collections.shuffle(cards); }
    public Iterator<Card> iterator() { return cards.iterator(); }  // deal without exposing the list
}

• Scheduler entities — User (own calendar), Room, Meeting, Interval, Scheduler. Store each user's bookings in a sorted structure so conflict checks are O(log n), not O(bookings).
• Deck follow-ups — "deal to N players", "model Blackjack" → add Hand, a Game, and scoring; Card stays an immutable Flyweight if you share the 52 instances.

Driving the 45-Minute LLD Interview

LLD interviews are graded on process as much as the final classes. A repeatable script beats raw pattern knowledge: clarify, scope, model, then deepen. Budget your 45 minutes explicitly and narrate as you go so the interviewer can steer.

1. Clarify requirements (5 min) — Ask: who are the actors? What are the core use cases? What's in vs out of scope? "Should the vending machine handle refunds and multiple currencies, or just single-coin single-item?" Write the agreed functional requirements down.
2. Define scope & core entities (5 min) — Name the nouns → candidate classes; name the verbs → methods/services. Explicitly say "I'll leave payment gateway integration out and stub it behind an interface."
3. Drive the class model live (20 min) — Sketch classes, fields, and key method signatures. State relationships (has-a vs is-a). Introduce a pattern only when a force demands it ("moves vary per piece → Strategy"). Talk through one end-to-end flow to prove the model works.
4. Deepen: concurrency, edge cases, extensibility (10 min) — Address the interesting hard part (race on last item, deadlock, new payment type). Show your design absorbs a new requirement with minimal change (Open/Closed).
5. Wrap (last few min) — Recap classes, note what you'd add with more time. Never leave a dangling half-drawn diagram.

• Time-boxing rule — if you're 20 minutes in and still debating a coin-return algorithm, you've mismanaged the clock. Say "I'll stub this and revisit if time permits" and move to the class model — a complete skeleton beats one perfect corner.
• Signal, don't lecture — name the pattern and why, in one sentence, then use it. Don't recite the GoF definition.

Concurrency in LLD — Locks, Ordering & Async

Once your class model works single-threaded, the senior-level follow-up is "now make it thread-safe." Three tools cover almost every LLD concurrency question: consistent lock ordering (deadlock avoidance), read-write locks (read-heavy shared state), and CompletableFuture (async composition without blocking threads).

// DEADLOCK: thread A locks acct1 then acct2; thread B locks acct2 then acct1 -> both stuck.
// FIX: impose a global order — always lock the lower id first.
void transfer(Account a, Account b, int amount) {
    Account first  = a.id < b.id ? a : b;
    Account second = a.id < b.id ? b : a;
    synchronized (first) {
        synchronized (second) {
            a.debit(amount);
            b.credit(amount);
        }
    }
}

// READ-WRITE LOCK: many concurrent readers, exclusive writer — ideal for an inventory read a lot, updated rarely.
class Inventory {
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    int stockOf(String code) {
        lock.readLock().lock();
        try { return map.get(code).stock; } finally { lock.readLock().unlock(); }
    }
    void restock(String code, int n) {
        lock.writeLock().lock();
        try { map.get(code).stock += n; } finally { lock.writeLock().unlock(); }
    }
}

// ASYNC: compose non-blocking calls; total latency = max(parts), not sum.
CompletableFuture<Trip> book(Rider r) {
    var driver  = CompletableFuture.supplyAsync(() -> dispatch.findDriver(r));
    var pricing = CompletableFuture.supplyAsync(() -> pricingSvc.quote(r));
    return driver.thenCombine(pricing, (d, price) -> startTrip(r, d, price));
}

• Deadlock's four conditions — mutual exclusion, hold-and-wait, no preemption, circular wait. Breaking any one prevents it; lock ordering breaks circular wait and is the go-to answer.
• Read-write lock — allows N concurrent readers OR 1 writer. Only a win when reads vastly outnumber writes; otherwise the bookkeeping overhead loses to a plain synchronized.
• Atomics over locks — for a single counter (seats left, stock), an AtomicInteger with compareAndSet is lock-free and faster than a mutex.
• CompletableFuture — thenCombine for fan-in, thenCompose for dependent chaining, allOf to await a batch. Frees the thread instead of blocking it.

Structural patterns: composing objects, not creating them

Structural GoF patterns describe how classes and objects are composed into larger structures while keeping those structures flexible and efficient. Bridge, Composite, Flyweight, and Facade each attack a different composition problem: exploding subclass hierarchies, part-whole trees, memory blow-up, and subsystem complexity.

• Bridge splits one hierarchy into two (abstraction & implementation) so they vary independently.
• Composite builds trees where a leaf and a container share one interface.
• Flyweight shares immutable intrinsic state across many instances to cut memory.
• Facade wraps a messy subsystem behind one simple entry point.

Bridge — decouple abstraction from implementation

Intent: separate an abstraction from its implementation so the two can vary independently, avoiding a Cartesian-product subclass explosion (e.g. CircleVector, CircleRaster, SquareVector…).

interface Renderer {                 // the "implementation" side
    String renderCircle(double r);
}
class VectorRenderer implements Renderer {
    public String renderCircle(double r) { return "vector circle r=" + r; }
}
class RasterRenderer implements Renderer {
    public String renderCircle(double r) { return "pixels circle r=" + r; }
}

abstract class Shape {               // the "abstraction" side
    protected final Renderer renderer;   // the bridge reference
    Shape(Renderer renderer) { this.renderer = renderer; }
    abstract String draw();
}
class Circle extends Shape {
    private final double radius;
    Circle(Renderer r, double radius) { super(r); this.radius = radius; }
    String draw() { return renderer.renderCircle(radius); }
}
// new Circle(new RasterRenderer(), 5).draw();  -> mix & match freely

When to use: two dimensions vary independently (shape × renderer, message × transport, remote × platform). Interview use case: a notification system where Notification (Alert/Reminder) bridges to Channel (SMS/Email/Push) — 2×3 combos with 5 classes, not 6.

Composite — treat leaves and containers uniformly

Intent: compose objects into tree structures and let clients treat individual objects and compositions of objects the same way.

import java.util.*;

interface FileNode {                 // component
    int sizeBytes();
    String name();
}
class FileLeaf implements FileNode { // leaf
    private final String name; private final int bytes;
    FileLeaf(String name, int bytes) { this.name = name; this.bytes = bytes; }
    public int sizeBytes() { return bytes; }
    public String name() { return name; }
}
class Directory implements FileNode { // composite
    private final String name;
    private final List<FileNode> children = new ArrayList<>();
    Directory(String name) { this.name = name; }
    Directory add(FileNode n) { children.add(n); return this; }
    public int sizeBytes() {          // recurse uniformly
        int total = 0;
        for (FileNode c : children) total += c.sizeBytes();
        return total;
    }
    public String name() { return name; }
}
// new Directory("root").add(new FileLeaf("a.txt", 100)).sizeBytes();

When to use: any part-whole hierarchy where clients should ignore the leaf/branch distinction. Interview use case: file systems, org charts, UI widget trees, arithmetic expression trees, or a menu of menus.

Flyweight — share intrinsic state to save memory

Intent: use sharing to support large numbers of fine-grained objects efficiently by separating intrinsic state (shared, immutable) from extrinsic state (passed in per call).

import java.util.*;

final class Glyph {                  // flyweight: intrinsic state only
    private final char symbol;       // shared across every 'a' on screen
    private final String font;
    Glyph(char symbol, String font) { this.symbol = symbol; this.font = font; }
    void draw(int x, int y) {        // extrinsic state passed in
        System.out.println(symbol + "@" + font + " (" + x + "," + y + ")");
    }
}
class GlyphFactory {
    private final Map<String, Glyph> pool = new HashMap<>();
    Glyph get(char c, String font) {
        return pool.computeIfAbsent(c + "|" + font, k -> new Glyph(c, font));
    }
    int distinctFlyweights() { return pool.size(); }
}
// 1M characters on screen -> only ~100 Glyph objects in the pool

When to use: millions of objects that share a small set of distinct values. Interview use case: characters in a text editor, tree sprites in a game map, or particle systems — position/color stay extrinsic, the sprite/glyph is pooled.

Facade — one simple door to a complex subsystem

Intent: provide a unified higher-level interface to a set of interfaces in a subsystem, making it easier to use. It does not hide the subsystem — advanced clients can still reach past it.

class Amplifier { void on() {} void volume(int v) {} }
class Projector { void on() {} void widescreen() {} }
class Lights    { void dim(int pct) {} }

class HomeTheaterFacade {
    private final Amplifier amp; private final Projector proj; private final Lights lights;
    HomeTheaterFacade(Amplifier a, Projector p, Lights l) { amp = a; proj = p; lights = l; }

    void watchMovie() {              // one call orchestrates the subsystem
        lights.dim(10);
        proj.on(); proj.widescreen();
        amp.on(); amp.volume(5);
    }
    void endMovie() { amp.on(); proj.on(); lights.dim(100); }
}
// client: new HomeTheaterFacade(a, p, l).watchMovie();

When to use: a subsystem is complex, layered, or you want to reduce coupling between clients and internals. Interview use case: a payment CheckoutFacade that hides fraud check + inventory hold + gateway charge + email receipt behind placeOrder(); or an SDK wrapping a raw REST/gRPC API.

Comparison — Bridge vs Composite vs Flyweight vs Facade

A quick decision table for which structural pattern the problem is really asking for.

Chain of Responsibility — pass the request down a chain

Intent: avoid coupling a sender to a receiver by giving multiple objects a chance to handle the request, passing it along a chain until one handles it.

abstract class Approver {
    protected Approver next;
    Approver linkTo(Approver n) { this.next = n; return n; }
    abstract void handle(double amount);
    protected void pass(double amount) {
        if (next != null) next.handle(amount);
        else System.out.println("No one could approve " + amount);
    }
}
class Manager extends Approver {
    void handle(double a) {
        if (a <= 1000) System.out.println("Manager approved " + a);
        else pass(a);
    }
}
class Director extends Approver {
    void handle(double a) {
        if (a <= 10000) System.out.println("Director approved " + a);
        else pass(a);
    }
}
// Approver chain = new Manager(); chain.linkTo(new Director());
// chain.handle(5000);  -> Director approves

Use case: approval workflows, servlet/middleware filter pipelines, event bubbling, logging levels, and exception handlers.

Mediator — centralize many-to-many communication

Intent: define an object that encapsulates how a set of objects interact, so they refer to the mediator instead of to each other, reducing N² coupling to N.

import java.util.*;

interface ChatMediator { void send(String msg, User from); void register(User u); }
class ChatRoom implements ChatMediator {
    private final List<User> users = new ArrayList<>();
    public void register(User u) { users.add(u); }
    public void send(String msg, User from) {
        for (User u : users) if (u != from) u.receive(msg);
    }
}
abstract class User {
    protected final ChatMediator room;
    User(ChatMediator room) { this.room = room; room.register(this); }
    void send(String m) { room.send(m, this); }
    abstract void receive(String m);
}
class BasicUser extends User {
    private final String name;
    BasicUser(ChatMediator r, String name) { super(r); this.name = name; }
    void receive(String m) { System.out.println(name + " got: " + m); }
}

Use case: chat rooms, air-traffic control, and UI dialogs where widgets coordinate (enabling/disabling) through a controller rather than wiring to each other.

Memento — capture and restore state without breaking encapsulation

Intent: capture an object's internal state so it can be restored later, without exposing that state to the outside world. The originator creates mementos; a caretaker stores them.

import java.util.*;

class Editor {                        // originator
    private String content = "";
    void type(String s) { content += s; }
    String read() { return content; }
    Memento save() { return new Memento(content); }
    void restore(Memento m) { this.content = m.state; }

    static final class Memento {      // opaque snapshot
        private final String state;
        private Memento(String state) { this.state = state; }
    }
}
class History {                       // caretaker
    private final Deque<Editor.Memento> stack = new ArrayDeque<>();
    void push(Editor.Memento m) { stack.push(m); }
    Editor.Memento pop() { return stack.pop(); }
}

Use case: undo/redo, transaction rollback, game checkpoints/save-states, and form draft snapshots. Frequently paired with Command (mod14).

Visitor — add operations to a hierarchy without editing it

Intent: represent an operation to be performed on the elements of an object structure; you can define a new operation without changing the classes of the elements it operates on (double dispatch).

interface Visitor { void visitCircle(Circle c); void visitSquare(Square s); }
interface Element { void accept(Visitor v); }

class Circle implements Element {
    final double r; Circle(double r) { this.r = r; }
    public void accept(Visitor v) { v.visitCircle(this); }   // dispatch 1
}
class Square implements Element {
    final double side; Square(double side) { this.side = side; }
    public void accept(Visitor v) { v.visitSquare(this); }
}
class AreaVisitor implements Visitor {                        // new op, no element edits
    double total = 0;
    public void visitCircle(Circle c) { total += Math.PI * c.r * c.r; }
    public void visitSquare(Square s) { total += s.side * s.side; }
}

Use case: compilers/AST traversal (type-check, codegen, pretty-print as separate visitors), document exporters, and reporting over a fixed class hierarchy.

Template Method & Iterator — fixed skeleton, and uniform traversal

Template Method intent: define the skeleton of an algorithm in a base method, deferring some steps to subclasses so they can vary steps without changing the algorithm's structure. Iterator intent: provide sequential access to elements of a collection without exposing its internal representation.

abstract class DataPipeline {         // Template Method
    final void run() {                // fixed skeleton, final = not overridable
        load(); transform(); save();
    }
    abstract void load();
    abstract void transform();
    void save() { System.out.println("default save"); }  // hook with default
}

import java.util.*;
class Range implements Iterable<Integer> {   // Iterator
    private final int n; Range(int n) { this.n = n; }
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            int i = 0;
            public boolean hasNext() { return i < n; }
            public Integer next() { return i++; }
        };
    }
}
// for (int x : new Range(3)) { ... }   // hasNext()/next() hidden from client

Use cases: Template Method — frameworks with lifecycle hooks (JUnit setUp/tearDown, servlet request handling). Iterator — any custom collection you want usable in a for-each loop.

Interpreter — evaluate a grammar as a class tree

Intent: given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language. Each grammar rule becomes a class; the parse tree is a Composite.

interface Expr { int eval(); }
class Num implements Expr {
    private final int v; Num(int v) { this.v = v; }
    public int eval() { return v; }
}
class Add implements Expr {
    private final Expr l, r; Add(Expr l, Expr r) { this.l = l; this.r = r; }
    public int eval() { return l.eval() + r.eval(); }
}
class Mul implements Expr {
    private final Expr l, r; Mul(Expr l, Expr r) { this.l = l; this.r = r; }
    public int eval() { return l.eval() * r.eval(); }
}
// (2 + 3) * 4  ->  new Mul(new Add(new Num(2), new Num(3)), new Num(4)).eval() == 20

Use case: simple DSLs — rule engines, SQL-like filters, regex matchers, calculator/boolean expression evaluators. For anything beyond a tiny grammar, reach for a real parser generator instead.

Comparison — the seven behavioral patterns at a glance

One row per pattern: what varies, the collaborators, and a canonical use case.

Thread-safe Singleton — DCL, holder idiom, and enum

The Singleton is the pattern most often botched under concurrency. A naive lazy getInstance() can construct two instances if two threads race the null check. Three correct idioms exist; know when each applies.

// 1) Double-checked locking — needs volatile, else a thread can see a
//    half-constructed object due to instruction reordering.
class ConfigDCL {
    private static volatile ConfigDCL instance;   // volatile is mandatory
    private ConfigDCL() {}
    static ConfigDCL get() {
        if (instance == null) {                   // 1st check (no lock)
            synchronized (ConfigDCL.class) {
                if (instance == null) {           // 2nd check (locked)
                    instance = new ConfigDCL();
                }
            }
        }
        return instance;
    }
}

// 2) Initialization-on-demand holder — lazy, no locks, JVM guarantees
//    the class is loaded exactly once on first access to Holder.
class ConfigHolder {
    private ConfigHolder() {}
    private static class Holder { static final ConfigHolder I = new ConfigHolder(); }
    static ConfigHolder get() { return Holder.I; }
}

// 3) Enum singleton — simplest; serialization- and reflection-safe.
enum ConfigEnum {
    INSTANCE;
    void doWork() { /* ... */ }
}

Rule of thumb: prefer the holder idiom for lazy init or the enum for absolute safety; reach for DCL only when construction must depend on runtime parameters.

Thread-safe Observer

The Observer/subject pattern breaks under concurrency in two spots: mutating the listener list while iterating it (throws ConcurrentModificationException), and holding a lock while calling out to unknown observer code (deadlock risk). Use a copy-on-write list and notify outside the lock.

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

interface Observer<T> { void onNext(T value); }

class Subject<T> {
    // CopyOnWriteArrayList: iteration never throws CME; writes are rare.
    private final List<Observer<T>> observers = new CopyOnWriteArrayList<>();

    void subscribe(Observer<T> o)   { observers.add(o); }
    void unsubscribe(Observer<T> o) { observers.remove(o); }

    void publish(T value) {
        // No external lock held while calling observer code -> no callback deadlock.
        for (Observer<T> o : observers) o.onNext(value);
    }
}

When observer counts are large and writes frequent, prefer a concurrent snapshot strategy or a dedicated event bus with its own dispatch thread rather than copy-on-write.

Producer-Consumer with a blocking queue

The bounded blocking queue is the canonical concurrency LLD building block: producers put (blocking when full), consumers take (blocking when empty). It decouples rates and provides natural backpressure.

import java.util.concurrent.*;

class WorkQueue {
    private final BlockingQueue<Runnable> queue = new ArrayBlockingQueue<>(1000);

    void produce(Runnable task) throws InterruptedException {
        queue.put(task);              // blocks if the queue is full (backpressure)
    }
    void startConsumer() {
        Thread worker = new Thread(() -> {
            try {
                while (!Thread.currentThread().isInterrupted()) {
                    Runnable task = queue.take();   // blocks if empty
                    task.run();
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt(); // restore the flag, exit
            }
        });
        worker.start();
    }
}

In practice a ThreadPoolExecutor wraps exactly this: a work queue plus a pool of consumer threads. Mentioning that mapping scores points.

Language idiom contrasts — Java vs C++ vs Python

LLD interviewers often ask you to "do this in your language." The same OOP concept has different idiomatic homes. Know the mapping.

# Python idioms: ABC for a contract, __slots__ for compact objects
from abc import ABC, abstractmethod

class Shape(ABC):
    __slots__ = ()                      # no per-instance __dict__
    @abstractmethod
    def area(self) -> float: ...

class Circle(Shape):
    __slots__ = ("r",)                  # memory-lean; blocks stray attributes
    def __init__(self, r): self.r = r
    def area(self): return 3.14159 * self.r * self.r

Immutability — the cheapest thread-safety

An immutable object needs no locks: if state never changes after construction, no two threads can conflict. This is why value objects, keys, and config should default to immutable.

• Java: make the class final, all fields private final, no setters, and defensively copy any mutable references in and out.
• Records (Java 16+) give you immutable data carriers for free: record Point(int x, int y) {}.
• C++: const members and passing const&; Python: frozen dataclasses or tuples/namedtuples.
• Copy-on-write gives an "update" by returning a new instance, leaving the original safe to share.

final class Money {                    // immutable value object
    private final long cents;
    private final String currency;
    Money(long cents, String currency) { this.cents = cents; this.currency = currency; }
    Money plus(Money o) {             // returns a NEW object, never mutates
        if (!currency.equals(o.currency)) throw new IllegalArgumentException("mix");
        return new Money(cents + o.cents, currency);
    }
}

Concurrency primitives you actually reach for in LLD

Beyond synchronized, a small toolkit covers most LLD concurrency asks. Choose the lightest tool that fits.

import java.util.concurrent.atomic.AtomicLong;
class IdGenerator {                   // lock-free, contention-friendly
    private final AtomicLong counter = new AtomicLong(0);
    long next() { return counter.incrementAndGet(); }  // CAS under the hood
}

LRU cache — HashMap + doubly-linked list, O(1)

The LRU (Least Recently Used) cache is the most-asked LLD problem. The trick is combining two structures: a hash map for O(1) lookup and a doubly-linked list for O(1) recency reordering and eviction. On every access, move the node to the front; evict from the tail when full.

import java.util.*;

class LRUCache<K, V> {
    private static class Node<K, V> {
        K key; V val; Node<K, V> prev, next;
        Node(K k, V v) { key = k; val = v; }
    }
    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null); // MRU sentinel
    private final Node<K, V> tail = new Node<>(null, null); // LRU sentinel

    LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail; tail.prev = head;
    }
    private void remove(Node<K, V> n) {
        n.prev.next = n.next; n.next.prev = n.prev;
    }
    private void addFront(Node<K, V> n) {
        n.next = head.next; n.prev = head;
        head.next.prev = n; head.next = n;
    }
    V get(K key) {
        Node<K, V> n = map.get(key);
        if (n == null) return null;
        remove(n); addFront(n);         // mark most-recently-used
        return n.val;
    }
    void put(K key, V val) {
        Node<K, V> n = map.get(key);
        if (n != null) { n.val = val; remove(n); addFront(n); return; }
        if (map.size() == capacity) {   // evict LRU (node before tail)
            Node<K, V> lru = tail.prev;
            remove(lru); map.remove(lru.key);
        }
        Node<K, V> fresh = new Node<>(key, val);
        addFront(fresh); map.put(key, fresh);
    }
}

Sentinel head/tail nodes remove all null-checks in the list surgery — a detail interviewers look for.

LFU cache — frequency buckets, O(1)

LFU (Least Frequently Used) evicts the item accessed the fewest times, breaking ties by recency. The O(1) design keeps a map of frequency → an ordered list (a per-frequency LRU) plus a running minFreq pointer so eviction is constant time.

import java.util.*;

class LFUCache {
    private final int capacity;
    private int minFreq = 0;
    private final Map<Integer, Integer> vals = new HashMap<>();   // key -> value
    private final Map<Integer, Integer> freqs = new HashMap<>();  // key -> freq
    // freq -> keys at that freq, in insertion (recency) order
    private final Map<Integer, LinkedHashSet<Integer>> buckets = new HashMap<>();

    LFUCache(int capacity) { this.capacity = capacity; }

    private void bump(int key) {
        int f = freqs.get(key);
        freqs.put(key, f + 1);
        buckets.get(f).remove(key);
        if (buckets.get(f).isEmpty()) {
            buckets.remove(f);
            if (minFreq == f) minFreq++;          // whole bucket drained
        }
        buckets.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key);
    }
    Integer get(int key) {
        if (!vals.containsKey(key)) return null;
        bump(key);
        return vals.get(key);
    }
    void put(int key, int value) {
        if (capacity == 0) return;
        if (vals.containsKey(key)) { vals.put(key, value); bump(key); return; }
        if (vals.size() == capacity) {            // evict LFU, oldest within tie
            int evict = buckets.get(minFreq).iterator().next();
            buckets.get(minFreq).remove(evict);
            vals.remove(evict); freqs.remove(evict);
        }
        vals.put(key, value); freqs.put(key, 1);
        buckets.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key);
        minFreq = 1;                              // new item always has freq 1
    }
}

Tie-break: the LinkedHashSet preserves recency within a frequency, so among equally-cold keys the least-recently-used one goes first.

In-memory key-value store with TTL / expiry

A KV store with expiry stores each value alongside an absolute expiry timestamp. Two strategies free memory: lazy expiry (check on read) and active expiry (a background sweep). Redis famously uses both.

import java.util.*;
import java.util.concurrent.*;

class KVStore<K, V> {
    private static class Entry<V> { V value; long expiryMs; }
    private final ConcurrentHashMap<K, Entry<V>> map = new ConcurrentHashMap<>();

    void put(K key, V value, long ttlMs) {
        Entry<V> e = new Entry<>();
        e.value = value;
        e.expiryMs = (ttlMs <= 0) ? Long.MAX_VALUE : System.currentTimeMillis() + ttlMs;
        map.put(key, e);
    }
    V get(K key) {                                // lazy expiry
        Entry<V> e = map.get(key);
        if (e == null) return null;
        if (System.currentTimeMillis() >= e.expiryMs) {
            map.remove(key, e);                   // atomic remove-if-same
            return null;
        }
        return e.value;
    }
    // Active expiry: schedule a sweep to reclaim memory from never-read keys.
    void startSweeper(ScheduledExecutorService ses) {
        ses.scheduleAtFixedRate(() -> {
            long now = System.currentTimeMillis();
            map.forEach((k, e) -> { if (now >= e.expiryMs) map.remove(k, e); });
        }, 1, 1, TimeUnit.SECONDS);
    }
}

Logging framework — levels, appenders, formatters

A logging framework is a Strategy/Composite showcase. A Logger filters by level, formats each event with a formatter, and writes it to one or more appenders (console, file, network). Each responsibility is a pluggable interface.

import java.util.*;

enum Level { DEBUG(0), INFO(1), WARN(2), ERROR(3);
    final int rank; Level(int r) { rank = r; }
}
interface Formatter { String format(Level level, String msg); }
class SimpleFormatter implements Formatter {
    public String format(Level level, String msg) {
        return System.currentTimeMillis() + " [" + level + "] " + msg;
    }
}
interface Appender { void append(String line); }
class ConsoleAppender implements Appender {
    public void append(String line) { System.out.println(line); }
}

class Logger {
    private final Level threshold;
    private final Formatter formatter;
    private final List<Appender> appenders;
    Logger(Level threshold, Formatter f, List<Appender> a) {
        this.threshold = threshold; this.formatter = f; this.appenders = a;
    }
    void log(Level level, String msg) {
        if (level.rank < threshold.rank) return;   // filter first: cheap
        String line = formatter.format(level, msg);
        for (Appender a : appenders) a.append(line);
    }
    void info(String m)  { log(Level.INFO, m); }
    void error(String m) { log(Level.ERROR, m); }
}

Filtering by level before formatting avoids paying string-building cost for suppressed messages — the reason real frameworks guard with isDebugEnabled().

Async logging — decouple the hot path from I/O

Synchronous file/network appenders block the calling thread on I/O. The fix reuses the producer-consumer pattern (mod12): the caller enqueues a log event; a dedicated background thread drains the queue and writes.

import java.util.concurrent.*;

class AsyncAppender implements Appender, AutoCloseable {
    private final BlockingQueue<String> queue = new LinkedBlockingQueue<>(10_000);
    private final Appender delegate;             // e.g. a FileAppender
    private final Thread worker;
    private volatile boolean running = true;

    AsyncAppender(Appender delegate) {
        this.delegate = delegate;
        worker = new Thread(() -> {
            while (running || !queue.isEmpty()) {
                try { delegate.append(queue.take()); }
                catch (InterruptedException e) { Thread.currentThread().interrupt(); break; }
            }
        });
        worker.start();
    }
    public void append(String line) {
        if (!queue.offer(line)) { /* queue full: drop or block per policy */ }
    }
    public void close() { running = false; worker.interrupt(); }
}

Comparison — eviction and expiry policies

Caches differ mainly in what they throw away first. Match the policy to the access pattern.

Text editor undo/redo — Command + Memento

An undo/redo editor is the canonical Command + Memento problem. Each edit is a Command object that knows how to execute and undo itself; two stacks track history. When the command needs to restore prior state, it carries a Memento (mod11).

import java.util.*;

class Document {                       // receiver
    private final StringBuilder buffer = new StringBuilder();
    void insert(int pos, String s) { buffer.insert(pos, s); }
    void delete(int pos, int len)  { buffer.delete(pos, pos + len); }
    String text() { return buffer.toString(); }
}
interface Command { void execute(); void undo(); }

class InsertCommand implements Command {
    private final Document doc; private final int pos; private final String text;
    InsertCommand(Document doc, int pos, String text) {
        this.doc = doc; this.pos = pos; this.text = text;
    }
    public void execute() { doc.insert(pos, text); }
    public void undo()    { doc.delete(pos, text.length()); }  // inverse op
}

class Editor {
    private final Document doc = new Document();
    private final Deque<Command> undo = new ArrayDeque<>();
    private final Deque<Command> redo = new ArrayDeque<>();

    void run(Command c) { c.execute(); undo.push(c); redo.clear(); } // new edit voids redo
    void undo() { if (!undo.isEmpty()) { Command c = undo.pop(); c.undo(); redo.push(c); } }
    void redo() { if (!redo.isEmpty()) { Command c = redo.pop(); c.execute(); undo.push(c); } }
    String text() { return doc.text(); }
}

Design choice: for invertible ops (insert ↔ delete) each command stores just the inverse. For lossy ops (e.g. "format all") store a Memento snapshot instead. Real editors mix both.

In-memory file system — node tree + path resolution

An in-memory file system is a Composite (mod10): directories contain files or sub-directories. The core operations are path resolution (walk /a/b/c segment by segment) and lazy creation (mkdir -p semantics).

import java.util.*;

class FSNode {
    final String name;
    final boolean isDir;
    String content = "";                          // files only
    final Map<String, FSNode> children = new TreeMap<>(); // sorted for ls
    FSNode(String name, boolean isDir) { this.name = name; this.isDir = isDir; }
}
class FileSystem {
    private final FSNode root = new FSNode("/", true);

    private FSNode resolve(String path, boolean createDirs) {
        FSNode cur = root;
        for (String seg : path.split("/")) {
            if (seg.isEmpty()) continue;          // skip leading / and //
            FSNode next = cur.children.get(seg);
            if (next == null) {
                if (!createDirs) return null;
                next = new FSNode(seg, true);
                cur.children.put(seg, next);      // mkdir -p
            }
            cur = next;
        }
        return cur;
    }
    void mkdir(String path) { resolve(path, true); }

    List<String> ls(String path) {
        FSNode n = resolve(path, false);
        if (n == null) return List.of();
        if (!n.isDir) return List.of(n.name);     // ls of a file -> itself
        return new ArrayList<>(n.children.keySet()); // sorted by TreeMap
    }
    void writeFile(String path, String content) {
        int cut = path.lastIndexOf('/');
        FSNode dir = resolve(path.substring(0, cut), true);
        String fname = path.substring(cut + 1);
        FSNode f = dir.children.computeIfAbsent(fname, k -> new FSNode(k, false));
        f.content = content;
    }
    String readFile(String path) {
        FSNode f = resolve(path, false);
        return (f == null || f.isDir) ? null : f.content;
    }
}

Using a TreeMap for children gives sorted ls output for free — a small touch interviewers notice.

Pub/Sub broker — topics, subscribers, delivery

A pub/sub message broker decouples producers from consumers through named topics. Publishers send to a topic; the broker fans each message out to every current subscriber of that topic. The core is a topic → subscriber-list registry plus a delivery loop.

import java.util.*;
import java.util.concurrent.*;

interface Subscriber { void onMessage(String topic, String payload); }

class Broker {
    // topic -> set of subscribers; CopyOnWrite tolerates subscribe during publish
    private final Map<String, Set<Subscriber>> topics = new ConcurrentHashMap<>();

    void subscribe(String topic, Subscriber s) {
        topics.computeIfAbsent(topic, t -> ConcurrentHashMap.newKeySet()).add(s);
    }
    void unsubscribe(String topic, Subscriber s) {
        Set<Subscriber> subs = topics.get(topic);
        if (subs != null) subs.remove(s);
    }
    void publish(String topic, String payload) {
        Set<Subscriber> subs = topics.get(topic);
        if (subs == null) return;                  // no subscribers -> drop
        for (Subscriber s : subs) {
            try { s.onMessage(topic, payload); }
            catch (RuntimeException e) { /* isolate: one bad sub can't stall others */ }
        }
    }
}

Delivery semantics to discuss: at-most-once (fire and forget, above), at-least-once (retry until ack), exactly-once (dedup + idempotency). State which you're building and why.

Pub/Sub — per-subscriber queues, async delivery, backpressure

Calling subscribers inline (as above) means one slow consumer blocks the publisher and every other subscriber. The fix: give each subscriber its own bounded queue and a delivery thread. When a queue fills, you must choose a backpressure policy.

import java.util.concurrent.*;

class Subscription implements AutoCloseable {
    private final BlockingQueue<String> queue = new ArrayBlockingQueue<>(1000);
    private final Thread worker;
    private volatile boolean running = true;

    Subscription(Subscriber s, String topic) {
        worker = new Thread(() -> {
            while (running) {
                try { s.onMessage(topic, queue.take()); }
                catch (InterruptedException e) { break; }
            }
        });
        worker.start();
    }
    // Backpressure policy = what offer() does when the queue is full:
    boolean deliver(String payload) {
        return queue.offer(payload);   // returns false if full -> caller drops or blocks
    }
    public void close() { running = false; worker.interrupt(); }
}

• Block — queue.put() stalls the publisher; slowest consumer sets the pace (strong coupling).
• Drop — offer() returns false, message discarded; protects the broker, loses data.
• Buffer to disk / overflow topic — spill excess so memory stays bounded but nothing is lost.
• Slow-consumer eviction — Kafka-style: fast consumers proceed, laggards fall behind their own offset.

Design comparison — the patterns behind each system

These three LLD problems recycle the same handful of patterns. Recognizing the reuse is what makes them fast to design under time pressure.