OOD / Low-Level Design

STEP 1: Clarify requirements & scope
   - What features are in / out of scope? (Say "I'll assume ... — is that OK?")
   - Functional: what must the system DO?
   - Non-functional: concurrency? persistence? scale? (usually keep in-memory, single process)
   - Nail down 3-5 concrete use cases before writing any class.

STEP 2: Identify core objects / entities (the NOUNS)
   - Scan requirements for nouns -> candidate classes.
   - "A parking lot HAS spots, a spot HOLDS a vehicle, a ticket TRACKS an entry."
   - Drop nouns that are just attributes (e.g. "color" is a field, not a class).

STEP 3: Define relationships (has-a / is-a, cardinality)
   - is-a  -> inheritance / interface implementation (Car IS-A Vehicle)
   - has-a -> composition / aggregation (ParkingLot HAS-A List<Level>)
   - cardinality: 1-to-1, 1-to-many, many-to-many
   - Prefer COMPOSITION over inheritance when unsure.

STEP 4: Design classes with fields, key methods & interfaces
   - Give each class ONE clear responsibility (SRP).
   - Program to interfaces, not implementations.
   - Enums for fixed sets (VehicleType, SpotType, Direction).
   - Sketch method signatures; don't implement everything.

STEP 5: Discuss design patterns, extensibility & edge cases
   - Which pattern fits? (Strategy for pricing, Factory for creation, State for lifecycle...)
   - "If we add feature X later, only class Y changes" (Open/Closed).
   - Edge cases: full capacity, invalid input, concurrency, null states.

Requirement sentence:
  "A customer inserts coins into a vending machine to buy a product."
                ^nouns: Customer, Coin, VendingMachine, Product
                ^verbs: insert, buy  -> methods on VendingMachine

  -> class VendingMachine { void insertCoin(Coin c); Product dispense(); }
  -> enum Coin { PENNY, NICKEL, DIME, QUARTER }
  -> class Product { String name; int price; }

// java
// D — Dependency Inversion: depend on the INTERFACE, inject the concretion.
interface PaymentProcessor { boolean pay(double amount); }

class CardProcessor implements PaymentProcessor {
    public boolean pay(double amount) { /* ... */ return true; }
}

class Checkout {
    private final PaymentProcessor processor;         // abstraction, not concrete
    Checkout(PaymentProcessor processor) {            // injected
        this.processor = processor;
    }
    boolean buy(double amount) { return processor.pay(amount); }
}
// Swap CardProcessor -> WalletProcessor WITHOUT touching Checkout (Open/Closed too).

// java
interface PricingStrategy { double price(long minutes); }

class FlatRate  implements PricingStrategy { public double price(long m){ return 5.0; } }
class PerMinute implements PricingStrategy { public double price(long m){ return 0.1 * m; } }

class ParkingBill {
    private PricingStrategy strategy;                 // holds a strategy
    void setStrategy(PricingStrategy s){ this.strategy = s; }
    double compute(long minutes){ return strategy.price(minutes); }
}

# python — Strategy is often just a function/callable
class ParkingBill:
    def __init__(self, strategy):        # strategy: Callable[[int], float]
        self.strategy = strategy
    def compute(self, minutes):
        return self.strategy(minutes)

flat = lambda m: 5.0
per_minute = lambda m: 0.1 * m
ParkingBill(per_minute).compute(30)      # 3.0

// java
enum VehicleType { CAR, BIKE, TRUCK }

class VehicleFactory {
    static Vehicle create(VehicleType type) {
        switch (type) {
            case CAR:   return new Car();
            case BIKE:  return new Bike();
            case TRUCK: return new Truck();
            default: throw new IllegalArgumentException("unknown type");
        }
    }
}

// java — thread-safe lazy singleton (holder idiom)
class ParkingLot {
    private ParkingLot() {}
    private static class Holder { static final ParkingLot INSTANCE = new ParkingLot(); }
    public static ParkingLot getInstance() { return Holder.INSTANCE; }
}

# python — module-level object is the idiomatic singleton
class _ParkingLot:
    def __init__(self): self.levels = []
parking_lot = _ParkingLot()   # import this shared instance everywhere

// java
interface Observer { void update(String event); }

class Subject {
    private final List<Observer> observers = new ArrayList<>();
    void subscribe(Observer o){ observers.add(o); }
    void notifyAll(String event){ for (Observer o : observers) o.update(event); }
}

// java
interface MachineState { void insertCoin(VendingMachine m); void dispense(VendingMachine m); }

class NoCoinState implements MachineState {
    public void insertCoin(VendingMachine m){ m.setState(m.hasCoin); }   // transition
    public void dispense(VendingMachine m){ System.out.println("insert coin first"); }
}

// java
interface Coffee { double cost(); }
class Espresso implements Coffee { public double cost(){ return 2.0; } }

abstract class CoffeeDecorator implements Coffee {
    protected final Coffee inner;
    CoffeeDecorator(Coffee inner){ this.inner = inner; }
}
class Milk extends CoffeeDecorator {
    Milk(Coffee c){ super(c); }
    public double cost(){ return inner.cost() + 0.5; }   // wraps + extends
}
// new Milk(new Espresso()).cost() == 2.5

// java
interface JsonLogger { void logJson(String json); }

class LegacyTextLogger { void writeLine(String text){ /* ... */ } }  // incompatible

class LoggerAdapter implements JsonLogger {
    private final LegacyTextLogger legacy;
    LoggerAdapter(LegacyTextLogger legacy){ this.legacy = legacy; }
    public void logJson(String json){ legacy.writeLine(json); }      // translate call
}

ParkingLot (Singleton)  ──has-a──▶ List<Level>
Level                   ──has-a──▶ List<ParkingSpot>
ParkingSpot             ──holds──▶ Vehicle (0..1)
Vehicle (abstract)      ◁── Car, Bike, Truck            (is-a)
Ticket                  ──refs──▶ Vehicle, ParkingSpot, entryTime
PricingStrategy         (Strategy)  used by ParkingLot to compute fee
VehicleType, SpotType   (enums)

// java — illustrative skeleton
enum VehicleType { CAR, BIKE, TRUCK }
enum SpotType    { COMPACT, LARGE, MOTORCYCLE, EV }

abstract class Vehicle {
    private final String plate;
    private final VehicleType type;
    Vehicle(String plate, VehicleType type){ this.plate = plate; this.type = type; }
    VehicleType getType(){ return type; }
    abstract boolean canFitIn(SpotType spot);
}

class Car extends Vehicle {
    Car(String plate){ super(plate, VehicleType.CAR); }
    boolean canFitIn(SpotType s){ return s == SpotType.COMPACT || s == SpotType.LARGE; }
}

class ParkingSpot {
    private final String id;
    private final SpotType type;
    private Vehicle vehicle;                 // null == free
    ParkingSpot(String id, SpotType type){ this.id = id; this.type = type; }
    boolean isFree(){ return vehicle == null; }
    boolean assign(Vehicle v){
        if (!isFree() || !v.canFitIn(type)) return false;
        this.vehicle = v; return true;
    }
    void release(){ this.vehicle = null; }
    SpotType getType(){ return type; }
}

class Ticket {
    final String id; final Vehicle vehicle; final ParkingSpot spot; final long entryTime;
    Ticket(String id, Vehicle v, ParkingSpot s){
        this.id = id; this.vehicle = v; this.spot = s; this.entryTime = System.currentTimeMillis();
    }
}

interface PricingStrategy { double fee(Ticket t, long exitTime); }

class Level {
    private final List<ParkingSpot> spots;
    Level(List<ParkingSpot> spots){ this.spots = spots; }
    // find first free spot the vehicle fits into. time = O(n) over spots
    ParkingSpot findSpot(Vehicle v){
        for (ParkingSpot s : spots)
            if (s.isFree() && v.canFitIn(s.getType())) return s;
        return null;
    }
}

class ParkingLot {                                   // Singleton
    private static final ParkingLot INSTANCE = new ParkingLot();
    private ParkingLot(){}
    public static ParkingLot getInstance(){ return INSTANCE; }

    private final List<Level> levels = new ArrayList<>();
    private PricingStrategy pricing;
    private final Map<String, Ticket> active = new HashMap<>();

    Ticket park(Vehicle v){
        for (Level level : levels){
            ParkingSpot spot = level.findSpot(v);
            if (spot != null && spot.assign(v)){
                Ticket t = new Ticket(UUID.randomUUID().toString(), v, spot);
                active.put(t.id, t);
                return t;
            }
        }
        return null;                                 // lot full for this vehicle
    }

    double unpark(String ticketId){
        Ticket t = active.remove(ticketId);
        if (t == null) throw new IllegalArgumentException("invalid ticket");
        t.spot.release();
        return pricing.fee(t, System.currentTimeMillis());
    }
}

ElevatorSystem  ──has-a──▶ List<Elevator>, Scheduler
Scheduler       (Strategy)  picks best elevator for a Request
Elevator        ──has-a──▶ Direction, ElevatorState, TreeSet<Integer> stops
Request         { floor, Direction }     (external)  or { targetFloor } (internal)
Direction       enum { UP, DOWN, IDLE }
ElevatorState   (State)  IDLE / MOVING / DOOR_OPEN
Observer        floor displays subscribe to elevator position changes

// java — illustrative skeleton
enum Direction { UP, DOWN, IDLE }

class Elevator {
    private final int id;
    private int currentFloor = 0;
    private Direction direction = Direction.IDLE;
    // sorted set of pending stops -> naturally serve floors in order
    private final TreeSet<Integer> stops = new TreeSet<>();

    Elevator(int id){ this.id = id; }

    void addStop(int floor){ stops.add(floor); }

    // move one step toward the next stop in the current direction
    void step(){
        if (stops.isEmpty()){ direction = Direction.IDLE; return; }
        Integer next = (direction == Direction.DOWN)
                ? stops.floor(currentFloor)   // nearest stop <= current
                : stops.ceiling(currentFloor);// nearest stop >= current
        if (next == null){ next = stops.first(); }
        if      (next > currentFloor){ currentFloor++; direction = Direction.UP; }
        else if (next < currentFloor){ currentFloor--; direction = Direction.DOWN; }
        else { stops.remove(currentFloor); /* open doors */ }
    }

    int distanceTo(int floor){ return Math.abs(currentFloor - floor); }
    int getCurrentFloor(){ return currentFloor; }
    Direction getDirection(){ return direction; }
}

interface Scheduler { Elevator pick(List<Elevator> elevators, int floor, Direction dir); }

// Nearest-car scheduling: choose the closest idle/compatible elevator.
class NearestCarScheduler implements Scheduler {
    public Elevator pick(List<Elevator> elevators, int floor, Direction dir){
        Elevator best = null; int bestDist = Integer.MAX_VALUE;
        for (Elevator e : elevators){
            int d = e.distanceTo(floor);
            if (d < bestDist){ bestDist = d; best = e; }
        }
        return best;
    }
}

class ElevatorSystem {
    private final List<Elevator> elevators;
    private final Scheduler scheduler;
    ElevatorSystem(List<Elevator> elevators, Scheduler scheduler){
        this.elevators = elevators; this.scheduler = scheduler;
    }
    void requestExternal(int floor, Direction dir){
        Elevator e = scheduler.pick(elevators, floor, dir);
        if (e != null) e.addStop(floor);
    }
}

Card    { Suit, Rank }   (immutable value object)
Deck    ──has-a──▶ List<Card>          (composition, 52 cards)
Hand    ──has-a──▶ List<Card>          (a player's cards)
Player  ──has-a──▶ Hand
Game (abstract) ◁── BlackjackGame, PokerGame   (Template Method for game flow)
Suit, Rank  (enums)

// java
enum Suit { HEARTS, DIAMONDS, CLUBS, SPADES }
enum Rank {
    TWO(2), THREE(3), FOUR(4), FIVE(5), SIX(6), SEVEN(7), EIGHT(8),
    NINE(9), TEN(10), JACK(10), QUEEN(10), KING(10), ACE(11);
    final int value;
    Rank(int value){ this.value = value; }
}

// immutable value object — good OOD habit for domain values
final class Card {
    final Suit suit; final Rank rank;
    Card(Suit suit, Rank rank){ this.suit = suit; this.rank = rank; }
    int value(){ return rank.value; }
    @Override public String toString(){ return rank + " of " + suit; }
}

class Deck {
    private final List<Card> cards = new ArrayList<>();
    private int dealt = 0;

    Deck(){                                          // Factory: build standard 52
        for (Suit s : Suit.values())
            for (Rank r : Rank.values())
                cards.add(new Card(s, r));
    }

    // Fisher-Yates shuffle. time = O(n)
    void shuffle(){
        Random rng = new Random();
        for (int i = cards.size() - 1; i > 0; i--){
            int j = rng.nextInt(i + 1);
            Collections.swap(cards, i, j);
        }
        dealt = 0;
    }

    Card dealCard(){                                 // time = O(1)
        if (dealt >= cards.size()) throw new IllegalStateException("deck empty");
        return cards.get(dealt++);
    }
    int remaining(){ return cards.size() - dealt; }
}

class Hand {
    private final List<Card> cards = new ArrayList<>();
    void add(Card c){ cards.add(c); }
    int score(){ return cards.stream().mapToInt(Card::value).sum(); }  // Blackjack-style
}

# python — same model, more compact
from enum import Enum
import random

class Suit(Enum):
    HEARTS = "H"; DIAMONDS = "D"; CLUBS = "C"; SPADES = "S"

class Deck:
    def __init__(self):
        ranks = list(range(2, 15))                    # 11=J,12=Q,13=K,14=A
        self.cards = [(s, r) for s in Suit for r in ranks]
        self.dealt = 0
    def shuffle(self):
        random.shuffle(self.cards); self.dealt = 0
    def deal(self):
        if self.dealt >= len(self.cards): raise IndexError("deck empty")
        card = self.cards[self.dealt]; self.dealt += 1
        return card

VendingMachine ──has-a──▶ Inventory, MachineState (current), balance
MachineState (State) ◁── NoMoneyState, HasMoneyState, DispensingState
Inventory      ──has-a──▶ Map<String, Slot>
Slot           { Product, count }
Product        { name, price }
Coin           enum { PENNY, NICKEL, DIME, QUARTER }

// java — State pattern drives the lifecycle
interface MachineState {
    void insertMoney(VendingMachine m, int cents);
    void selectProduct(VendingMachine m, String code);
    void dispense(VendingMachine m);
}

class Product { final String name; final int priceCents;
    Product(String n, int p){ name = n; priceCents = p; } }

class Slot { Product product; int count;
    Slot(Product p, int c){ product = p; count = c; } }

class VendingMachine {
    final MachineState noMoney    = new NoMoneyState();
    final MachineState hasMoney   = new HasMoneyState();
    private MachineState state = noMoney;

    private final Map<String, Slot> inventory = new HashMap<>();
    private int balanceCents = 0;
    private String selected;

    void setState(MachineState s){ this.state = s; }
    void addBalance(int c){ balanceCents += c; }
    int  getBalance(){ return balanceCents; }
    Slot slot(String code){ return inventory.get(code); }
    void select(String code){ this.selected = code; }
    String getSelected(){ return selected; }

    // delegate to current state -> no giant if/switch
    void insertMoney(int cents){ state.insertMoney(this, cents); }
    void selectProduct(String code){ state.selectProduct(this, code); }
    void dispense(){ state.dispense(this); }

    int refund(){ int r = balanceCents; balanceCents = 0; setState(noMoney); return r; }
}

class NoMoneyState implements MachineState {
    public void insertMoney(VendingMachine m, int cents){
        m.addBalance(cents); m.setState(m.hasMoney);
    }
    public void selectProduct(VendingMachine m, String code){
        System.out.println("insert money first");
    }
    public void dispense(VendingMachine m){ System.out.println("no money"); }
}

class HasMoneyState implements MachineState {
    public void insertMoney(VendingMachine m, int cents){ m.addBalance(cents); }
    public void selectProduct(VendingMachine m, String code){
        Slot slot = m.slot(code);
        if (slot == null || slot.count == 0){ System.out.println("out of stock"); return; }
        if (m.getBalance() < slot.product.priceCents){ System.out.println("insufficient funds"); return; }
        m.select(code); m.dispense();
    }
    public void dispense(VendingMachine m){
        Slot slot = m.slot(m.getSelected());
        slot.count--;
        int change = m.getBalance() - slot.product.priceCents;
        System.out.println("dispensed " + slot.product.name + ", change=" + change);
        m.setState(m.noMoney);
    }
}

[ ] Clarified functional + non-functional requirements, stated assumptions
[ ] Listed 3-5 concrete use cases
[ ] Extracted nouns -> core classes; verbs -> methods
[ ] Marked each relationship: is-a vs has-a, and cardinality
[ ] Each class has a single, clear responsibility (SRP)
[ ] Programmed to interfaces / abstractions (DIP)
[ ] Used enums for fixed sets (types, states, directions)
[ ] Chose patterns deliberately (Strategy/Factory/State/Observer...) and justified them
[ ] Design is Open/Closed: new feature -> new class, not edits to old ones
[ ] Handled edge cases (full/empty, invalid input, concurrency if asked)
[ ] Sketched a class diagram + key method signatures
[ ] Called out extension points ("to add X later, only Y changes")

STEP 1: Read the API, not the story
   - List every public method + its required complexity (LC states it, or the
     constraints imply it: 1e5 calls => O(1)/O(log n) per call).
   - Note which methods are QUERIES (read) and which are COMMANDS (write).

STEP 2: Find the tightest operation -> it picks the structure
   - Rank the methods by how hard they are at the required complexity.
   - Design for the HARDEST one; the easy ones will fall out.
   - "O(1) random access"   -> array          (LC 380, 384)
   - "O(1) min/max/median"  -> carried value / heap / bucket list (155, 295, 432)
   - "largest key <= x"     -> sorted list + binary search / TreeMap (981, 729, 1146)
   - "prefix / wildcard"    -> Trie of nodes  (208, 211)
   - "O(1) evict oldest"    -> linked list + map (146)

STEP 3: Write the invariant as a comment ABOVE the fields
   - One sentence, true between every pair of calls.
   - If you cannot state it, your state is wrong (usually redundant or missing).

STEP 4: Implement each method as "restore the invariant"
   - Every command ends by re-establishing it; every query may assume it.
   - Constructor establishes it on empty state.
   - Then and only then: edge cases (empty, full, duplicate, unknown key).

// java
// LC 1603 - Design Parking System
// IDEA: the only query is addCar -> "is a spot of this type left?".
//       No car is ever identified and none ever leaves, so the state collapses
//       to ONE counter per spot type. No Spot / Vehicle / Ticket class needed.
class ParkingSystem {
    // time = O(1) per addCar, space = O(1)
    private final int[] remaining = new int[4];      // index 1=big, 2=medium, 3=small

    public ParkingSystem(int big, int medium, int small) {
        remaining[1] = big; remaining[2] = medium; remaining[3] = small;
    }

    // INVARIANT: remaining[t] == capacity[t] - parked(t), and never negative
    public boolean addCar(int carType) {
        if (remaining[carType] == 0) return false;   // full for this type
        remaining[carType]--;
        return true;
    }
}

# python
# LC 1603 - Design Parking System
# IDEA: one counter per spot type; identity of a car is never asked for.
class ParkingSystem:
    # time = O(1) per addCar, space = O(1)
    def __init__(self, big: int, medium: int, small: int):
        self.remaining = {1: big, 2: medium, 3: small}

    # INVARIANT: remaining[t] == capacity[t] - parked(t), never negative
    def addCar(self, carType: int) -> bool:
        if self.remaining[carType] == 0:
            return False
        self.remaining[carType] -= 1
        return True

// java — the same prompt, one requirement heavier
// IDEA: leave() forces spot IDENTITY (free/occupied pools); a variable fit rule
//       forces a POLICY OBJECT (Strategy) instead of an if/else in park().
enum SpotType { BIG, MEDIUM, SMALL }

interface SpotPolicy { List<SpotType> fitsFor(SpotType wanted); }   // Strategy

class ExactFitPolicy implements SpotPolicy {
    public List<SpotType> fitsFor(SpotType wanted) { return List.of(wanted); }
}

class UpgradePolicy implements SpotPolicy {          // a car may take a bigger spot
    public List<SpotType> fitsFor(SpotType wanted) {
        switch (wanted) {
            case SMALL:  return List.of(SpotType.SMALL, SpotType.MEDIUM, SpotType.BIG);
            case MEDIUM: return List.of(SpotType.MEDIUM, SpotType.BIG);
            default:     return List.of(SpotType.BIG);
        }
    }
}

class ParkingLotV2 {
    // time = O(#types) park / O(1) leave, space = O(total spots)
    private final Map<SpotType, Deque<Integer>> free = new EnumMap<>(SpotType.class);
    private final Map<Integer, SpotType> occupied = new HashMap<>();   // spotId -> type
    private final SpotPolicy policy;                                   // injected (DIP)
    private int nextId = 0;

    ParkingLotV2(Map<SpotType, Integer> capacity, SpotPolicy policy) {
        this.policy = policy;
        for (SpotType t : SpotType.values()) {
            Deque<Integer> ids = new ArrayDeque<>();
            for (int i = 0; i < capacity.getOrDefault(t, 0); i++) ids.push(nextId++);
            free.put(t, ids);
        }
    }

    // INVARIANT: every spot id is in exactly one of `free` / `occupied`
    Integer park(SpotType wanted) {
        for (SpotType t : policy.fitsFor(wanted)) {
            Deque<Integer> pool = free.get(t);
            if (!pool.isEmpty()) { int id = pool.pop(); occupied.put(id, t); return id; }
        }
        return null;                                  // no acceptable spot
    }

    boolean leave(int spotId) {
        SpotType t = occupied.remove(spotId);
        if (t == null) return false;                  // unknown / already free
        free.get(t).push(spotId);
        return true;
    }
}

# python — same model; the Strategy is just a function
# IDEA: leave() needs spot identity -> free/occupied pools; fit rule -> injected policy.
from enum import Enum

class SpotType(Enum):
    BIG = 1; MEDIUM = 2; SMALL = 3

def exact_fit(wanted):                       # Strategy A
    return [wanted]

def upgrade_fit(wanted):                     # Strategy B: may take a bigger spot
    order = [SpotType.SMALL, SpotType.MEDIUM, SpotType.BIG]
    return order[order.index(wanted):]

class ParkingLotV2:
    # time = O(#types) park / O(1) leave, space = O(total spots)
    def __init__(self, capacity, policy=exact_fit):
        self.policy = policy
        self.free = {t: [] for t in SpotType}
        self.occupied = {}                   # spot_id -> SpotType
        next_id = 0
        for t in SpotType:
            for _ in range(capacity.get(t, 0)):
                self.free[t].append(next_id)
                next_id += 1

    # INVARIANT: every spot id is in exactly one of free / occupied
    def park(self, wanted):
        for t in self.policy(wanted):
            if self.free[t]:
                spot_id = self.free[t].pop()
                self.occupied[spot_id] = t
                return spot_id
        return None

    def leave(self, spot_id):
        t = self.occupied.pop(spot_id, None)
        if t is None:
            return False
        self.free[t].append(spot_id)
        return True

Twitter  ──has-a──▶ Map<Integer, User>   (registry of users)
Twitter  ──has-a──▶ int clock            (global monotonic timestamp)
User     ──has-a──▶ Set<Integer> followees, List<Tweet> tweets
Tweet    { int id, int time }            (immutable value object)

getNewsFeed(u) = top-10 by time over { tweets of u } ∪ { tweets of each followee }