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