R24 — Low-level design case studies

R23 gave the method, the principles and the patterns. This section applies them to ten classic low-level design questions. Each walkthrough is a transcript of a 45–60 minute round with the same phases, so you can rehearse the rhythm as well as the content:

1. Scope and requirements — the clarifying questions that change the design.
2. Entities and responsibilities — the classes, found from the nouns and verbs.
3. Class diagram — relationships, interfaces, composition versus association.
4. Key flows — a sequence or state diagram for the central use case.
5. Patterns used, and why — each one tied to the problem it solves (R23).
6. The core code — compact Java 17 for the heart of the design.
7. Concurrency, edge cases and testing — what breaks, and how the design copes.
8. Extensions — new requirements absorbed with minimal change.
9. Quick reference and the 60-second version.

The order is chosen so that each walkthrough adds one difficulty to the last:

Two walkthroughs carry animations: the ATM's state machine with its journal, outbox and cash chain, and the elevator dispatcher with its strategy and sweeps.

Walkthrough 1 — ATM: a state machine that moves money

Where this starts: R23 gave you the method (find nouns and verbs, assign responsibilities, draw the classes), SOLID and the patterns. This walkthrough applies them to the first classic case, an ATM. It is small enough to finish in 45 minutes, and it teaches two lessons that every later case reuses. First, a machine whose behaviour depends on where it is in a conversation is a state machine, and the State pattern keeps that readable. Second, when the machine moves money, every step must survive a crash halfway through. These are the idempotency and reconciliation ideas from R3 and R6, now inside a class design.

Scope and requirements

Interviewer: Design the software for an ATM.

You: An ATM is a small computer. It drives hardware (card reader, PIN pad, screen, cash dispenser, receipt printer) and talks to the bank's central computer, which I'll call the host. The host owns accounts and balances. The ATM owns the conversation with the customer and the cash in its cassettes. A cassette is the locked box that holds notes of one denomination. Some questions first:

Interviewer: Withdrawal and balance enquiry; maybe deposit later. The host verifies PINs, checks balances and daily limits, and debits the account. Three cassettes: ₹500, ₹200 and ₹100. At most ₹10,000 and 40 notes per withdrawal. And yes, tell me about power failures.

You: Then the requirements are these.

Functional:

• Read a card and take a PIN; the host verifies it. After three wrong PINs the host blocks the card and the ATM keeps it.
• Withdraw any multiple of ₹100 up to ₹10,000, using whatever notes are loaded.
• Show or print the balance.
• Cancel at any point before cash moves. The card always comes back unless it is retained.
• Go out of service when cash runs out or hardware fails, and come back when serviced.

Constraints:

• One customer at a time per machine. Many machines and other channels (UPI, net banking) hit the same account at the host at the same time.
• An account is debited at most once per withdrawal, and only for notes that actually left the machine.
• Every step is journaled to local disk so that a reboot can tell where it stopped.
• Money is held in paise as a long.
• Hardware sits behind interfaces, so the logic runs in tests without a machine.

The account is debited once, and only for notes that physically left the machine; every other outcome is reversed. The states, the journal and the outbox all exist to keep that promise.

Entities and responsibilities

Interviewer: What are your classes?

You: I read the requirements for nouns and verbs. Nouns: ATM, card, PIN, account, host, cassette, note, withdrawal, receipt, screen. Verbs: insert, verify, withdraw, dispense, print, cancel, retain, reverse. Then I drop nouns that are only data (the PIN becomes an encrypted value; the account lives at the host, not here) and give each verb an owner. One phrase matters most: what the ATM does depends on what has happened so far. You cannot withdraw before you enter a PIN. That tells me the behaviour belongs in state objects, not in if (pinVerified) checks spread across one large class.

Notice that Atm never knows the balance. The host is the only source of truth for money in the account; the ATM is the only source of truth for money in the cassettes. Keeping that split clean is single responsibility applied to data ownership.

Class diagram

classDiagram
    class Atm {
        -AtmState state
        +insertCard(card)
        +enterPin(pin)
        +withdraw(amount)
        +cancel()
    }
    class AtmState {
        <<interface>>
        +insertCard(atm, card) AtmState
        +enterPin(atm, pin) AtmState
        +withdraw(atm, amount) AtmState
        +cancel(atm) AtmState
        +onEnter(atm) AtmState
    }
    class BankHost {
        <<interface>>
        +verifyPin(card, pin) PinOutcome
        +authorise(txnId, card, amount) AuthResult
    }
    class CashDispenser {
        +plan(amount) DispensePlan
        +dispense(plan) DispenseOutcome
    }
    class NoteHandler {
        -Cassette cassette
        -NoteHandler next
        +plan(remaining) Map
    }
    class Cassette {
        -Denomination denomination
        -int count
    }
    class Journal {
        +record(txnId, step)
        +unfinished() List
    }
    class HostOutbox {
        +confirm(txnId)
        +reverse(txnId, amount)
    }
    Atm --> AtmState : current
    AtmState <|.. IdleState
    AtmState <|.. CardInsertedState
    AtmState <|.. AuthenticatedState
    AtmState <|.. DispensingState
    AtmState <|.. OutOfServiceState
    Atm --> BankHost
    Atm *-- CashDispenser
    Atm *-- Journal
    Atm *-- HostOutbox
    CashDispenser *-- NoteHandler : head
    NoteHandler --> NoteHandler : next
    NoteHandler o-- Cassette

Atm composes the dispenser, journal and outbox: they are created with the machine and mean nothing without it. It only associates with BankHost through an interface, because the host is someone else's system and tests swap in a fake. The states are tiny classes that each implement AtmState; the Atm holds exactly one at a time and replaces it on every transition. NoteHandler points to the next handler, which is the shape of Chain of Responsibility.

Key flows

Interviewer: Walk me through a withdrawal.

You: Here are the states and what moves the machine between them.

stateDiagram-v2
    [*] --> Idle
    Idle --> CardInserted : card inserted
    CardInserted --> CardInserted : wrong PIN
    CardInserted --> Authenticated : PIN ok
    CardInserted --> Idle : cancel or card retained
    Authenticated --> Authenticated : balance enquiry
    Authenticated --> Dispensing : host approves
    Authenticated --> Idle : cancel or declined
    Dispensing --> Idle : delivered or reversal queued
    Idle --> OutOfService : no cash or fault
    OutOfService --> Idle : serviced

A ₹2,600 withdrawal, step by step:

1. In Idle, the card reader reports a card. The state shows "Enter PIN" and returns CardInsertedState.
2. The PIN pad encrypts the PIN in hardware; the ATM software never sees it in clear. CardInsertedState sends it to the host. The host keeps the wrong-PIN count, so taking the card out and putting it back does not reset it.
3. The customer picks ₹2,600. AuthenticatedState first asks the dispenser for a plan (5 × ₹500 + 1 × ₹100). If no plan exists, it says so and asks for another amount. We never debit for cash we cannot pay out.
4. The ATM creates a TxnId and writes AUTH_REQUESTED to the journal before sending anything. The id goes with every message about this withdrawal, so the host can recognise a repeat.
5. The host checks the balance and limits, debits the account, and replies "approved". The journal records AUTHORISED and the machine enters DispensingState.
6. DispensingState returns the card first (so it is not left behind), journals DISPENSING, then runs the motor. The cash unit reports how many notes it actually presented.
7. All notes taken: journal DISPENSED, and put a confirmation in the outbox. Short or failed: journal what happened and put a reversal for the undelivered amount in the outbox.
8. The outbox sends to the host in the background, retrying until each message is acknowledged. The machine returns to Idle.

Step through it below: a normal withdrawal, a host that times out, a jam mid-dispense, and the cash chain backing off to find a plan.

Patterns used, and why

The core code

Interviewer: Show me the state machine and the dispenser.

You: Value types first. Amounts are paise in a long; a denomination knows its own value.

public record Money(long paise) {
    public Money {
        if (paise < 0) throw new IllegalArgumentException("negative amount");
    }
    public static Money rupees(long r) { return new Money(r * 100); }
    public Money minus(Money other)    { return new Money(paise - other.paise); }
}

public enum Denomination {
    RS_500(50_000), RS_200(20_000), RS_100(10_000);
    public final long paise;
    Denomination(long paise) { this.paise = paise; }
}

public record TxnId(String atmId, long sequence) {}   // unique per machine; the host de-duplicates on it

The state interface is sealed: the compiler knows the full list of states, and nobody can add one by accident. Default methods reject every event, so each state overrides only the events it accepts. Every method returns the next state.

public sealed interface AtmState
        permits IdleState, CardInsertedState, AuthenticatedState, DispensingState, OutOfServiceState {

    default AtmState insertCard(Atm atm, Card card)     { return reject(atm, "Machine busy"); }
    default AtmState enterPin(Atm atm, EncryptedPin p)  { return reject(atm, "Please insert a card"); }
    default AtmState withdraw(Atm atm, Money amount)    { return reject(atm, "Not available now"); }
    default AtmState cancel(Atm atm)                    { return this; }
    default AtmState onEnter(Atm atm)                   { return this; }   // entry action; may move on at once

    private AtmState reject(Atm atm, String message) {
        atm.screen().show(message);
        return this;
    }
}

The states are records, because a state is a value: the card in play, the transaction being dispensed. They hold no mutable fields, which makes them easy to reason about and to test.

public record IdleState() implements AtmState {
    @Override public AtmState insertCard(Atm atm, Card card) {
        atm.screen().show("Enter PIN");
        return new CardInsertedState(card);
    }
}

public record OutOfServiceState() implements AtmState {}   // every event rejected until an engineer resets it

public record CardInsertedState(Card card) implements AtmState {
    @Override public AtmState enterPin(Atm atm, EncryptedPin pin) {
        return switch (atm.host().verifyPin(card, pin)) {
            case OK -> { atm.screen().showMenu(); yield new AuthenticatedState(card); }
            case WRONG_PIN -> { atm.screen().show("Wrong PIN, try again"); yield this; }
            case CARD_BLOCKED -> {
                atm.cardReader().retain();
                atm.screen().show("Card retained. Please contact your bank.");
                yield new IdleState();
            }
        };
    }
    @Override public AtmState cancel(Atm atm) {
        atm.cardReader().eject();
        return new IdleState();
    }
}

AuthenticatedState holds the money logic. Look at the order: plan, journal, then call the host. A timeout from the host is an unknown outcome (R0): the account may or may not have been debited, so we queue a reversal and never dispense.

public record AuthenticatedState(Card card) implements AtmState {
    @Override public AtmState withdraw(Atm atm, Money amount) {
        Optional<DispensePlan> plan = atm.dispenser().plan(amount);
        if (plan.isEmpty()) {
            atm.screen().show("This amount cannot be dispensed. Please choose another.");
            return this;
        }
        TxnId txn = atm.nextTxnId();
        atm.journal().record(txn, Step.AUTH_REQUESTED, amount);       // durable before the request leaves
        AuthResult result;
        try {
            result = atm.host().authorise(txn, card, amount);
        } catch (HostTimeoutException e) {
            atm.journal().record(txn, Step.REVERSAL_QUEUED, amount);
            atm.outbox().reverse(txn, amount);                        // safe even if the host never debited
            atm.screen().show("Service unavailable. Any amount debited will be reversed.");
            return cancel(atm);
        }
        if (result != AuthResult.APPROVED) {
            atm.journal().record(txn, Step.DECLINED, amount);
            atm.screen().show(result.customerMessage());
            return cancel(atm);
        }
        atm.journal().record(txn, Step.AUTHORISED, amount);
        return new DispensingState(txn, amount, plan.get());
    }
    @Override public AtmState cancel(Atm atm) {
        atm.cardReader().eject();
        return new IdleState();
    }
}

public record DispensingState(TxnId txn, Money amount, DispensePlan plan) implements AtmState {
    @Override public AtmState onEnter(Atm atm) {
        atm.cardReader().eject();                                     // card back before cash
        atm.journal().record(txn, Step.DISPENSING, amount);           // written before the motor turns
        DispenseOutcome out = atm.dispenser().dispense(plan);         // counted by the cash unit's sensors
        if (out.delivered().equals(amount)) {
            atm.journal().record(txn, Step.DISPENSED, amount);
            atm.outbox().confirm(txn);
        } else {
            Money shortfall = amount.minus(out.delivered());
            atm.journal().record(txn, Step.PARTIAL, out.delivered());
            atm.outbox().reverse(txn, shortfall);
            atm.screen().show("Could not dispense the full amount. The rest will be credited back.");
        }
        return atm.dispenser().isEmpty() ? new OutOfServiceState() : new IdleState();
    }
    // every customer event uses the rejecting defaults: nothing interrupts a dispense
}

The Atm context is small. It serialises events with synchronized, because the card reader and keypad report from their own driver threads, and it runs entry actions until the state settles.

public final class Atm {
    private AtmState state = new IdleState();
    private final BankHost host;
    private final CashDispenser dispenser;
    private final Journal journal;
    private final HostOutbox outbox;
    // screen, cardReader and the sequence counter injected the same way; getters elided

    public synchronized void insertCard(Card c)      { transition(state.insertCard(this, c)); }
    public synchronized void enterPin(EncryptedPin p) { transition(state.enterPin(this, p)); }
    public synchronized void withdraw(Money amount)   { transition(state.withdraw(this, amount)); }
    public synchronized void cancel()                 { transition(state.cancel(this)); }

    private void transition(AtmState next) {
        while (next != state) {              // reference check: a state that returns itself stays put
            state = next;
            next = state.onEnter(this);
        }
    }
}

Now the dispenser chain. A greedy chain (take as many big notes as possible, pass the rest on) is the textbook version, but it fails on real cassette mixes. With one ₹500 note and plenty of ₹200 notes but no ₹100s, ₹600 fails greedily (₹500, then ₹100 that nobody has), yet three ₹200 notes would work. So each link tries its largest count first and backs off when the rest of the chain cannot cover the remainder.

public final class NoteHandler {
    private final Cassette cassette;
    private final NoteHandler next;          // null at the end of the chain

    public NoteHandler(Cassette cassette, NoteHandler next) {
        this.cassette = cassette;
        this.next = next;
    }

    /** Notes to take from this link and those after it, or empty if the amount cannot be made. */
    public Optional<Map<Denomination, Integer>> plan(long remaining, int notesLeft) {
        if (remaining == 0) return Optional.of(new EnumMap<>(Denomination.class));
        long unit = cassette.denomination().paise;
        int max = (int) Math.min(Math.min(remaining / unit, cassette.count()), notesLeft);
        for (int take = max; take >= 0; take--) {                    // greedy first, then back off
            long rest = remaining - take * unit;
            Optional<Map<Denomination, Integer>> tail =
                    rest == 0   ? Optional.of(new EnumMap<>(Denomination.class))
                  : next == null ? Optional.<Map<Denomination, Integer>>empty()
                  : next.plan(rest, notesLeft - take);
            if (tail.isPresent()) {
                if (take > 0) tail.get().put(cassette.denomination(), take);
                return tail;
            }
        }
        return Optional.empty();
    }
}

With three or four denominations and at most 40 notes, the back-off explores under a thousand combinations at worst, which takes microseconds. CashDispenser.plan builds the chain from the loaded cassettes in descending order and calls head.plan(amount.paise(), 40). Planning never changes counts; counts drop only when the cash unit reports notes actually delivered.

Concurrency, edge cases and testing

Interviewer: The power goes out while the dispenser is counting notes. What happens to the customer's account?

You: At that moment the host has debited ₹2,600, and some unknown number of notes may have reached the customer. Three things make this safe.

First, the journal order. DISPENSING is on disk before the motor turns. On boot, Recovery reads every transaction without a final step and acts on the last step it finds:

• AUTH_REQUESTED or AUTHORISED: no cash moved. Queue a full reversal.
• DISPENSING: ask the cash unit. Dispensers keep their own note counts in the device controller, and notes left in the presenter are retracted into a reject bin and counted. If the device can say what was delivered, confirm that amount and reverse the rest. If it cannot, mark the transaction suspect and do neither automatically.
• DISPENSED or PARTIAL: the outcome is known; just make sure the outbox message is still queued.

Second, idempotent host messages. Every reversal and confirmation carries the TxnId. The outbox may resend after a reboot, and the host applies each message at most once (R3). Without that, a resend would credit the customer twice.

Third, reconciliation. When the cassettes are replenished, staff count the remaining notes. Starting count minus remaining count must equal the total of DISPENSED amounts in the journal plus notes in the reject bin. A suspect transaction is settled by that count, and the bank's records are matched against the host's daily settlement file (R6). Banking regulators, including the RBI in India, set deadlines for reversing failed ATM withdrawals, so suspect cases cannot wait forever.

What's being probed: whether you see that a crash between "debit" and "cash out" leaves an unknown outcome, and that only a journal plus idempotent reversal resolves it.

Concept — Write intent before effect. Before any step with a physical or financial effect, write down what you are about to do; after it, write down that you did it. After a crash, the gap between the two records tells you exactly which steps might be half done. It is the same idea as a database's write-ahead log, and as the outbox in R4. Recovery then uses idempotent messages (R3) and, where the machine cannot know, a count against reality (R6).

Takeaway: Journal before the effect, make every compensating message idempotent, and let reconciliation settle what the machine cannot know.

Other things that can go wrong:

Testing follows from the interfaces. A FakeHost can approve, decline or time out on demand; a FakeCashUnit can deliver all, some or none of the notes. Each test drives events into Atm and checks the screen messages, the final state, the journal and the outbox. The recovery tests write a journal ending at each possible step, run Recovery, and check the queued messages. The dispenser gets a brute-force check: for every amount up to ₹10,000 and a range of cassette counts, plan must succeed exactly when some combination of notes exists.

Extensions the interviewer will ask for

Interviewer: Add cash deposits.

You: A new path, not a rewrite. AuthenticatedState.deposit() moves to a new AcceptingCashState, which counts and validates notes, shows the total for the customer to confirm, then sends a credit request with a TxnId. The journal and outbox are reused unchanged. Existing states are untouched apart from one new menu option, which is open/closed in practice.

Interviewer: Cardless withdrawal: the customer scans a UPI QR code on the screen.

You: Only the way we authenticate changes. I extract an Authenticator interface with CardPinAuthenticator and UpiQrAuthenticator; IdleState gains a "scan to withdraw" event that leads to the same AuthenticatedState, holding a payer reference instead of a card. Withdrawal, dispensing and recovery stay the same.

Interviewer: The bank loads a ₹50 cassette.

You: Add a RS_50 constant and one more NoteHandler at the end of the chain. No other class changes.

Interviewer: Operations want an alert when a cassette runs low.

You: Cassette publishes a LowCash event to registered listeners (Observer); a FleetReporter listener sends it to the monitoring system. The dispenser does not know who is listening.

Quick reference

The 60-second version

An ATM is a state machine wrapped around a money transfer. I model it with the State pattern: a sealed AtmState with Idle, CardInserted, Authenticated, Dispensing and OutOfService records. Each state handles events and returns the next state, while a small Atm context serialises events and holds the devices. The host owns the balance; the ATM owns the cassettes. A withdrawal first plans the notes with a Chain of Responsibility that backs off when greedy fails. Then it journals its intent, gets the host's approval under a unique transaction id, journals again, dispenses, and confirms or reverses through a durable, idempotent outbox. A power cut at any point leaves a journal entry that tells recovery exactly what to do, and when the machine truly cannot know, the cassette count at replenishment settles it.

Walkthrough 2 — Elevator system: many objects acting at once

Building on the ATM: the ATM served one customer at a time, so a single lock on one object was enough. An elevator bank is different. Several cars move at once, people press buttons on every floor while the cars are moving, and a decision made now ("send car 2") must stay sensible while the world keeps changing underneath it. This walkthrough adds three things: a clean split between deciding (which car answers a call) and doing (how a car serves its stops), a scheduling algorithm behind a Strategy so it can be swapped, and a deliberate choice of how threads share state.

Scope and requirements

Interviewer: Design an elevator system for an office building.

You: Two kinds of button drive it. A hall call is pressing up or down on a floor; it says where someone is and which way they want to go, but not their destination. A car call is pressing a floor number inside a car. The core problem is assigning hall calls to cars and ordering each car's stops. Some questions:

Interviewer: Twenty floors, four cars, up/down hall buttons. Minimise average waiting time. Cars have load sensors. Maintenance mode is required; fire mode can come later. Write the controller as if it drives real hardware.

You: Then the requirements are these.

Functional:

• Accept hall calls (floor, direction) and car calls (car, floor) at any time, including while cars are moving.
• Assign each hall call to exactly one car, using a replaceable scheduling strategy.
• Each car serves its stops in a sensible order: keep going in one direction while there are stops ahead, then reverse.
• Turn off a hall lamp when a car arrives going the requested way.
• Take a car out of service and give its waiting hall calls to other cars.

Constraints:

• Button presses come from many threads at once and must never block on a moving car.
• Pressing a lit button again changes nothing.
• No request is lost, and no waiting passenger is starved.
• The motor and doors are slow (seconds); nothing should hold a lock while waiting on them.
• The logic must be testable step by step, without real time passing.

Separate deciding from doing: a dispatcher chooses a car from a snapshot of the cars, and each car alone owns and orders its stops.

Entities and responsibilities

Interviewer: Classes?

You: Nouns from the brief: building, floor, car, button, hall call, car call, door, motor, display, request, schedule. Verbs: press, assign, move, stop, open, close, reverse. The interesting verb is assign. It needs a view of every car, so it cannot live inside one car; it belongs to a coordinator, the Dispatcher. Move, stop and open belong to the car itself. Floors turn out to be just numbers here, so I don't make them classes. A floor class would hold no behaviour.

Class diagram

classDiagram
    class Dispatcher {
        -BlockingQueue inbox
        -Set assigned
        +submit(request)
        +setStrategy(strategy)
        +onStopped(carId, floor, served)
    }
    class DispatchStrategy {
        <<interface>>
        +choose(call, cars) Optional
    }
    class NearestSuitableCar
    class ElevatorCar {
        -TreeMap stops
        -int floor
        -Direction direction
        +addStop(floor, kind)
        +snapshot() CarSnapshot
        +step()
    }
    class CarSnapshot {
        <<record>>
        +carId
        +floor
        +direction
        +pendingStops
    }
    class Request {
        <<interface>>
    }
    class HallCall {
        <<record>>
    }
    class CarCall {
        <<record>>
    }
    class CarListener {
        <<interface>>
        +onStopped(carId, floor, served)
    }
    class Motor {
        <<interface>>
        +moveOneFloor(direction)
    }
    class Door {
        <<interface>>
        +openWaitClose()
    }
    Dispatcher --> DispatchStrategy
    DispatchStrategy <|.. NearestSuitableCar
    Dispatcher o-- "4" ElevatorCar
    Request <|.. HallCall
    Request <|.. CarCall
    Dispatcher ..> Request : consumes
    ElevatorCar *-- Motor
    ElevatorCar *-- Door
    ElevatorCar ..> CarSnapshot : publishes
    ElevatorCar --> CarListener : notifies
    CarListener <|.. Dispatcher

The dispatcher aggregates cars: it coordinates them but does not own their insides. A car composes its motor and door. The two arrows that matter for concurrency are the snapshot (the dispatcher reads an immutable copy rather than the car's live fields) and the listener (the car reports back through an interface, so it never calls dispatcher internals directly).

Key flows

Interviewer: Someone on floor 7 presses "up". Take me through it.

sequenceDiagram
    participant P as Passenger
    participant D as Dispatcher
    participant S as Strategy
    participant C as Car 2
    participant HW as Motor and Door
    P->>D: HallCall floor 7 UP
    D->>D: drop if already assigned
    D->>S: choose using car snapshots
    S-->>D: car 2
    D->>C: addStop 7 HALL_UP
    loop every floor
        C->>HW: move one floor
        C->>C: stop here?
    end
    C->>HW: open, wait, close
    C-->>D: onStopped 7 HALL_UP
    D-->>P: hall lamp off
    P->>D: CarCall car 2 floor 15
    D->>C: addStop 15 CAR

1. The hall panel's driver thread calls dispatcher.submit(new HallCall(7, UP)). That only adds to a queue, so the button thread returns at once.
2. The dispatcher thread takes the call. If (7, UP) is already assigned, the press is a duplicate and is dropped.
3. It collects a CarSnapshot from each car. These are immutable, so reading them needs no lock.
4. The strategy scores each car. Car 2 is at floor 4 going up, so 7 is "on the way" and cheap; car 1 at floor 9 going down would have to finish its sweep first, so it is expensive. Car 2 wins.
5. car2.addStop(7, HALL_UP) takes car 2's lock for microseconds, adds the stop, and wakes the car if it was idle.
6. Car 2's own thread moves one floor at a time. After every floor it asks: is there a stop here that I should serve going this way? Checking floor by floor means a stop added mid-journey is picked up naturally.
7. At 7 it opens the doors, then reports onStopped(2, 7, {HALL_UP}). The dispatcher clears the assignment and the lamp goes off.
8. The passenger presses 15 inside. That car call goes straight to car 2; no strategy is needed.

Step through it below: assigning a hall call by strategy score, the LOOK sweep, duplicate presses, and swapping the strategy at runtime.

Patterns used, and why

Why not the State pattern for the car, as in the ATM? The car's state is a direction and a service flag, and its behaviour in each state is the same loop with a different sign. An enum is enough. Use the State pattern when states respond to events in really different ways; here it would just be ceremony.

The core code

Interviewer: Show me the strategy and the car.

You: The vocabulary first. A sealed Request means route can rely on there being exactly two kinds.

public enum Direction { UP, DOWN, IDLE }

public enum StopKind {
    CAR, HALL_UP, HALL_DOWN;

    static StopKind forHall(Direction d) { return d == Direction.UP ? HALL_UP : HALL_DOWN; }

    Optional<Direction> hallDirection() {
        return switch (this) {
            case HALL_UP -> Optional.of(Direction.UP);
            case HALL_DOWN -> Optional.of(Direction.DOWN);
            case CAR -> Optional.empty();
        };
    }
}

public sealed interface Request permits HallCall, CarCall {}
public record HallCall(int floor, Direction direction) implements Request {}
public record CarCall(int carId, int floor) implements Request {}

public record CarSnapshot(int carId, int floor, Direction direction, int pendingStops, boolean inService) {}

The strategy is a pure function from a call and snapshots to a choice. It has no threads and no hardware, so it is trivial to test and to replace. The cost here is distance, plus a heavy penalty when the car must finish a sweep in the other direction first, plus a small penalty per pending stop to spread the load.

public interface DispatchStrategy {
    Optional<Integer> choose(HallCall call, List<CarSnapshot> cars);
}

public final class NearestSuitableCar implements DispatchStrategy {
    private final int floors;

    public NearestSuitableCar(int floors) { this.floors = floors; }

    @Override public Optional<Integer> choose(HallCall call, List<CarSnapshot> cars) {
        return cars.stream()
                   .filter(CarSnapshot::inService)
                   .min(Comparator.comparingInt((CarSnapshot c) -> cost(c, call)))
                   .map(CarSnapshot::carId);
    }

    int cost(CarSnapshot car, HallCall call) {
        int distance = Math.abs(car.floor() - call.floor());
        int load = car.pendingStops();
        if (car.direction() == Direction.IDLE) return distance + load;
        boolean onTheWay =
                (car.direction() == Direction.UP && call.direction() == Direction.UP && call.floor() >= car.floor())
             || (car.direction() == Direction.DOWN && call.direction() == Direction.DOWN && call.floor() <= car.floor());
        return onTheWay ? distance + load : distance + load + 2 * floors;   // must reverse first
    }
}

The car is where concurrency lives. Its stop set, floor and direction are guarded by one ReentrantLock. addStop holds the lock for microseconds. The motor and doors run outside the lock, so a button press never waits for a car to travel a floor. The stop set is a TreeMap, because the car keeps asking "what is the next stop above me?" and higherKey answers that in logarithmic time.

public final class ElevatorCar {
    private final int id;
    private final Motor motor;
    private final Door door;
    private final CarListener listener;

    private final ReentrantLock lock = new ReentrantLock();
    private final Condition hasWork = lock.newCondition();
    private final TreeMap<Integer, EnumSet<StopKind>> stops = new TreeMap<>();   // guarded by lock
    private int floor;                                                           // guarded by lock
    private Direction direction = Direction.IDLE;                                // guarded by lock
    private boolean inService = true;                                            // guarded by lock
    private volatile CarSnapshot snapshot;                                       // read without the lock

    // constructor sets id, motor, door, listener and publishes the first snapshot

    public void addStop(int target, StopKind kind) {
        lock.lock();
        try {
            stops.computeIfAbsent(target, f -> EnumSet.noneOf(StopKind.class)).add(kind);
            publish();
            hasWork.signal();
        } finally {
            lock.unlock();
        }
    }

    public CarSnapshot snapshot() { return snapshot; }

    /** The car's own thread. */
    void runLoop() throws InterruptedException {
        while (true) {
            lock.lock();
            try {
                while (!inService || stops.isEmpty()) {
                    direction = Direction.IDLE;
                    publish();
                    hasWork.await();
                }
            } finally {
                lock.unlock();
            }
            step();
        }
    }

step makes one decision under the lock, then performs one slow action without it. Tests call step directly, so they control time completely.

    void step() {
        Direction move = null;
        Set<StopKind> served = Set.of();
        int at;
        lock.lock();
        try {
            if (!inService || stops.isEmpty()) return;
            at = floor;
            if (shouldStopHere()) served = clearCurrentFloor();
            else move = direction = chooseDirection();
            publish();
        } finally {
            lock.unlock();
        }

        if (move == null) {
            door.openWaitClose();                    // refuses to close while the load sensor reads overweight
            listener.onStopped(id, at, served);      // called without our lock held: no lock-order deadlock
        } else {
            motor.moveOneFloor(move);
            lock.lock();
            try { floor += (move == Direction.UP) ? 1 : -1; publish(); }
            finally { lock.unlock(); }
        }
    }

    private boolean shouldStopHere() {
        EnumSet<StopKind> kinds = stops.get(floor);
        if (kinds == null) return false;
        if (kinds.contains(StopKind.CAR) || direction == Direction.IDLE) return true;
        boolean up = direction == Direction.UP;
        boolean sameWay = kinds.contains(up ? StopKind.HALL_UP : StopKind.HALL_DOWN);
        boolean nothingAhead = (up ? stops.higherKey(floor) : stops.lowerKey(floor)) == null;
        return sameWay || nothingAhead;              // at the end of a sweep, serve both hall directions
    }

    private Set<StopKind> clearCurrentFloor() {
        EnumSet<StopKind> kinds = stops.get(floor);
        boolean turnaround = direction == Direction.IDLE
                || (direction == Direction.UP ? stops.higherKey(floor) : stops.lowerKey(floor)) == null;
        EnumSet<StopKind> served = EnumSet.copyOf(kinds);
        if (!turnaround) served.remove(direction == Direction.UP ? StopKind.HALL_DOWN : StopKind.HALL_UP);
        kinds.removeAll(served);
        if (kinds.isEmpty()) stops.remove(floor);
        return served;
    }

    private Direction chooseDirection() {            // LOOK: keep going while there is work ahead
        Integer above = stops.higherKey(floor), below = stops.lowerKey(floor);
        if (direction == Direction.UP && above != null) return Direction.UP;
        if (direction == Direction.DOWN && below != null) return Direction.DOWN;
        if (above != null && below != null) return (above - floor <= floor - below) ? Direction.UP : Direction.DOWN;
        return above != null ? Direction.UP : Direction.DOWN;
    }

    private void publish() {
        snapshot = new CarSnapshot(id, floor, direction, stops.size(), inService);
    }
}

The ordering rule is the LOOK algorithm, named after the disk-head scheduler it comes from. It sweeps in one direction while stops remain ahead, then reverses. It prevents starvation: any stop is reached within at most two sweeps. A car going up passes a floor where someone wants to go down, unless that floor is the top of its sweep.

The dispatcher consumes the queue on its own thread. A set of assigned hall calls makes a second press a no-op. The strategy reference is volatile, so operations can swap it at run time.

public final class Dispatcher implements CarListener {
    private final Map<Integer, ElevatorCar> cars;
    private final BlockingQueue<Request> inbox = new LinkedBlockingQueue<>();
    private final Set<HallCall> assigned = ConcurrentHashMap.newKeySet();
    private final Queue<HallCall> unassigned = new ConcurrentLinkedQueue<>();   // no car in service
    private volatile DispatchStrategy strategy;

    // constructor elided

    public void submit(Request r)               { inbox.add(r); }   // button threads; never blocks
    public void setStrategy(DispatchStrategy s) { strategy = s; }

    void runLoop() throws InterruptedException {
        while (true) route(inbox.take());
    }

    private void route(Request r) {
        if (r instanceof CarCall c) {
            cars.get(c.carId()).addStop(c.floor(), StopKind.CAR);
        } else if (r instanceof HallCall h && assigned.add(h)) {
            List<CarSnapshot> view = cars.values().stream().map(ElevatorCar::snapshot).toList();
            strategy.choose(h, view).ifPresentOrElse(
                    id -> cars.get(id).addStop(h.floor(), StopKind.forHall(h.direction())),
                    () -> { assigned.remove(h); unassigned.add(h); });
        }
    }

    @Override public void onStopped(int carId, int floor, Set<StopKind> served) {
        for (StopKind k : served) {
            k.hallDirection().ifPresent(d -> assigned.remove(new HallCall(floor, d)));
        }
    }
}

Concurrency, edge cases and testing

Interviewer: Ten people press buttons in the same second while all four cars are moving. Why doesn't this corrupt anything, and why did you choose this locking?

You: There are three reasonable designs, and I picked the middle one.

Under my choice, ten presses become ten queue entries; LinkedBlockingQueue is thread-safe and producers never wait. The single dispatcher thread handles them one at a time, so de-duplication and assignment never race each other. Each addStop takes one car's lock briefly. The car thread releases its lock before touching the motor or calling the listener. So no thread ever holds two locks at once, which rules out deadlock by construction.

The dispatcher decides from snapshots that may be a few milliseconds old. That is fine, because a slightly stale view can only produce a slightly worse choice, never a wrong state. Correctness lives inside the car's lock. This is the same split as BookMyShow's seat map and hold in R19: approximate reads guide the decision, and the strict write lives in one place.

What's being probed: whether you can explain why your concurrency design is safe, not just say "I'll make it synchronized".

Concept — Confine mutable state, share immutable views. Give each piece of mutable state exactly one owner and one lock, keep critical sections short, never do slow I/O while holding a lock, and let other threads read published immutable snapshots. Deadlock needs a thread holding one lock while waiting for another; if no thread ever holds two, deadlock cannot happen. R8 covers the distributed version of the same idea with leases.

Takeaway: One owner per piece of mutable state, nothing slow under a lock, and stale-but-safe snapshots for anyone deciding from outside.

Edge cases:

Testing has three layers. Strategy tests feed hand-built snapshots and check the chosen car; they are pure functions. Car tests use a FakeMotor and FakeDoor that record calls, then call step() repeatedly on one thread and assert the sequence of floors and stops, so there are no sleeps or flaky timing. A simulation harness runs all four cars by calling step() round-robin against a seeded random traffic generator. It checks invariants (every hall call is eventually served, no car moves with its doors open) and reports average waiting time, so two strategies can be compared on the same traffic. A separate stress test hammers submit from many threads and checks that nothing is lost.

Extensions the interviewer will ask for

Interviewer: In the morning rush everyone goes up from the lobby. Can you do better?

You: Add a ZonedStrategy that assigns cars to floor bands (car 1 serves 2–6, car 2 serves 7–11, and so on) and returns idle cars to the lobby. A scheduler calls dispatcher.setStrategy(...) at 8:30 and back at 10:30. No other class changes, which is the reason the policy sits behind an interface.

Interviewer: The building switches to destination panels: people type their floor in the lobby.

You: A new request type, DestinationCall(from, to), added to the sealed Request. The compiler then points me to every place that must handle it. Add a DestinationStrategy that groups people going to nearby floors into the same car, and the panel shows which car to take. The car is unchanged: it still just gets stops.

Interviewer: Fire mode.

You: A fire alarm publishes an event. The dispatcher, as an Observer, stops accepting hall calls, clears every car's stops, and gives each car a single stop at the lobby with doors held open on arrival. Cars gain a FIRE_RECALL service mode that ignores car calls. This is the first time a car's behaviour truly differs by mode, so if more modes arrive (independent service, VIP), I would move the car's mode into State classes then.

Interviewer: Energy saving at night.

You: Another strategy: prefer a car that is already moving over waking an idle one, and park idle cars spread across the building. It plugs in the same way.

Quick reference

The 60-second version

I split the elevator system into deciding and doing. Button presses become HallCall and CarCall records on a blocking queue. One dispatcher thread drops duplicates and asks a pluggable DispatchStrategy to choose a car, using immutable snapshots of every car; the default scores distance plus a penalty for cars heading the other way. Each car owns its own stops in a TreeMap under its own lock and runs a LOOK loop: one floor at a time, stopping where a car call or a same-direction hall call waits, reversing when nothing is ahead. Motors and doors run outside the lock, and no thread ever holds two locks, so presses never wait on a moving car and deadlock is impossible. Cars report arrivals through a listener that clears hall lamps. Because the strategy is an interface and step() is separate from the thread, zoning, destination dispatch and fire mode plug in without rewrites, and every behaviour can be tested deterministically.

Walkthrough 3 — Snake and ladder: a game loop with clean entities

Building on the elevator: the elevator taught us to put the part most likely to change (the scheduling policy) behind a Strategy, and to split step() from the thread so tests control time. Snake and ladder looks like a toy, but interviewers use it to test exactly those habits, with a new twist: randomness. The game is a loop driven by dice. If the dice are hidden inside the game, you cannot test it, replay it or debug it. This walkthrough adds three habits: model data as data (a snake is not a class), make each rule variant a strategy, and treat randomness as a dependency you inject.

Scope and requirements

Interviewer: Design snake and ladder.

You: Quick recap of the game. Players take turns rolling a die and moving their token forward. Landing at the foot of a ladder moves you up to its top; landing on a snake's head moves you down to its tail. The first to reach the last cell wins. The rules vary a lot from house to house, which is the real design problem. Questions:

Interviewer: Board size configurable, 100 by default. Two to six players, one die by default. Make the finishing rule and the six rule configurable, since my family plays it differently from yours. Snakes and ladders come from configuration. I care most that it is extensible and testable.

You: Requirements, then.

Functional:

• Build a board of N cells with a set of snakes and ladders, rejecting invalid layouts.
• Two to six players take turns; each turn: roll, move, apply a snake or ladder, check for a win.
• Pluggable finishing rule: exact landing, bounce back, or overshoot allowed.
• Pluggable turn rule: plain turns, or a six rolls again with the third six cancelled.
• Report every move to whoever is listening (console, UI, log).

Constraints:

• Game logic does no input or output and never calls a global random number generator.
• Any game can be replayed exactly from its seed or its list of rolls.
• One game is turn-based and single-threaded; many games may run side by side.

The board is data, the rules are strategies, and randomness is a dependency you inject.

Entities and responsibilities

Interviewer: Classes. Do snakes and ladders each get one?

You: That is the classic trap. Nouns from the brief: board, cell, snake, ladder, player, token, die, turn, game, rule. A snake and a ladder have the same structure, a start cell and an end cell, and the same behaviour: if you land on the start, go to the end. They differ only in which way they point. Two classes, or a Snake extends Jump hierarchy, would add types without adding behaviour. So both are one record, Jump(from, to), and "is it a snake?" is just to < from.

Cells are the same story. A cell with no behaviour is just an integer, so I don't make a Cell class. Tokens are just a player's position. The verbs (roll, move, jump, win, next turn) belong to the Game, except where the brief says they vary: rolling (dice), finishing (end rule) and turn order (turn rule). Those become interfaces.

Positions belong to the game, not to Player. The same person can be in two games at once, and keeping all mutable state in Game means one object to save, restore or lock.

Class diagram

classDiagram
    class Game {
        -positions
        -int current
        -int bonusRolls
        +playTurn() Move
        +isOver() boolean
        +winner() Optional
    }
    class Board {
        -int size
        -Map jumps
        +of(size, jumps) Board
        +resolve(cell) int
        +jumpAt(cell) Optional
    }
    class Jump {
        <<record>>
        +from
        +to
        +isSnake() boolean
    }
    class Dice {
        <<interface>>
        +roll() Roll
    }
    class RandomDice
    class ScriptedDice
    class EndRule {
        <<interface>>
        +land(from, steps, size) int
    }
    class TurnRule {
        <<interface>>
        +decide(roll, bonusSoFar) TurnOutcome
    }
    class GameListener {
        <<interface>>
        +onMove(move)
        +onWin(player)
    }
    class Player {
        <<record>>
    }
    Game --> Board
    Game --> Dice
    Game --> EndRule
    Game --> TurnRule
    Game o-- Player
    Game --> GameListener
    Board *-- Jump
    Dice <|.. RandomDice
    Dice <|.. ScriptedDice

Board composes its jumps; they have no life outside it. Game only associates with Board, because the board is immutable and many games can share one instance. Everything that varies (dice, end rule, turn rule, listeners) is an interface the game depends on, so the game never names a concrete rule. That is dependency inversion from R23.

Key flows

Interviewer: Take me through one turn.

sequenceDiagram
    participant UI
    participant G as Game
    participant D as Dice
    participant T as TurnRule
    participant E as EndRule
    participant B as Board
    participant L as Listeners
    UI->>G: playTurn
    G->>D: roll
    D-->>G: Roll of 4
    G->>T: decide with bonus so far
    T-->>G: PASS
    G->>E: land from 12 by 4
    E-->>G: 16
    G->>B: resolve 16
    B-->>G: 6, a snake
    G->>L: onMove
    G->>G: win check, next player

1. The UI calls playTurn(). The game never waits for input itself; whoever drives it decides when a turn happens.
2. Dice.roll() returns a Roll. The game neither knows nor cares whether it came from a seeded generator or a test script.
3. TurnRule.decide says what this roll means for the turn. A third six in a row under SixRollsAgain(3) returns FORFEIT and the token does not move.
4. EndRule.land turns "from 12 by 4" into a landing cell. Near the end it applies the house rule: stay, bounce back, or stop at the last cell.
5. Board.resolve applies a jump if one starts there. Validation guaranteed jumps never chain, so one lookup is enough.
6. The game records a Move and tells every listener.
7. If the token is on the last cell, that player wins. Otherwise either the same player rolls again (a bonus roll) or the turn passes on.

Patterns used, and why

The core code

Interviewer: Show me the board and the turn logic.

You: The board validates in its factory method, so an invalid board cannot be constructed at all. I forbid a jump that ends where another starts. That removes loops (snake to ladder to the same snake) and keeps resolve to one lookup.

public record Jump(int from, int to) {
    public Jump {
        if (from == to) throw new IllegalArgumentException("a jump must move: " + from);
    }
    public boolean isSnake()  { return to < from; }
    public boolean isLadder() { return to > from; }
}

public final class Board {
    private final int size;
    private final Map<Integer, Jump> jumps;          // keyed by start cell

    private Board(int size, Map<Integer, Jump> jumps) {
        this.size = size;
        this.jumps = Map.copyOf(jumps);
    }

    public static Board of(int size, Collection<Jump> list) {
        if (size < 10) throw new IllegalArgumentException("board too small: " + size);
        Map<Integer, Jump> byStart = new HashMap<>();
        for (Jump j : list) {
            if (j.from() < 1 || j.from() >= size) throw invalid("must start inside the board, not on the last cell", j);
            if (j.to() < 1 || j.to() > size)      throw invalid("must end on the board", j);
            if (byStart.putIfAbsent(j.from(), j) != null) throw invalid("two jumps start on one cell", j);
        }
        for (Jump j : byStart.values()) {
            if (byStart.containsKey(j.to())) throw invalid("ends where another jump starts", j);
        }
        return new Board(size, byStart);
    }

    public int size()                      { return size; }
    public Optional<Jump> jumpAt(int cell) { return Optional.ofNullable(jumps.get(cell)); }
    public int resolve(int cell)           { Jump j = jumps.get(cell); return j == null ? cell : j.to(); }

    private static IllegalArgumentException invalid(String why, Jump j) {
        return new IllegalArgumentException("Invalid jump " + j + ": " + why);
    }
}

Dice return the individual faces, not just a total, because rules care about faces ("a six", "a double"). RandomDice takes a RandomGenerator (the Java 17 interface that java.util.Random implements), so a test or a replay can pass a seeded one. ScriptedDice plays back a fixed list.

public record Roll(List<Integer> faces) {
    public Roll { faces = List.copyOf(faces); }
    public int total()           { return faces.stream().mapToInt(Integer::intValue).sum(); }
    public boolean all(int face) { return faces.stream().allMatch(f -> f == face); }
}

public interface Dice { Roll roll(); }

public final class RandomDice implements Dice {
    private final int count, sides;
    private final RandomGenerator rng;

    public RandomDice(int count, int sides, RandomGenerator rng) {
        if (count < 1 || sides < 2) throw new IllegalArgumentException("bad dice");
        this.count = count; this.sides = sides; this.rng = rng;
    }

    @Override public Roll roll() {
        List<Integer> faces = new ArrayList<>(count);
        for (int i = 0; i < count; i++) faces.add(1 + rng.nextInt(sides));
        return new Roll(faces);
    }
}

public final class ScriptedDice implements Dice {
    private final Deque<Roll> script = new ArrayDeque<>();

    public static ScriptedDice of(int... singleDieRolls) {
        ScriptedDice d = new ScriptedDice();
        for (int r : singleDieRolls) d.script.add(new Roll(List.of(r)));
        return d;
    }

    @Override public Roll roll() {
        if (script.isEmpty()) throw new IllegalStateException("test script ran out of rolls");
        return script.removeFirst();
    }
}

The rules are small. The standard finishing rules are an enum that implements the interface, so they are ready to use, while anyone can still write a new EndRule class.

public interface EndRule {
    /** Cell the token lands on before any jump; returns `from` if the move is not allowed. */
    int land(int from, int steps, int size);
}

public enum EndRules implements EndRule {
    EXACT    { public int land(int from, int steps, int size) { return from + steps > size ? from : from + steps; } },
    BOUNCE   { public int land(int from, int steps, int size) { int t = from + steps; return t > size ? 2 * size - t : t; } },
    OVERSHOOT { public int land(int from, int steps, int size) { return Math.min(size, from + steps); } }
}

public enum TurnOutcome { PASS, ROLL_AGAIN, FORFEIT }

public interface TurnRule { TurnOutcome decide(Roll roll, int bonusRollsSoFar); }

public record PlainTurns() implements TurnRule {
    public TurnOutcome decide(Roll roll, int bonusSoFar) { return TurnOutcome.PASS; }
}

public record SixRollsAgain(int limit) implements TurnRule {      // limit 3: the third six in a row is cancelled
    public TurnOutcome decide(Roll roll, int bonusSoFar) {
        if (!roll.all(6)) return TurnOutcome.PASS;
        return bonusSoFar + 1 >= limit ? TurnOutcome.FORFEIT : TurnOutcome.ROLL_AGAIN;
    }
}

The game owns only sequencing and state. Positions start at 0, meaning "not yet on the board". Each turn asks each collaborator one question.

public record Move(Player player, Roll roll, int from, int to, Optional<Jump> jump, TurnOutcome outcome) {}

public final class Game {
    private final Board board;
    private final Dice dice;
    private final EndRule endRule;
    private final TurnRule turnRule;
    private final List<Player> players;
    private final List<GameListener> listeners;
    private final int[] positions;                 // 0 = not yet on the board
    private int current;
    private int bonusRolls;
    private Player winner;

    // private constructor called by Game.Builder, which supplies defaults:
    // Boards.standard(), new RandomDice(1, 6, new Random()), EndRules.EXACT, new SixRollsAgain(3)

    public Move playTurn() {
        if (winner != null) throw new IllegalStateException("game is over");
        Player player = players.get(current);
        Roll roll = dice.roll();
        TurnOutcome outcome = turnRule.decide(roll, bonusRolls);

        int from = positions[current];
        int to = from;
        Optional<Jump> jump = Optional.empty();
        if (outcome != TurnOutcome.FORFEIT) {
            int landed = endRule.land(from, roll.total(), board.size());
            jump = board.jumpAt(landed);
            to = board.resolve(landed);
            positions[current] = to;
        }

        Move move = new Move(player, roll, from, to, jump, outcome);
        listeners.forEach(l -> l.onMove(move));

        if (to == board.size()) {
            winner = player;
            listeners.forEach(l -> l.onWin(player));
        } else if (outcome == TurnOutcome.ROLL_AGAIN) {
            bonusRolls++;
        } else {
            bonusRolls = 0;
            current = (current + 1) % players.size();
        }
        return move;
    }

    public boolean isOver()           { return winner != null; }
    public Optional<Player> winner()  { return Optional.ofNullable(winner); }
}

The console version is three lines: build a game with a ConsolePrinter listener, then while (!game.isOver()) game.playTurn();. A UI calls playTurn() from a button handler instead. Neither needs a different Game.

Concurrency, edge cases and testing

Interviewer: The whole game depends on random dice. How do you test it?

You: By never letting the game reach for randomness itself. Dice is injected, so a test hands it a script and checks exact positions. Here is a full game on a 20-cell board, with the exact finishing rule and plain turns:

@Test
void ladderOvershootAndExactFinish() {
    Board board = Board.of(20, List.of(new Jump(3, 15), new Jump(18, 2)));
    Game game = Game.builder()
            .board(board)
            .players("Asha", "Ravi")
            .dice(ScriptedDice.of(3, 1, 6, 2, 5))
            .endRule(EndRules.EXACT)
            .turnRule(new PlainTurns())
            .build();

    assertEquals(15, game.playTurn().to());     // Asha rolls 3, climbs the ladder from 3 to 15
    assertEquals(1,  game.playTurn().to());     // Ravi rolls 1
    assertEquals(15, game.playTurn().to());     // Asha rolls 6: 21 overshoots 20, so she stays
    assertEquals(15, game.playTurn().to());     // Ravi rolls 2, lands on 3, climbs to 15
    assertEquals(20, game.playTurn().to());     // Asha rolls 5, exactly 20
    assertEquals("Asha", game.winner().orElseThrow().name());
}

For broader checks I use seeded dice: new RandomDice(1, 6, new Random(seed)). The same seed produces the same game every time. I run thousands of seeded games and check invariants after every move: positions stay between 0 and the board size, no token ever rests on the start of a jump, and every game ends within a turn cap. When one fails, the test prints the seed, and that seed reproduces the bug on any machine. In production I log the seed (or the list of rolls) with each game, so a disputed game can be replayed exactly.

What's being probed: whether you treat randomness, like time and I/O, as a dependency to inject rather than a global to call.

Concept — Inject the source of non-determinism. Anything that makes a run unrepeatable (random numbers, the clock, the network) should come in through an interface. In tests you pass a script or a fixed seed; in production you pass the real thing. A seed is a starting number for a pseudo-random generator; the same seed always produces the same sequence, which turns a "random" bug into a reproducible one. R23's dependency inversion principle is the general rule; the elevator's fake motor was the same idea for time.

Takeaway: If a class calls new Random() or Instant.now() inside its logic, it cannot be tested exactly; pass those in.

Concurrency is simple because the game is turn-based. One game is single-threaded: only the current player can act. In an online version, each game's commands are processed one at a time (one actor or one lock per game), and each command carries the turn number it expects. A double-click or a late request from the previous turn carries a stale number and is rejected. Many games run in parallel with no shared mutable state; the shared Board is immutable, so sharing it is free.

Edge cases:

Extensions the interviewer will ask for

Interviewer: House rule: you need a six to get onto the board.

You: Add an EntryRule interface, asked only when a token is at position 0: NoEntryRule always lets it in, SixToEnter requires roll.all(6). The game gains one if (from == 0 && !entryRule.mayEnter(roll)) before landing. Existing rules are untouched.

Interviewer: Play with two dice, and doubles roll again.

You: new RandomDice(2, 6, rng) already works, because Roll carries faces. Add a DoublesRollAgain turn rule that checks whether the two faces are equal. That is a new class, and no existing class changes.

Interviewer: Special cells: "miss a turn", "roll again".

You: This is the one real change. A jump is one kind of cell effect, so I generalise: sealed interface CellEffect permits Jump, SkipTurn, ExtraRoll, and Board maps cells to effects. The game switches over the effect. Because the interface is sealed, the compiler lists every place that must handle the new types. Snakes and ladders keep working as Jump effects.

Interviewer: Undo and replay.

You: Every Move is already recorded. Replay is building the same game with a ScriptedDice made from the recorded rolls. Undo is replaying all but the last move, which is cheap for a game this small, and it avoids writing inverse operations. Chess, next, is where undo needs real design.

Quick reference

The 60-second version

Snake and ladder is a test of clean modelling. The board is data: an immutable Board of N cells with Jump(from, to) records, where a snake is simply a jump that goes down. It is validated once in a factory method so loops and illegal jumps cannot exist, and it can be shared by many games. The Game owns positions and sequencing only. Each turn it asks injected collaborators one question each: the Dice for a roll, the TurnRule whether this roll passes, repeats or is forfeited, the EndRule where the token lands near the end, and the board whether a jump applies. Listeners hear every move. Because randomness is injected, a scripted die gives exact unit tests and a seeded one gives reproducible simulations and replayable disputes. New house rules, extra dice and special cells arrive as new classes, not rewrites.

Walkthrough 4 — Chess: a rich rule set with polymorphism and undo

Building on snake and ladder: there, the rules were a few small strategies and undo was "replay everything but the last move". Chess raises both. Six piece types move differently, a move is legal only if it does not expose your own king, special moves (castling, en passant, promotion) break the simple patterns, and the game ends on positions (checkmate, stalemate) rather than on a cell number. This walkthrough adds polymorphism for behaviour that varies by type, a generate-then-filter approach to legality, and the Command pattern with real undo, which also powers the legality check itself.

Scope and requirements

Interviewer: Design a chess game.

You: Chess has a lot of rules, so scope matters more than usual. Questions:

Interviewer: Two human players on one machine for now. Full rules including castling, en passant and promotion. Checkmate, stalemate, resignation and the fifty-move rule; repetition if time allows. Undo is required. Yes to loading positions.

You: Requirements, then.

Functional:

• Set up the standard starting position, or any position from FEN.
• Accept a move (from, to, optional promotion piece); reject it unless it is legal.
• Support castling, en passant and promotion.
• After each move, report check, checkmate, stalemate or a fifty-move draw.
• Undo any number of moves.
• Resign.

Constraints:

• Rules live in the domain model, independent of any UI.
• Legal-move generation must be correct first and reasonably fast; an engine may be added later.
• Every move must be reversible exactly, including castling rights and the en passant square.

A move is legal only if your own king is not attacked after it, so generate each piece's moves by its pattern, then filter by making the move, testing the king, and undoing it.

Entities and responsibilities

Interviewer: Classes. Where does "how a knight moves" live?

You: Nouns: game, board, square, piece (six kinds), colour, player, move, history, clock. Verbs: move, capture, castle, promote, check, undo, resign. "How a piece moves" changes by piece type, which is the textbook case for polymorphism: each piece answers "what are your moves from here?" instead of one giant switch on piece type. Two things keep pieces simple. First, a piece does not store its square; the board maps squares to pieces. Otherwise every move would update the board and the piece, and the two copies could disagree. Second, "is this move legal?" is not a per-piece question, because it depends on where your king is. That lives in a separate Rules class.

Class diagram

classDiagram
    class Game {
        -Deque history
        -GameStatus status
        +play(from, to, promotion) GameStatus
        +undo()
        +resign(color)
    }
    class Position {
        -Color sideToMove
        -CastlingRights rights
        -Square enPassant
        -int halfmoveClock
    }
    class Board {
        -grid
        +at(square) Piece
        +put(square, piece)
        +kingSquare(color) Square
    }
    class Piece {
        <<interface>>
        +color() Color
        +pseudoLegalMoves(position, from) List
        +attacks(board, from, target) boolean
    }
    class King
    class Queen
    class Rook
    class Bishop
    class Knight
    class Pawn
    class Move {
        <<record>>
    }
    class MoveCommand {
        +execute()
        +undo()
    }
    class Rules {
        +legalMoves(position) List
        +isAttacked(board, square, by) boolean
        +status(position) GameStatus
    }
    Game *-- Position
    Game *-- MoveCommand : history
    Position *-- Board
    Board o-- Piece
    Piece <|.. King
    Piece <|.. Queen
    Piece <|.. Rook
    Piece <|.. Bishop
    Piece <|.. Knight
    Piece <|.. Pawn
    MoveCommand --> Move
    MoveCommand --> Position : mutates
    Rules ..> Piece
    Rules ..> MoveCommand
    Game ..> Rules

Game composes the position and the history; Position composes the board. The board only aggregates pieces: pieces are immutable records with no square, so one Rook(WHITE) value could stand on any square, and two white rooks are equal values. Piece is a sealed interface, so the compiler knows there are exactly six kinds. Rules depends on pieces and commands but holds no state.

Key flows

Interviewer: White plays e2 to e4. What happens?

sequenceDiagram
    participant P as Player
    participant G as Game
    participant R as Rules
    participant PC as Piece
    participant C as MoveCommand
    P->>G: play e2 e4
    G->>R: legalMoves for position
    loop each own piece
        R->>PC: pseudoLegalMoves
        PC-->>R: candidate moves
        R->>C: execute, is own king attacked, undo
    end
    R-->>G: legal moves
    G->>G: find the e2 to e4 move
    G->>C: execute and push to history
    G->>R: status for the side to move
    R-->>G: IN_PROGRESS
    G-->>P: status

1. Game.play asks Rules for every legal move in the position.
2. For each of White's pieces, Rules asks the piece for its pseudo-legal moves: moves that follow its movement pattern and respect blockers, without yet worrying about check. The pawn on e2 offers e3 and e4 (a double push).
3. For each candidate, Rules executes a MoveCommand, checks whether White's king is now attacked, and undoes the command. Candidates that expose the king are dropped.
4. Game looks for a legal move matching e2 to e4 (and the promotion piece, if any). No match means an illegal move, which is rejected with no change.
5. It executes that move's command and pushes it on the history stack. The command sets the en passant square to e3, because a black pawn on d4 or f4 could now capture en passant.
6. Rules.status looks at the new side to move. No legal moves while in check is checkmate; no legal moves and not in check is stalemate; otherwise check or in progress.

Interviewer: Why generate moves that might be illegal and then filter? Why not have each piece generate only legal moves?

You: Because legality is not about the moving piece. A bishop's move can be illegal because it was pinned, meaning it shields its own king from an enemy rook. A king's move is illegal if the square is attacked. A pawn's en passant capture can be illegal because removing two pawns from a rank opens a line to the king. Each piece would need to understand the whole board and every enemy piece. Filtering asks one simple question after the fact (is my king attacked now?), and it gets pins, discovered attacks and en passant right with no special code. The cost is a make, a test and an undo per candidate. With around 30 candidates per position, that is trivial for two humans, and engines use the same make/unmake approach with faster data structures.

The one thing filtering cannot catch is castling through check, because after castling the king has left the square it crossed. So the king checks that one itself while generating castling moves.

What's being probed: whether you put each rule where its information lives, rather than forcing a per-piece model to answer a whole-board question.

Concept — Generate, then filter. When a rule depends on global state (here, the king's safety), split the job: a local generator proposes candidates using local knowledge (how this piece moves), and a global filter rejects candidates by checking the result. It is the same shape as "propose, then validate" in many systems. R23's single responsibility principle explains why: the piece owns movement, and Rules owns legality.

Takeaway: Pieces know how they move; only the rules engine knows whether a move is legal, and it finds out by trying it.

Patterns used, and why

The core code

Interviewer: Show me piece movement, check detection and the move command.

You: Basic types first. A Move carries everything needed to undo it, including the captured piece. captured and promotion are null when they don't apply.

public enum Color { WHITE, BLACK; public Color opposite() { return this == WHITE ? BLACK : WHITE; } }

public record Square(int file, int rank) {                   // file 0..7 = a..h, rank 0..7 = 1..8
    public Square {
        if (file < 0 || file > 7 || rank < 0 || rank > 7) throw new IllegalArgumentException("off board");
    }
    public Optional<Square> offset(int df, int dr) {
        int f = file + df, r = rank + dr;
        return (f < 0 || f > 7 || r < 0 || r > 7) ? Optional.empty() : Optional.of(new Square(f, r));
    }
    public static Square parse(String s) { return new Square(s.charAt(0) - 'a', s.charAt(1) - '1'); }
}

public enum MoveKind { NORMAL, DOUBLE_PUSH, EN_PASSANT, CASTLE_KING_SIDE, CASTLE_QUEEN_SIDE, PROMOTION }

public record Move(Square from, Square to, Piece piece, Piece captured, MoveKind kind, Piece promotion) {
    static Move normal(Square from, Square to, Piece piece, Piece captured) {
        return new Move(from, to, piece, captured, MoveKind.NORMAL, null);
    }
}

public sealed interface Piece permits King, Queen, Rook, Bishop, Knight, Pawn {
    Color color();
    /** Moves allowed by this piece's pattern and blockers; may still leave its own king in check. */
    List<Move> pseudoLegalMoves(Position pos, Square from);
    /** Would this piece, standing on `from`, attack `target`? Never includes castling. */
    boolean attacks(Board board, Square from, Square target);
}

Sliding pieces (rook, bishop, queen) differ only in their directions, and stepping pieces (knight, king) only in their offsets. So the shared walking logic sits in one helper, and each piece is a few lines.

final class Rays {
    static final int[][] ROOK   = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static final int[][] BISHOP = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    static final int[][] QUEEN  = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    static final int[][] KNIGHT = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};

    static List<Move> slide(Board b, Square from, Piece p, int[][] dirs) {
        List<Move> out = new ArrayList<>();
        for (int[] d : dirs) {
            for (Optional<Square> s = from.offset(d[0], d[1]); s.isPresent(); s = s.get().offset(d[0], d[1])) {
                Piece other = b.at(s.get());
                if (other == null) { out.add(Move.normal(from, s.get(), p, null)); continue; }
                if (other.color() != p.color()) out.add(Move.normal(from, s.get(), p, other));
                break;                                             // blocked either way
            }
        }
        return out;
    }

    static List<Move> step(Board b, Square from, Piece p, int[][] offsets) {
        List<Move> out = new ArrayList<>();
        for (int[] d : offsets) {
            from.offset(d[0], d[1]).ifPresent(to -> {
                Piece other = b.at(to);
                if (other == null || other.color() != p.color()) out.add(Move.normal(from, to, p, other));
            });
        }
        return out;
    }

    static boolean rayHits(Board b, Square from, Square target, int[][] dirs) {
        for (int[] d : dirs) {
            for (Optional<Square> s = from.offset(d[0], d[1]); s.isPresent(); s = s.get().offset(d[0], d[1])) {
                if (s.get().equals(target)) return true;
                if (b.at(s.get()) != null) break;
            }
        }
        return false;
    }

    static boolean stepHits(Square from, Square target, int[][] offsets) {
        for (int[] d : offsets) {
            if (from.file() + d[0] == target.file() && from.rank() + d[1] == target.rank()) return true;
        }
        return false;
    }
}

public record Rook(Color color) implements Piece {
    public List<Move> pseudoLegalMoves(Position pos, Square from) { return Rays.slide(pos.board(), from, this, Rays.ROOK); }
    public boolean attacks(Board b, Square from, Square target)   { return Rays.rayHits(b, from, target, Rays.ROOK); }
}
// Bishop and Queen are identical apart from Rays.BISHOP and Rays.QUEEN.

public record Knight(Color color) implements Piece {
    public List<Move> pseudoLegalMoves(Position pos, Square from) { return Rays.step(pos.board(), from, this, Rays.KNIGHT); }
    public boolean attacks(Board b, Square from, Square target)   { return Rays.stepHits(from, target, Rays.KNIGHT); }
}

The pawn is the odd one out: it moves straight but captures diagonally, has a double first step, captures en passant and promotes. Note that attacks is not derived from its moves. A pawn attacks diagonally even when nothing is there to capture, and its forward push never attacks anything.

public record Pawn(Color color) implements Piece {
    private int forward()   { return color == Color.WHITE ? 1 : -1; }
    private int startRank() { return color == Color.WHITE ? 1 : 6; }
    private int lastRank()  { return color == Color.WHITE ? 7 : 0; }

    public List<Move> pseudoLegalMoves(Position pos, Square from) {
        Board b = pos.board();
        List<Move> out = new ArrayList<>();
        from.offset(0, forward()).filter(s -> b.at(s) == null).ifPresent(one -> {
            advance(out, from, one, null);
            if (from.rank() == startRank()) {
                one.offset(0, forward()).filter(s -> b.at(s) == null)
                   .ifPresent(two -> out.add(new Move(from, two, this, null, MoveKind.DOUBLE_PUSH, null)));
            }
        });
        for (int df : new int[] {-1, 1}) {
            from.offset(df, forward()).ifPresent(to -> {
                Piece target = b.at(to);
                if (target != null && target.color() != color) advance(out, from, to, target);
                else if (to.equals(pos.enPassant()))
                    out.add(new Move(from, to, this, new Pawn(color.opposite()), MoveKind.EN_PASSANT, null));
            });
        }
        return out;
    }

    private void advance(List<Move> out, Square from, Square to, Piece captured) {
        if (to.rank() != lastRank()) { out.add(Move.normal(from, to, this, captured)); return; }
        for (Piece p : List.of(new Queen(color), new Rook(color), new Bishop(color), new Knight(color))) {
            out.add(new Move(from, to, this, captured, MoveKind.PROMOTION, p));
        }
    }

    public boolean attacks(Board b, Square from, Square target) {
        return target.rank() == from.rank() + forward() && Math.abs(target.file() - from.file()) == 1;
    }
}

The king adds castling. Castling rights already guarantee that the king and rook have never moved. The king checks three things: the squares between are empty, it is not in check now, and it does not pass through an attacked square. Landing in check is caught by the general filter. Because attacks never includes castling, Rules.isAttacked can safely call it without recursing back into castling generation.

public record King(Color color) implements Piece {
    public List<Move> pseudoLegalMoves(Position pos, Square from) {
        List<Move> out = Rays.step(pos.board(), from, this, Rays.QUEEN);
        Board b = pos.board();
        int r = from.rank();
        Color enemy = color.opposite();
        if (Rules.isAttacked(b, from, enemy)) return out;                        // no castling out of check
        if (pos.rights().kingSide(color) && empty(b, r, 5, 6) && !Rules.isAttacked(b, new Square(5, r), enemy))
            out.add(new Move(from, new Square(6, r), this, null, MoveKind.CASTLE_KING_SIDE, null));
        if (pos.rights().queenSide(color) && empty(b, r, 1, 3) && !Rules.isAttacked(b, new Square(3, r), enemy))
            out.add(new Move(from, new Square(2, r), this, null, MoveKind.CASTLE_QUEEN_SIDE, null));
        return out;
    }
    private static boolean empty(Board b, int rank, int fromFile, int toFile) {
        for (int f = fromFile; f <= toFile; f++) if (b.at(new Square(f, rank)) != null) return false;
        return true;
    }
    public boolean attacks(Board b, Square from, Square target) { return Rays.stepHits(from, target, Rays.QUEEN); }
}

The command saves exactly what it overwrites: castling rights, the en passant square and the fifty-move counter. The pieces themselves are restored from the Move. execute and undo mirror each other line for line, which makes them easy to review.

public final class MoveCommand {
    private final Position pos;
    private final Move m;
    private CastlingRights prevRights;
    private Square prevEnPassant;
    private int prevHalfmove;

    public MoveCommand(Position pos, Move m) { this.pos = pos; this.m = m; }

    public void execute() {
        prevRights = pos.rights(); prevEnPassant = pos.enPassant(); prevHalfmove = pos.halfmoveClock();
        Board b = pos.board();
        int r = m.from().rank();
        b.remove(m.from());
        switch (m.kind()) {
            case EN_PASSANT -> b.remove(new Square(m.to().file(), r));      // captured pawn sits beside, not on `to`
            case CASTLE_KING_SIDE -> b.relocate(new Square(7, r), new Square(5, r));
            case CASTLE_QUEEN_SIDE -> b.relocate(new Square(0, r), new Square(3, r));
            default -> { }
        }
        b.put(m.to(), m.kind() == MoveKind.PROMOTION ? m.promotion() : m.piece());
        pos.setEnPassant(m.kind() == MoveKind.DOUBLE_PUSH ? new Square(m.from().file(), (r + m.to().rank()) / 2) : null);
        pos.setRights(prevRights.after(m));
        pos.setHalfmoveClock(m.piece() instanceof Pawn || m.captured() != null ? 0 : prevHalfmove + 1);
        pos.switchSide();
    }

    public void undo() {
        pos.switchSide();
        Board b = pos.board();
        int r = m.from().rank();
        b.remove(m.to());
        b.put(m.from(), m.piece());                                          // a promoted piece reverts to the pawn
        switch (m.kind()) {
            case EN_PASSANT -> b.put(new Square(m.to().file(), r), m.captured());
            case CASTLE_KING_SIDE -> b.relocate(new Square(5, r), new Square(7, r));
            case CASTLE_QUEEN_SIDE -> b.relocate(new Square(3, r), new Square(0, r));
            default -> { if (m.captured() != null) b.put(m.to(), m.captured()); }
        }
        pos.setRights(prevRights); pos.setEnPassant(prevEnPassant); pos.setHalfmoveClock(prevHalfmove);
    }
}

Rules brings it together. Check detection asks every enemy piece whether it attacks the king's square, which is 16 cheap calls at most. squaresOf returns a fresh list, because the filter changes the board while we loop.

public final class Rules {
    public static List<Move> legalMoves(Position pos) {
        Color us = pos.sideToMove();
        List<Move> legal = new ArrayList<>();
        for (Square sq : pos.board().squaresOf(us)) {
            for (Move m : pos.board().at(sq).pseudoLegalMoves(pos, sq)) {
                MoveCommand c = new MoveCommand(pos, m);
                c.execute();
                if (!isInCheck(pos, us)) legal.add(m);
                c.undo();
            }
        }
        return legal;
    }

    public static boolean isInCheck(Position pos, Color c) {
        return isAttacked(pos.board(), pos.board().kingSquare(c), c.opposite());
    }

    public static boolean isAttacked(Board b, Square target, Color by) {
        for (Square sq : b.squaresOf(by)) if (b.at(sq).attacks(b, sq, target)) return true;
        return false;
    }

    public static GameStatus status(Position pos) {
        boolean check = isInCheck(pos, pos.sideToMove());
        if (legalMoves(pos).isEmpty()) return check ? GameStatus.CHECKMATE : GameStatus.STALEMATE;
        if (pos.halfmoveClock() >= 100) return GameStatus.DRAW_FIFTY_MOVES;   // 50 moves by each side
        return check ? GameStatus.CHECK : GameStatus.IN_PROGRESS;
    }
}

Game.play finds the matching legal move (comparing from, to and the promotion piece; records compare by value), executes its command, pushes it on a Deque<MoveCommand>, recomputes the status and notifies listeners. Game.undo pops and undoes. Both are a few lines and are elided here.

Concurrency, edge cases and testing

Interviewer: How do you know the move generator is right? Chess has a lot of corner cases.

You: With perft, short for performance test, the standard check for chess move generators. It counts every legal move sequence to a fixed depth from a position, and compares the count with published values. From the starting position the counts are 20 at depth 1, 400 at depth 2, 8,902 at depth 3 and 197,281 at depth 4. A wrong en passant, castling or pin rule changes those numbers. Well-known test positions full of castling, promotion and en passant traps have published counts too. Perft also exercises undo heavily, because every sequence is made and unmade. Any undo bug corrupts the counts.

Then I add scenario tests that read like games. Fool's mate is the shortest checkmate:

@Test
void foolsMate() {
    Game g = Game.standard();
    g.play(sq("f2"), sq("f3"), null);
    g.play(sq("e7"), sq("e5"), null);
    g.play(sq("g2"), sq("g4"), null);
    assertEquals(GameStatus.CHECKMATE, g.play(sq("d8"), sq("h4"), null));
}

@Test
void stalemateIsNotCheckmate() {
    Game g = Game.fromFen("7k/5K2/6Q1/8/8/8/8/8 b - - 0 1");   // black king h8, white king f7, queen g6
    assertEquals(GameStatus.STALEMATE, g.status());
}

Edge cases:

Extensions the interviewer will ask for

Interviewer: Add a computer opponent.

You: Introduce a Player interface with HumanPlayer (waits for UI input) and EnginePlayer. The engine searches ahead with minimax and alpha-beta pruning, using Rules.legalMoves and the same MoveCommand make/undo. Nothing in the rules changes. The search algorithm is itself a strategy, so a weaker "beginner" engine is another class.

Interviewer: Add chess clocks with increments.

You: A ChessClock listens for moves (Observer) and switches sides. A TimeControl strategy decides what happens on each move: add an increment, apply a delay, or nothing. Running out of time becomes a status the game reads from the clock. Undo in a timed game is simply refused.

Interviewer: Support Chess960, where the back row starts shuffled.

You: A factory builds the starting position from one of the 960 legal arrangements. Castling generalises: CastlingRights stores which file each rook started on, and the king's castling code checks the squares between those files. The pieces' movement code does not change.

Interviewer: Spectators and game export.

You: A spectator is another GameListener. Export walks the MoveCommand history and writes standard algebraic notation into PGN, the standard text format for recorded games.

Quick reference

The 60-second version

Chess is about putting each rule where its information lives. Pieces are a sealed interface with six immutable records. Each knows only its movement pattern (sliding or stepping, sharing one helper) and which squares it attacks; none stores its square, because the board is the single source of truth. A Position adds side to move, castling rights, the en passant square and the fifty-move counter. Legality is a whole-board question, so Rules generates every piece's pseudo-legal moves, then makes each with a MoveCommand, checks whether its own king is attacked, and undoes it. That one filter handles pins, discovered checks and en passant, and only castling through check needs special code in the king. The same command gives user undo. After each move, no legal moves means checkmate if in check and stalemate if not. Perft counts against published values prove the generator, and engines, clocks and Chess960 plug in without touching piece movement.

Walkthrough 5 — Blackjack: cards, hands and money at one table

Building on chess: chess was a deep rule set between two players with perfect information. Blackjack is shallower but brings back everything from the earlier walkthroughs at once. Money moves, as in the ATM. A dealer follows fixed rules that casinos vary, a strategy as in the elevator. Randomness from a shuffled shoe must be injectable, as in snake and ladder. And there is a value that is not just a number: an ace counts as 1 or 11. This walkthrough adds the modelling of a hand value that carries its own ambiguity, a phase machine for a betting round, and settlement that keeps every paisa accounted for across several players and split hands.

Scope and requirements

Interviewer: Design a blackjack game for a casino table.

You: A recap of the rules. Each player bets, then gets two cards face up; the dealer gets one card up and one face down (the hole card). Number cards count their number, J, Q and K count 10, and an ace counts 1 or 11, whichever helps. Players draw cards (hit) or stop (stand), trying to get closer to 21 than the dealer without going over (bust). Then the dealer plays by fixed rules. Two cards making 21 is a blackjack, which usually pays 3 to 2. Questions:

Interviewer: A six-deck shoe, reshuffled once about three quarters have been dealt. Up to five seats. Hit, stand, double and split; insurance and surrender later. Dealer stands on soft 17 by default, but it must be configurable. Blackjack pays 3:2. Players have a wallet with the casino; amounts in paise.

You: Requirements, then.

Functional:

• Run rounds: take bets, deal, let each hand act in turn, play the dealer, settle every hand.
• Actions: hit, stand, double (one more card, bet doubled), split a pair into two hands.
• Configurable dealer rule (stand or hit on soft 17) and payout policy.
• Reshuffle the shoe between rounds once the cut card has been passed.
• Debit bets and credit payouts to each player's wallet.

Constraints:

• Hand values must be right for every mix of aces.
• Money: integers in paise; bets in whole rupees, so 3:2 is always an exact integer.
• No money created or lost: across any number of rounds, player wallet changes plus the house result must sum to zero.
• Shuffling is injected, so any round can be reproduced in a test.
• One table's actions are processed in order; many tables run in parallel.

Entities and responsibilities

Interviewer: Classes. And how do you deal with the ace?

You: Nouns: card, rank, suit, deck, shoe, hand, player, dealer, bet, wallet, table, round, payout. Verbs: shuffle, deal, hit, stand, double, split, settle. The ace is the interesting part. The tempting model is int value() with a special case somewhere. But "soft 17" (a 17 where an ace still counts 11, such as ace and 6) behaves differently from "hard 17" (10, 7) for the dealer, and both are 17. So a hand's value is not one number. It is a pair: the best total, and whether that total is soft, meaning an ace is still counting as 11 and could drop to 1 if needed.

Computing it is simple once you notice one fact: at most one ace can ever count as 11, because two would already make 22. So count every ace as 1, and if there is an ace and adding 10 keeps the total at 21 or below, add 10 and call the hand soft. Every rule then reads from that pair: blackjack is two cards totalling 21, bust is a total over 21, and the dealer's soft-17 rule checks total == 17 && soft.

A hand's value is a pair, the best total and whether an ace is still counting as 11, and every rule (blackjack, bust, soft 17) reads from that pair.

What's being probed: whether you spot that an ambiguous value needs a richer type, instead of patching an int with special cases at every call site.

Concept — Make the value object carry the ambiguity. When a quantity has more than one meaning (an ace as 1 or 11, a price with or without tax, an amount in some currency), give it a small immutable type that holds what the rules need. Then compute it in exactly one place. Here HandValue(total, soft) is computed by one static method, and the dealer rule, the bust check and blackjack detection all use it. R23's value objects and single responsibility cover the general idea; the Money record in the ATM was the same move.

Takeaway: If two things that look equal behave differently, your type is missing a field; add it and compute it in one place.

Class diagram

classDiagram
    class Table {
        -CardSource shoe
        +newRound() Round
    }
    class Round {
        -Phase phase
        -List hands
        -Hand dealer
        +placeBet(player, amount)
        +deal()
        +act(player, action)
    }
    class Hand {
        -List cards
        -long bet
        -boolean fromSplit
        +value() HandValue
        +isBlackjack() boolean
        +canSplit() boolean
    }
    class HandValue {
        <<record>>
        +total
        +soft
    }
    class Card {
        <<record>>
    }
    class CardSource {
        <<interface>>
        +draw() Card
        +pastCutCard() boolean
        +shuffle()
    }
    class Shoe
    class StackedShoe
    class DealerStrategy {
        <<interface>>
        +shouldHit(value) boolean
    }
    class PayoutPolicy {
        <<interface>>
        +blackjackWinnings(bet) long
    }
    class Settlement {
        +creditFor(hand, dealer) long
    }
    class Wallet {
        <<interface>>
        +debit(ref, player, amount)
        +credit(ref, player, amount)
    }
    Table *-- Round : current
    Table --> CardSource
    Round *-- Hand
    Hand o-- Card
    Hand ..> HandValue : computes
    Round --> DealerStrategy
    Round --> Settlement
    Settlement --> PayoutPolicy
    Round --> Wallet
    CardSource <|.. Shoe
    CardSource <|.. StackedShoe

A round composes its hands; they mean nothing after settlement. Hands aggregate cards, which come from and return to the shoe. The four interfaces (card source, dealer rule, payout policy and wallet) are exactly the four things the interviewer said vary or live elsewhere. HandValue is computed on demand, not stored, so it can never go stale when a card is added.

Key flows

Interviewer: Take me through a round.

stateDiagram-v2
    [*] --> Betting
    Betting --> Settled : deal, dealer has blackjack
    Betting --> PlayerTurns : deal
    PlayerTurns --> PlayerTurns : hit, double, split, next hand
    PlayerTurns --> DealerTurn : every hand finished
    DealerTurn --> Settled : dealer stands or busts
    Settled --> [*]

1. Betting. Each player places a bet. The wallet is debited at once, with reference roundId:handId:bet, so the stake is held while the round runs. A player cannot spend it elsewhere mid-round.
2. Deal. Two passes: one card to each hand, then one to the dealer. The dealer's second card is the hole card.
3. Peek. If the dealer has blackjack, the round settles immediately: everyone loses except a player blackjack, which pushes (the stake is returned). The dealer can only have blackjack when the up card is an ace or a ten-value, which is when a real dealer peeks.
4. Player turns. Hands act in seat order. A hand finishes when it stands, busts, reaches 21 or doubles. A player blackjack finishes immediately. A split inserts the new hand right after the current one, so it plays next.
5. Dealer turn. If any hand is still live (not bust and not a blackjack), the dealer reveals the hole card and hits while the DealerStrategy says so. No player choice is involved.
6. Settlement. For each hand, Settlement computes what to credit back (stake plus winnings, the stake alone for a push, or nothing). The wallet is credited with reference roundId:handId:settle.
7. Between rounds, the table checks pastCutCard() and reshuffles if needed. Mid-round reshuffles never happen.

Patterns used, and why

The core code

Interviewer: Show me hand values, the dealer rule and settlement.

You: Cards and the value calculation. Rank stores base points with the ace as 1; HandValue.of is the only place that decides whether an ace counts 11.

public enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES }

public 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(1);
    public final int points;
    Rank(int points) { this.points = points; }
}

public record Card(Rank rank, Suit suit) {}

public record HandValue(int total, boolean soft) {
    public static HandValue of(List<Card> cards) {
        int hard = 0;
        boolean hasAce = false;
        for (Card c : cards) {
            hard += c.rank().points;
            hasAce |= c.rank() == Rank.ACE;
        }
        // At most one ace can count as 11: two would make 22.
        return (hasAce && hard + 10 <= 21) ? new HandValue(hard + 10, true) : new HandValue(hard, false);
    }
    public boolean bust() { return total > 21; }
}

A Hand holds the cards and the bet, and knows the rule-related questions about itself. A hand reaching 21 or more finishes automatically, which also finishes a natural blackjack the moment it is dealt. A 21 made after a split is not a blackjack, which is why the hand remembers where it came from.

public final class Hand {
    private final String id;
    private final String playerId;
    private final List<Card> cards = new ArrayList<>();
    private boolean fromSplit;
    private long bet;
    private boolean finished;

    public Hand(String id, String playerId, long bet, boolean fromSplit) {
        this.id = id; this.playerId = playerId; this.bet = bet; this.fromSplit = fromSplit;
    }

    public void add(Card c) {
        cards.add(c);
        if (value().total() >= 21) finished = true;
    }

    public HandValue value()     { return HandValue.of(cards); }
    public boolean isBlackjack() { return !fromSplit && cards.size() == 2 && value().total() == 21; }
    public boolean canDouble()   { return !finished && cards.size() == 2; }
    public boolean canSplit()    { return !finished && cards.size() == 2 && cards.get(0).rank() == cards.get(1).rank(); }
    public boolean pairOfAces()  { return cards.size() == 2 && cards.get(0).rank() == Rank.ACE; }

    /** Moves the second card into a new hand with an equal bet; both hands are now split hands. */
    public Hand splitOff(String newId) {
        fromSplit = true;
        Hand other = new Hand(newId, playerId, bet, true);
        other.cards.add(cards.remove(1));
        return other;
    }

    public void doubleBet() { bet *= 2; }
    public void finish()    { finished = true; }
    // getters for id, playerId, bet, cards and finished elided
}

The variable rules are tiny interfaces. Each is a single question, so each implementation is one line, and a test can pin down exactly where two casinos differ.

public interface DealerStrategy { boolean shouldHit(HandValue v); }

public record StandOnSoft17() implements DealerStrategy {
    public boolean shouldHit(HandValue v) { return v.total() < 17; }
}

public record HitSoft17() implements DealerStrategy {
    public boolean shouldHit(HandValue v) { return v.total() < 17 || (v.total() == 17 && v.soft()); }
}

public interface PayoutPolicy { long blackjackWinnings(long bet); }

public record ThreeToTwo() implements PayoutPolicy {
    public long blackjackWinnings(long bet) { return bet * 3 / 2; }   // exact: bets are whole rupees
}

Settlement is a pure function: given a hand and the dealer's final hand, how much goes back to the wallet? The stake was taken at betting time, so a win returns the stake plus winnings, a push returns the stake, and a loss returns nothing. The order of the checks encodes the rules: a player who busts loses even if the dealer busts later.

public final class Settlement {
    private final PayoutPolicy payout;

    public Settlement(PayoutPolicy payout) { this.payout = payout; }

    public long creditFor(Hand h, Hand dealer) {
        long bet = h.bet();
        HandValue p = h.value(), d = dealer.value();
        if (p.bust()) return 0;
        if (h.isBlackjack()) return dealer.isBlackjack() ? bet : bet + payout.blackjackWinnings(bet);
        if (dealer.isBlackjack()) return 0;
        if (d.bust() || p.total() > d.total()) return 2 * bet;
        return p.total() == d.total() ? bet : 0;
    }
}

The Round drives the phases. Every public method starts with a phase guard, and every wallet call carries a reference unique to the round, hand and purpose, so a retried call cannot move money twice.

public final class Round {
    public enum Phase { BETTING, PLAYER_TURNS, DEALER_TURN, SETTLED }
    public enum Action { HIT, STAND, DOUBLE, SPLIT }

    private final String roundId;
    private final CardSource shoe;
    private final DealerStrategy dealerRule;
    private final Settlement settlement;
    private final Wallet wallet;
    private final List<Hand> hands = new ArrayList<>();      // play order; splits insert after the current hand
    private final Hand dealer = new Hand("dealer", "house", 0, false);
    private Phase phase = Phase.BETTING;
    private int turn;
    private int nextHandNo;

    // constructor elided

    public void placeBet(String playerId, long paise) {
        require(Phase.BETTING);
        if (paise <= 0 || paise % 100 != 0) throw new IllegalArgumentException("bets are whole rupees");
        Hand h = new Hand(roundId + "-" + nextHandNo++, playerId, paise, false);
        wallet.debit(ref(h, "bet"), playerId, paise);         // throws if funds are short; no hand is added
        hands.add(h);
    }

    public void deal() {
        require(Phase.BETTING);
        if (hands.isEmpty()) throw new IllegalStateException("no bets placed");
        for (int pass = 0; pass < 2; pass++) {
            for (Hand h : hands) h.add(shoe.draw());
            dealer.add(shoe.draw());                           // second dealer card is the hole card
        }
        if (dealer.isBlackjack()) { settle(); return; }        // the peek
        phase = Phase.PLAYER_TURNS;
        advance();
    }

    public void act(String playerId, Action action) {
        require(Phase.PLAYER_TURNS);
        Hand h = hands.get(turn);
        if (!h.playerId().equals(playerId)) throw new IllegalStateException("not your turn");
        switch (action) {
            case HIT -> h.add(shoe.draw());
            case STAND -> h.finish();
            case DOUBLE -> {
                if (!h.canDouble()) throw new IllegalStateException("cannot double");
                wallet.debit(ref(h, "double"), playerId, h.bet());
                h.doubleBet();
                h.add(shoe.draw());
                h.finish();
            }
            case SPLIT -> {
                if (!h.canSplit()) throw new IllegalStateException("cannot split");
                String newId = roundId + "-" + nextHandNo++;
                wallet.debit(roundId + ":" + newId + ":bet", playerId, h.bet());   // a failed debit changes nothing
                boolean aces = h.pairOfAces();
                Hand second = h.splitOff(newId);
                hands.add(turn + 1, second);
                h.add(shoe.draw());
                second.add(shoe.draw());
                if (aces) { h.finish(); second.finish(); }      // split aces get one card each
            }
        }
        advance();
    }

    private void advance() {
        while (turn < hands.size() && hands.get(turn).isFinished()) turn++;
        if (turn == hands.size()) playDealer();
    }

    private void playDealer() {
        phase = Phase.DEALER_TURN;
        boolean anyLive = hands.stream().anyMatch(h -> !h.value().bust() && !h.isBlackjack());
        if (anyLive) {
            while (dealerRule.shouldHit(dealer.value())) dealer.add(shoe.draw());
        }
        settle();
    }

    private void settle() {
        for (Hand h : hands) {
            long credit = settlement.creditFor(h, dealer);
            if (credit > 0) wallet.credit(ref(h, "settle"), h.playerId(), credit);
        }
        phase = Phase.SETTLED;
    }

    private void require(Phase expected) {
        if (phase != expected) throw new IllegalStateException("expected " + expected + " but round is " + phase);
    }

    private String ref(Hand h, String purpose) { return roundId + ":" + h.id() + ":" + purpose; }
}

The Shoe builds six decks and shuffles them with an injected java.util.Random. In production that is a SecureRandom (regulated gaming requires approved random number generators). In tests it is a seeded Random, or the shoe is replaced by a StackedShoe that deals a fixed list. pastCutCard() becomes true once 75% of 312 cards (234) have been dealt, and the table reshuffles before the next round. That leaves 78 cards, far more than five seats can use in one round.

Concurrency, edge cases and testing

Interviewer: This is an online table. Money is involved and players are on flaky phones. What can go wrong?

You: The same things as at the ATM, plus timing.

• Ordering. Each table is one actor: a single thread (or a serial queue) processes that table's commands in arrival order. Round itself is not thread-safe, and it doesn't need to be. Tables share nothing, so thousands run in parallel.
• Duplicate commands. A phone retries "double" after a timeout. The phase and turn guards reject an action that no longer fits. Even if a duplicate slipped through, the wallet reference round:hand:double is idempotent, so the money moves once (R3).
• Slow or absent players. Each turn has a timer; on expiry the server acts as if the player stood. A disconnected player's hand is never left blocking the table.
• Money held for the round. Debiting at bet time means the wallet's own atomic check stops a player betting the same balance at two tables. Settlement only ever credits.
• Crash mid-round. The round's state, plus the log of cards dealt and actions taken, is persisted after each command. On restart it is replayed, or the round is voided and every stake refunded under fresh idempotent references. Which one is chosen is a business rule, but both keep the books balanced.

Edge cases:

Testing uses a StackedShoe. Cards come out in deal order: player, dealer, player, dealer, then draws. Here is the dealer rule difference, proved with one stack:

@Test
void soft17RuleChangesTheOutcome() {
    // player 10, dealer A, player 8, dealer 6 (soft 17), next card 4
    List<Card> stack = cards("10S", "AH", "8D", "6C", "4S");

    Round stand = round(new StackedShoe(stack), new StandOnSoft17());
    stand.placeBet("asha", 100_000);
    stand.deal();
    stand.act("asha", Round.Action.STAND);
    assertEquals(200_000, wallet.creditedTo("asha"));        // 18 beats the dealer's soft 17

    wallet.reset();
    Round hit = round(new StackedShoe(stack), new HitSoft17());
    hit.placeBet("asha", 100_000);
    hit.deal();
    hit.act("asha", Round.Action.STAND);
    assertEquals(0, wallet.creditedTo("asha"));              // dealer draws the 4: soft 21 beats 18
}

Beyond scenarios, HandValue.of gets an exhaustive test over all two- and three-card combinations against a slow reference that tries every ace as 1 or 11. The most valuable test is a conservation run. Simulate a million seeded rounds with random legal actions, recording every wallet movement in an in-memory ledger. At the end, total debits minus total credits must equal the house result exactly, to the paisa. Any rounding bug, missed refund or double credit breaks the equation. This is reconciliation (R6) in miniature.

Extensions the interviewer will ask for

Interviewer: Add insurance.

You: When the dealer's up card is an ace, a new step runs before the peek: each player may place an insurance side bet of up to half their stake, which pays 2:1 if the dealer has blackjack. That is one new phase, INSURANCE, between dealing and player turns; a debit with reference hand:insurance; and one more line in settlement. Existing actions don't change.

Interviewer: This table pays 6:5 on blackjack.

You: new SixToFive() with bet * 6 / 5, injected through the table's configuration. The whole-rupee rule still guarantees an exact integer. No other class changes.

Interviewer: Use a continuous shuffling machine instead of a shoe.

You: Another CardSource. Used cards go back into the machine after each round, and pastCutCard() is always false. The round never knows the difference.

Interviewer: Add surrender.

You: A new Action.SURRENDER, allowed only on the first two cards: the hand finishes and settlement returns half the stake. The sealed set of actions makes the compiler point at the switch that must handle it.

Quick reference

The 60-second version

Blackjack combines the earlier lessons. The key modelling insight is that a hand's value is a pair, the best total and whether an ace is still counting 11, computed in one place by counting aces as 1 and adding 10 when it fits. Soft 17, bust and blackjack all read from that pair. A Round moves through enum phases (betting, player turns, dealer, settled) with a guard on every action. Splits insert a new hand into the play order, and split 21s are not blackjacks. The dealer's soft-17 behaviour, the blackjack payout and the card source are strategies, because casinos vary exactly those. Money follows the ATM's rules: the stake is debited at bet time, payouts are credited at settlement by a pure Settlement function, and every wallet call carries an idempotent reference per round, hand and purpose. Each table is a single actor, stacked shoes make tests exact, and a million-round conservation test proves that not a single paisa is created or lost.

Walkthrough 6 — Splitwise: sharing expenses without losing a paisa

Building on the games: the games were about rules — whose turn it is, which move is legal, when the game ends. From here the classes model money and records that must stay consistent. A wrong move in chess is rejected and forgotten; a wrong number in a ledger is remembered forever and someone pays for it. So the design questions change: where does each paisa go, what can never be edited, and what must add up to zero every single time.

Scope and requirements

Interviewer: Design the classes for an expense-sharing app like Splitwise. Friends add expenses, the app tells them who owes whom.

You: The heart of it is a ledger: every expense moves money between people on paper, and the balances must always add up. Before drawing classes, some questions:

Interviewer: All four split types. One payer per expense is fine to start. Groups, and treat one-to-one as a group of two. Yes, show simplified settlements. Rupees only for now. Expenses can be edited and deleted, and people want to see the history.

You: Requirements, then.

Functional:

• Create a group and add members.
• Add an expense: who paid, how much, and how it is split — equal, exact, percentage or shares.
• See each member's net balance in the group: positive means others owe you, negative means you owe.
• See a simplified settle-up plan: the fewest practical payments that clear every balance.
• Record a settlement ("Riya paid Arjun ₹500").
• Edit or delete an expense, with history kept.

Constraints:

• Money is an integer number of paise. No double, ever.
• Every expense must split to exactly its total — not one paisa more or less.
• The sum of all balances in a group is always zero. This is the invariant everything else protects.
• Two members adding expenses at the same moment must not lose either one.

Every posting to the ledger must sum to zero, so the group's balances always sum to zero. If that holds, no rounding, edit or race can create or destroy money.

Entities and responsibilities

Interviewer: What are your classes?

You: I read the requirements for nouns and verbs. The nouns — group, member, expense, split, balance, settlement — become candidate classes. The verbs tell me who owns behaviour: split an amount belongs to the split rule, post to a ledger belongs to the ledger, simplify debts is an algorithm with no state of its own, so it becomes a small service. "Balance" is a noun I deliberately do not store as an editable field: it is derived from the ledger.

Class diagram

classDiagram
  class Expense {
    +ExpenseId id
    +UserId paidBy
    +long totalPaise
    +Split split
  }
  class Split {
    <<sealed interface>>
    +allocate(long totalPaise) Map
  }
  class GroupLedger {
    +post(String sourceId, Map deltas)
    +balances() Map
  }
  Group "1" *-- "1" GroupLedger
  Group "1" o-- "many" Expense
  Expense --> Split
  Split <|.. Equal
  Split <|.. Exact
  Split <|.. Percent
  Split <|.. Shares
  GroupLedger "1" *-- "many" LedgerEntry
  ExpenseService --> GroupLedger
  ExpenseService --> Split
  DebtSimplifier ..> GroupLedger : reads balances

The important relationships: an Expense has a Split, and the split is chosen by the caller, not by if statements inside the service. The GroupLedger owns its entries — nothing else may append to it, so it is the one place that checks the zero-sum rule. DebtSimplifier only depends on balances; it never writes, which makes it trivial to test and safe to call as often as the screen refreshes.

Key flows

Interviewer: Walk me through adding an expense.

You: This is the central flow; everything else is a variation of it.

sequenceDiagram
  participant App
  participant ES as ExpenseService
  participant S as Split
  participant L as GroupLedger
  App->>ES: addExpense paidBy Arjun total 100000 Equal over 3
  ES->>ES: check payer and participants are members
  ES->>S: allocate 100000
  S-->>ES: Arjun 33334, Riya 33333, Kabir 33333
  ES->>ES: build deltas, payer plus total, each minus share
  ES->>L: post expense id, deltas
  L->>L: check deltas sum to zero
  L-->>ES: ok, balances updated
  ES-->>App: expense saved

1. The app sends who paid, the total in paise and a Split object — here Equal over three people for ₹1,000 (100,000 paise).
2. The service checks that everyone named is a group member.
3. The split allocates the total. 100,000 does not divide by three, so one person carries the extra paisa: 33,334 + 33,333 + 33,333 = 100,000.
4. The service builds the posting: the payer is credited the full total, and everyone (payer included) is debited their share. Arjun nets +100,000 − 33,334 = +66,666; Riya and Kabir −33,333 each. Keeping "paid" and "owes" separate means the same code handles a payer who is not in the split, like a parent paying for the children's dinner.
5. The ledger refuses any posting that does not sum to zero, appends the entries, and updates the running balances.

What's being probed: whether you treat balances as a derived view over an append-only ledger, rather than numbers you edit.

Concept — double-entry bookkeeping. Accountants never change a number in place; they write a new entry, and every entry has equal and opposite sides. If the sides always cancel, the books always balance, and history is never lost. A shared-expense app is a tiny double-entry ledger: each expense is one balanced posting, and each person's balance is the sum of their lines. Edits are a reversing posting plus a new one. R6 and R7 rely on the same property when reconciling payments.

Takeaway: Store immutable, zero-sum postings; compute balances from them; never edit a balance directly.

Patterns used, and why

The core code

Interviewer: Show me the heart of it.

You: Value types first. Ids are records, so a group id cannot be passed where a user id belongs.

public record UserId(String value) implements Comparable<UserId> {
    public int compareTo(UserId o) { return value.compareTo(o.value); }
}
public record ExpenseId(String value) {}
public record Expense(ExpenseId id, int version, UserId paidBy, long totalPaise, Split split) {}
public record Transfer(UserId from, UserId to, long paise) {}
public class InvalidSplitException extends RuntimeException {
    public InvalidSplitException(String m) { super(m); }
}

The allocator is where money is got right. It divides a total by integer weights using only integer arithmetic, then hands the leftover paise — always fewer than the number of people — to those with the largest remainders, ties broken by user id so the result is deterministic. This is the largest remainder method.

final class Allocator {
    static Map<UserId, Long> byWeights(long total, Map<UserId, Long> weights) {
        long sumW = weights.values().stream().mapToLong(Long::longValue).sum();
        if (total <= 0 || sumW <= 0) throw new InvalidSplitException("total and weights must be positive");
        record Rem(UserId user, long remainder) {}
        Map<UserId, Long> out = new TreeMap<>();
        List<Rem> rems = new ArrayList<>();
        long allocated = 0;
        for (var e : weights.entrySet()) {
            long numerator = Math.multiplyExact(total, e.getValue());
            out.put(e.getKey(), numerator / sumW);                 // floor
            allocated += numerator / sumW;
            rems.add(new Rem(e.getKey(), numerator % sumW));
        }
        rems.sort(Comparator.comparingLong(Rem::remainder).reversed().thenComparing(Rem::user));
        for (int i = 0; i < total - allocated; i++) {              // leftover < number of people
            out.merge(rems.get(i).user(), 1L, Long::sum);
        }
        return out;
    }
}

The four strategies. Percent uses basis points (1% = 100 bp), so 33.33% is the integer 3,333. Equal and shares are just weights; exact only validates.

public sealed interface Split permits Split.Equal, Split.Exact, Split.Percent, Split.Shares {
    Map<UserId, Long> allocate(long totalPaise);

    record Equal(List<UserId> users) implements Split {
        public Map<UserId, Long> allocate(long total) {
            Map<UserId, Long> w = new TreeMap<>();
            users.forEach(u -> w.put(u, 1L));
            return Allocator.byWeights(total, w);
        }
    }
    record Exact(Map<UserId, Long> amounts) implements Split {
        public Map<UserId, Long> allocate(long total) {
            long sum = amounts.values().stream().mapToLong(Long::longValue).sum();
            if (sum != total) throw new InvalidSplitException("adds to " + sum + ", expected " + total);
            return new TreeMap<>(amounts);
        }
    }
    record Percent(Map<UserId, Long> basisPoints) implements Split {
        public Map<UserId, Long> allocate(long total) {
            long sum = basisPoints.values().stream().mapToLong(Long::longValue).sum();
            if (sum != 10_000) throw new InvalidSplitException("percentages must add to 100");
            return Allocator.byWeights(total, basisPoints);
        }
    }
    record Shares(Map<UserId, Long> shares) implements Split {
        public Map<UserId, Long> allocate(long total) { return Allocator.byWeights(total, shares); }
    }
}

The ledger is the only class allowed to change balances, so it is the only place the zero-sum check lives. A set of posted source ids makes a replayed posting a no-op.

public record LedgerEntry(String sourceId, UserId user, long deltaPaise, Instant at) {}

public final class GroupLedger {
    private final List<LedgerEntry> entries = new ArrayList<>();
    private final Map<UserId, Long> net = new HashMap<>();
    private final Set<String> posted = new HashSet<>();

    public synchronized void post(String sourceId, Map<UserId, Long> deltas, Instant at) {
        long sum = deltas.values().stream().mapToLong(Long::longValue).sum();
        if (sum != 0) throw new IllegalStateException("unbalanced posting " + sourceId);
        if (!posted.add(sourceId)) return;                         // idempotent replay
        deltas.forEach((u, d) -> {
            entries.add(new LedgerEntry(sourceId, u, d, at));
            net.merge(u, d, Long::sum);
        });
    }

    public synchronized Map<UserId, Long> balances() { return Map.copyOf(net); }
}

The service builds postings. An edit is a reversal of the old version plus a posting of the new one, each with its own source id, so history shows exactly what changed.

public final class ExpenseService {
    private final GroupLedger ledger;
    private final Clock clock;
    // constructor, membership checks and persistence elided

    public void addExpense(Expense e) {
        ledger.post("exp:" + e.id().value() + ":v" + e.version(), deltasFor(e), clock.instant());
    }

    public void editExpense(Expense old, Expense updated) {           // updated.version = old + 1
        Map<UserId, Long> reverse = new HashMap<>();
        deltasFor(old).forEach((u, d) -> reverse.put(u, -d));
        ledger.post("rev:" + old.id().value() + ":v" + old.version(), reverse, clock.instant());
        addExpense(updated);
    }

    public void settle(String settlementId, UserId from, UserId to, long paise) {
        ledger.post("set:" + settlementId, Map.of(from, paise, to, -paise), clock.instant());
    }

    private static Map<UserId, Long> deltasFor(Expense e) {
        Map<UserId, Long> d = new HashMap<>();
        d.merge(e.paidBy(), e.totalPaise(), Long::sum);
        e.split().allocate(e.totalPaise()).forEach((u, share) -> d.merge(u, -share, Long::sum));
        return d;
    }
}

Finally, debt simplification. Only net balances matter — who paid for which bill is irrelevant to settling up. Put creditors and debtors in two max-heaps, match the largest of each, and transfer the smaller amount. Each step clears at least one person, so n people need at most n − 1 payments.

public final class DebtSimplifier {
    public List<Transfer> simplify(Map<UserId, Long> net) {
        record Bal(UserId user, long amount) {}
        Comparator<Bal> largestFirst = Comparator.comparingLong(Bal::amount).reversed()
                                                 .thenComparing(Bal::user);
        PriorityQueue<Bal> creditors = new PriorityQueue<>(largestFirst);
        PriorityQueue<Bal> debtors = new PriorityQueue<>(largestFirst);   // amounts kept positive
        net.forEach((u, v) -> {
            if (v > 0) creditors.add(new Bal(u, v));
            else if (v < 0) debtors.add(new Bal(u, -v));
        });
        List<Transfer> plan = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            Bal c = creditors.poll(), d = debtors.poll();
            long x = Math.min(c.amount(), d.amount());
            plan.add(new Transfer(d.user(), c.user(), x));
            if (c.amount() > x) creditors.add(new Bal(c.user(), c.amount() - x));
            if (d.amount() > x) debtors.add(new Bal(d.user(), d.amount() - x));
        }
        return plan;
    }
}

A Goa trip: Arjun paid ₹9,000 for the villa, Riya ₹3,000 for food, Kabir nothing, split equally.

Each owes 12,000 / 3 = 4,000
Arjun +5,000   Riya −1,000   Kabir −4,000     sum = 0
Largest creditor Arjun 5,000, largest debtor Kabir 4,000 → Kabir pays Arjun 4,000
Arjun +1,000, Riya −1,000                                → Riya pays Arjun 1,000
2 payments for 3 people (n − 1)

Interviewer: Is that always the true minimum number of payments?

You: No. The exact minimum means finding as many subgroups as possible whose balances cancel among themselves, and that search grows exponentially with group size. Greedy never needs more than n − 1 payments and runs in O(n log n); for a group of friends it is the right trade.

Concurrency, edge cases and testing

Interviewer: Two people add expenses to the same group at the same moment.

You: In memory, GroupLedger.post is synchronized, so postings to one group are applied one at a time, and different groups never block each other. In a database, each posting is one transaction that inserts all its entry rows together. Balances are either computed with SUM(delta) GROUP BY user or kept in a balance table updated in the same transaction:

BEGIN;
INSERT INTO ledger_entry (group_id, source_id, user_id, delta_paise) VALUES
  (:g, 'exp:e91:v1', 'arjun',  66666),
  (:g, 'exp:e91:v1', 'riya',  -33333),
  (:g, 'exp:e91:v1', 'kabir', -33333);
UPDATE balance SET net_paise = net_paise + :delta WHERE group_id = :g AND user_id = :u;  -- once per user
COMMIT;
-- UNIQUE (group_id, source_id, user_id) makes a retried posting fail instead of doubling

The UPDATE ... SET net = net + delta is an atomic increment, so two concurrent postings both land — neither overwrites the other, which is what would happen with "read balance, add, write back". The unique key on source_id makes a double-tapped "Save" or a network retry harmless (R3).

Never compute shares with double: 0.1 + 0.2 is not 0.3, and the error ends up in someone's balance.

What else can go wrong, and the answer:

Tests I would write first are property tests: for random totals and weights, shares always sum to the total and each is within one paisa of its exact value; after any random sequence of add, edit and settle, balances sum to zero; and posting the simplified transfers as settlements brings everyone to zero.

Extensions the interviewer will ask for

Interviewer: Now support several currencies.

You: Balances become keyed by (user, currency), and an expense carries its currency. The ledger checks the zero-sum rule per currency within a posting. Debt simplification runs once per currency. Converting everything to rupees is an optional view on top, using a stated rate and date — never stored as if it were the truth.

Interviewer: Several people paid for one expense.

You: paidBy becomes a Map<UserId, Long> of contributions that must sum to the total. deltasFor credits each payer their contribution. The split strategies and the ledger do not change at all.

Interviewer: A new split type: "equal, but Kabir pays ₹200 extra for his drinks".

You: A fifth record, Adjusted(Map<UserId, Long> extras, List<UserId> users), that subtracts the extras from the total, splits the rest equally with the allocator, and adds the extras back. Add it to the permits list; the compiler then flags any switch that forgot it. Nothing else changes — that is the Strategy pattern earning its place.

Quick reference

The 60-second version

An expense app is a small double-entry ledger. Each expense picks a split strategy — equal, exact, percentage in basis points, or shares — and a single allocator divides the total in integer paise, giving leftover paise to the largest remainders so the shares always add up exactly. The service turns the split into one posting: the payer is credited the total, each participant debited their share, and the ledger refuses any posting that does not sum to zero. Balances are derived from these immutable entries; edits are a reversal plus a new posting, and a unique source id makes retries harmless. Concurrency is one transaction per posting with atomic increments. To settle up, a greedy matcher pairs the biggest creditor with the biggest debtor until everyone is at zero, needing at most n − 1 payments.

Walkthrough 7 — Meeting scheduler: free slots, rooms and time zones

Building on Splitwise: Splitwise protected one invariant — postings sum to zero. A scheduler protects a different kind: two things must never occupy the same time. The records are now intervals — a start and an end — and the hard parts are finding gaps between many people's intervals, refusing an overlapping room booking even when two requests arrive together, and remembering that "10 a.m." means different instants in Bengaluru and London.

Scope and requirements

Interviewer: Design the classes for a meeting scheduler inside a company — like the scheduling part of Outlook or Google Calendar.

You: Two problems sit at the centre: finding a time that suits everyone, and booking a room without ever double-booking it. Some questions first:

Interviewer: Suggest slots; the organiser picks one. Offices in Bengaluru, London and New York. Rooms have capacity and some have video kits. Daily and weekly recurrence, and people do move single occurrences. Several app servers behind a load balancer. Email invites and a reminder ten minutes before.

You: Requirements, then.

Functional:

• Create a meeting: organiser, attendees, duration, optional room requirements.
• Suggest slots within a search window where every required attendee is free and inside their working hours.
• Book a room that fits, with no overlap with any other booking of that room.
• Attendees accept or decline; the organiser sees responses.
• Recurring meetings, with single occurrences moved or cancelled.
• Notify on create, update, cancel and response; remind before start.

Constraints:

• A room is never double-booked, even when two organisers click "Book" in the same millisecond on different servers.
• Times are stored as instants (UTC); each user and office has a time zone, and daylight saving time (DST) shifts must be right.
• Intervals are half-open: [10:00, 11:00) includes 10:00 but not 11:00, so back-to-back meetings do not clash.

Store every time as an instant, but define working hours and recurrences in the owner's own zone, and convert at the edge.

Entities and responsibilities

Interviewer: Classes?

You: Nouns from the requirements: meeting, attendee, room, calendar, slot, invitation, recurrence, notification. Verbs: suggest slots (an algorithm over calendars — a service), book a room (owned by whatever guards that room's timeline), respond to an invitation (the invitation's own state), notify (reactions to events). "Slot" is just an interval, so it becomes one value type, TimeRange, used everywhere.

Class diagram

classDiagram
  class TimeRange {
    +Instant start
    +Instant end
    +overlaps(TimeRange) boolean
  }
  class Meeting {
    +MeetingId id
    +UserId organiser
    +TimeRange when
    +Recurrence recurrence
  }
  class RoomCalendar {
    +tryBook(Booking) boolean
  }
  class MeetingListener {
    <<interface>>
  }
  Meeting "1" *-- "many" Invitation
  Meeting --> TimeRange
  Meeting --> Recurrence
  Meeting --> Room : optional
  Room "1" *-- "1" RoomCalendar
  User "1" --> "many" Invitation
  SchedulerService --> CalendarService
  SchedulerService --> FreeSlotFinder
  SchedulerService --> RoomCalendar
  SchedulerService --> MeetingEvents
  MeetingEvents o-- MeetingListener
  MeetingListener <|.. EmailNotifier
  MeetingListener <|.. ReminderScheduler

The key relationships: each Room owns exactly one RoomCalendar, and only that calendar can add a booking — so the overlap check has one home. SchedulerService depends on the finder and calendars but holds no state of its own. MeetingEvents aggregates listeners it does not know the details of, so adding SMS later touches no scheduling code.

Key flows

Interviewer: Walk me through scheduling a meeting with a room.

sequenceDiagram
  participant O as Organiser
  participant S as SchedulerService
  participant C as CalendarService
  participant F as FreeSlotFinder
  participant R as RoomCalendar
  participant E as MeetingEvents
  O->>S: suggest attendees, 30 min, next 3 days
  S->>C: busy intervals for each attendee
  C-->>S: meetings plus time outside working hours
  S->>F: find window, 30 min, busy lists
  F-->>S: free slots
  S-->>O: slots, each with rooms that fit
  O->>S: book slot Tue 14.30 UTC, room Kaveri
  S->>R: tryBook Kaveri, Tue 14.30 to 15.00
  R-->>S: true
  S->>E: publish MeetingCreated
  E-->>O: invites and reminder scheduled

1. The organiser asks for a 30-minute slot over the next three days for people in Bengaluru and London.
2. CalendarService returns each attendee's busy intervals: existing meetings, with recurrences expanded, plus everything outside their working hours, converted from their own zone to instants. Treating "not working" as "busy" means the finder needs no special case for zones.
3. FreeSlotFinder merges all busy intervals into one sorted, non-overlapping list and returns the gaps of at least 30 minutes.
4. The organiser picks one. RoomCalendar.tryBook checks and inserts in one atomic step. If another organiser got the room first, it returns false and the organiser is offered the next room.
5. The meeting is saved and MeetingCreated is published; email and reminder listeners react.

Interviewer: Why merge the intervals first instead of checking each candidate slot against everyone?

You: Checking every slot against every meeting is slots × meetings. Merging sorts once — O(m log m) for m busy intervals — and then one pass finds every gap. It also makes the answer obvious to read: after merging, "free" is literally the space between consecutive blocks.

Patterns used, and why

The core code

Interviewer: Show me the free-slot search and the room guard.

You: Everything rests on one value type with the half-open overlap rule.

public record TimeRange(Instant start, Instant end) {
    public TimeRange {
        if (!start.isBefore(end)) throw new IllegalArgumentException("start must be before end");
    }
    /** Half-open: [10:00, 11:00) and [11:00, 12:00) do not overlap. */
    public boolean overlaps(TimeRange o) { return start.isBefore(o.end) && o.start.isBefore(end); }

    static Instant later(Instant a, Instant b) { return a.isAfter(b) ? a : b; }
}

Merging: sort by start, then fold each interval into the last merged block if it starts before (or exactly when) that block ends.

public final class FreeSlotFinder {

    static List<TimeRange> merge(Collection<TimeRange> busy) {
        List<TimeRange> sorted = new ArrayList<>(busy);
        sorted.sort(Comparator.comparing(TimeRange::start));
        Deque<TimeRange> merged = new ArrayDeque<>();
        for (TimeRange r : sorted) {
            TimeRange last = merged.peekLast();
            if (last != null && !r.start().isAfter(last.end())) {
                merged.pollLast();
                merged.addLast(new TimeRange(last.start(), TimeRange.later(last.end(), r.end())));
            } else {
                merged.addLast(r);
            }
        }
        return List.copyOf(merged);
    }

    public List<TimeRange> find(TimeRange window, Duration minLength, Collection<TimeRange> allBusy) {
        List<TimeRange> free = new ArrayList<>();
        Instant cursor = window.start();
        for (TimeRange b : merge(allBusy)) {
            if (!b.end().isAfter(window.start())) continue;          // ends before the window
            if (!b.start().isBefore(window.end())) break;            // starts after the window
            addIfLongEnough(free, cursor, b.start(), minLength);
            cursor = TimeRange.later(cursor, b.end());
        }
        addIfLongEnough(free, cursor, window.end(), minLength);
        return free;
    }

    private static void addIfLongEnough(List<TimeRange> out, Instant from, Instant to, Duration min) {
        if (Duration.between(from, to).compareTo(min) >= 0) out.add(new TimeRange(from, to));
    }
}

Working hours become busy intervals. ZonedDateTime.of(day, 09:00, zone) gives the right instant on each day, so a London attendee's 9 a.m. is 08:00 UTC in summer and 09:00 UTC in winter without any special code.

static List<TimeRange> outsideWorkingHours(TimeRange window, ZoneId zone, LocalTime from, LocalTime to) {
    List<TimeRange> busy = new ArrayList<>();
    LocalDate day = window.start().atZone(zone).toLocalDate().minusDays(1);
    LocalDate last = window.end().atZone(zone).toLocalDate().plusDays(1);
    Instant prevEnd = day.atStartOfDay(zone).toInstant();
    for (; !day.isAfter(last); day = day.plusDays(1)) {
        // weekends and holidays elided: skip the day and let prevEnd carry over
        Instant workStart = ZonedDateTime.of(day, from, zone).toInstant();
        if (prevEnd.isBefore(workStart)) busy.add(new TimeRange(prevEnd, workStart));
        prevEnd = ZonedDateTime.of(day, to, zone).toInstant();
    }
    return busy;
}

The room guard. Bookings of one room are kept in a TreeMap keyed by start. Because existing bookings never overlap each other, only two can clash with a new one: the latest that starts at or before it, and the earliest that starts at or after it. Both lookups are O(log n).

public record Booking(MeetingId meetingId, TimeRange range) {}

public final class RoomCalendar {
    private final NavigableMap<Instant, Booking> byStart = new TreeMap<>();

    public synchronized boolean tryBook(Booking b) { return tryBookAll(List.of(b)); }

    /** All or nothing — used for a recurring series. */
    public synchronized boolean tryBookAll(List<Booking> bookings) {
        for (Booking b : bookings) if (clashes(b.range())) return false;
        bookings.forEach(b -> byStart.put(b.range().start(), b));
        return true;
    }

    public synchronized void release(Booking b) { byStart.remove(b.range().start(), b); }

    private boolean clashes(TimeRange r) {
        var before = byStart.floorEntry(r.start());
        var after = byStart.ceilingEntry(r.start());
        return (before != null && before.getValue().range().overlaps(r))
            || (after != null && after.getValue().range().overlaps(r));
    }
}

Recurrence is stored as a rule in the organiser's zone and expanded only for the window asked about. Expanding with local date-times and converting each one keeps a weekly 10:00 London meeting at 10:00 London time across the DST change.

public enum Frequency {
    DAILY, WEEKLY;
    LocalDateTime next(LocalDateTime t, int n) { return this == DAILY ? t.plusDays(n) : t.plusWeeks(n); }
}

public record Recurrence(Frequency freq, int interval, LocalDateTime firstStart,
                         Duration length, ZoneId zone, LocalDate until) {
    public List<TimeRange> occurrencesIn(TimeRange window) {
        List<TimeRange> out = new ArrayList<>();
        for (LocalDateTime t = firstStart; !t.toLocalDate().isAfter(until); t = freq.next(t, interval)) {
            Instant s = t.atZone(zone).toInstant();
            if (!s.isBefore(window.end())) break;
            TimeRange occ = new TimeRange(s, s.plus(length));
            if (occ.overlaps(window)) out.add(occ);
        }
        return out;   // exceptions (moved or cancelled occurrences) applied by the caller, keyed by original start
    }
}

Notifications use Observer. Events are a sealed family; a failing listener is logged, never allowed to undo the booking.

public sealed interface MeetingEvent permits MeetingEvent.Created, MeetingEvent.Cancelled, MeetingEvent.Responded {
    MeetingId meetingId();
    record Created(MeetingId meetingId, Set<UserId> attendees, TimeRange when) implements MeetingEvent {}
    record Cancelled(MeetingId meetingId, Set<UserId> attendees) implements MeetingEvent {}
    record Responded(MeetingId meetingId, UserId who, boolean accepted) implements MeetingEvent {}
}

public interface MeetingListener { void on(MeetingEvent e); }

public final class MeetingEvents {
    private final List<MeetingListener> listeners = new CopyOnWriteArrayList<>();
    public void subscribe(MeetingListener l) { listeners.add(l); }
    public void publish(MeetingEvent e) {
        for (MeetingListener l : listeners) {
            try { l.on(e); } catch (RuntimeException ex) { /* log and carry on */ }
        }
    }
}

Concurrency, edge cases and testing

Interviewer: You said several app servers. Your synchronized method only protects one JVM.

You: Right — the in-memory guard is the design for one process, and it shows the logic clearly. With several servers, the database must refuse the overlap itself. Postgres can do it declaratively with an exclusion constraint: no two rows may have the same room and overlapping time ranges.

CREATE EXTENSION IF NOT EXISTS btree_gist;          -- lets a GiST index compare room_id with =
CREATE TABLE room_booking (
  room_id    bigint    NOT NULL,
  meeting_id bigint    NOT NULL,
  during     tstzrange NOT NULL,                    -- '[start, end)' half-open by default
  EXCLUDE USING gist (room_id WITH =, during WITH &&)
);
-- Two concurrent inserts for Kaveri, 14:30-15:00: one commits; the other fails
-- with an exclusion violation, which the service maps to "room just taken".

On a database without range constraints, the alternative is to lock the room's row first — SELECT ... FROM room WHERE id = ? FOR UPDATE — then check for overlaps and insert in the same transaction. The room row acts as a per-room mutex, so bookings for different rooms never wait for each other.

The overlap check and the insert must be one atomic step per room — in a lock, or in a constraint the database enforces.

What's being probed: whether you see the check-then-act race, and move the check to where it cannot be raced.

Concept — check-then-act. "Is the room free? Yes. Book it." is two steps, and another request can slip between them, so both see "free" and both book. The cure is to make check and act indivisible: hold a lock on something both requests must touch (the room row), or let the database reject the second write (a constraint). It is the same idea as BookMyShow's conditional update in R19; R8 covers why a lock outside the database needs fencing to be safe.

Takeaway: Never check availability and then book in separate steps; guard each room with one atomic operation.

Other things that go wrong:

Tests: free-slot search with overlapping, touching and nested intervals; a window fully covered; attendees in three zones on a DST-change week; and a concurrency test that fires a hundred threads booking the same room and slot and asserts exactly one succeeds.

Extensions the interviewer will ask for

Interviewer: Optional attendees.

You: Run the finder twice: once with required attendees only, then rank those slots by how many optional attendees are also free. The finder itself does not change.

Interviewer: Book a room automatically — the smallest that fits.

You: A RoomSelectionPolicy strategy filters rooms by capacity and features, sorts them, and the service tries tryBook on each in order until one returns true.

Interviewer: Move one occurrence of a weekly meeting.

You: Store an exception keyed by that occurrence's original start: either "cancelled" or "moved to this range". Expansion applies exceptions after generating occurrences. The room calendar releases the old booking and tries the new one; if that fails, the move is refused and the original stays.

Quick reference

The 60-second version

A meeting scheduler is built on one value type: a half-open interval of two instants with a single overlap rule. To suggest times, collect every attendee's busy intervals — existing meetings with recurrences expanded, plus everything outside their working hours converted from their own zone — merge them into sorted non-overlapping blocks, and return the gaps that are long enough. Each room owns a calendar that checks and inserts in one atomic step: a TreeMap with floor and ceiling lookups inside a lock for one process, and a Postgres exclusion constraint or a locked room row when there are many servers. Recurrences are stored as a rule in the organiser's zone with per-occurrence exceptions, so DST never shifts them. Notifications hang off an Observer, so email and reminders never touch scheduling logic.

Walkthrough 8 — Stack Overflow: votes, reputation and moderation

Building on the meeting scheduler: the scheduler stopped two bookings landing on the same interval. Stack Overflow has the same "only one" rule in a different shape — one vote per user per post — and adds a second record that depends on the first: reputation. Every vote changes someone's score, so the vote and the reputation must never drift apart, even when a user clicks twice, changes their mind, or the request is retried.

Scope and requirements

Interviewer: Design the classes for a Q&A site like Stack Overflow.

You: It looks like a content site, but the interesting part is that votes are money-like: they move reputation, and reputation unlocks powers. Questions first:

Interviewer: Take these rules as given, not the real site's: an upvote gives the author +5 on a question and +10 on an answer; a downvote gives the author −2, and downvoting an answer costs the voter −1. An accepted answer gives the answerer +15 and the asker +2. Everyone starts at 1 and the displayed reputation never goes below 1. Votes can be changed or retracted. No self-votes. One accepted answer, changeable. Search by tags and keywords. Commenting needs 50, downvoting 125, voting to close 3,000; five close votes close a question.

You: Requirements, then.

Functional:

• Post questions with tags; post answers; comment on either.
• Upvote, downvote, change or retract a vote on a question or answer.
• Accept one answer per question; change the accepted answer.
• Keep each user's reputation per the rules; gate actions by reputation.
• Search questions by tag and keyword.
• Flag posts; vote to close; close at five votes; moderators can delete and lock.

Constraints:

• One vote per (voter, post). Clicking upvote twice is the same as clicking once.
• Reputation must equal the sum of its events, so it can be audited and recomputed.
• A post's displayed score may lag a moment; the vote record itself must be exact.

A vote is a state per (voter, post), not an action; reputation changes by the difference between the old state and the new one.

Entities and responsibilities

Interviewer: Classes?

You: The nouns are user, question, answer, comment, tag, vote, reputation, flag, close vote. Questions and answers share most behaviour — author, body, score, votes — so they are two kinds of Post. Comments are deliberately not posts here: they carry no votes or reputation in our rules, and forcing them into the hierarchy would invite bugs. The verbs place behaviour: vote belongs to a VoteService that guards the one-vote rule; award reputation belongs to a rules object plus a ledger; search belongs to an index fed by events.

Class diagram

classDiagram
  class Post {
    <<sealed>>
    +PostId id
    +UserId author
    +long score
    +PostStatus status
  }
  class Question {
    +String title
    +Set tags
    +AnswerId accepted
  }
  class VoteService {
    +cast(UserId, PostId, VoteValue)
  }
  class ReputationLedger {
    +apply(ReputationEvent)
    +reputationOf(UserId) long
  }
  Post <|-- Question
  Post <|-- Answer
  Question "1" *-- "many" Answer
  Post "1" *-- "many" Comment
  Question "many" -- "many" Tag
  VoteService --> ReputationRules
  VoteService --> ReputationLedger
  VoteService --> PostEvents
  ModerationService --> Privilege
  PostEvents o-- SearchIndex : observer

The important relationships: VoteService is the only writer of votes, and the only caller that turns a vote change into reputation events, so the two cannot drift. ReputationRules is a pure function the service depends on, which is why changing the numbers never touches the voting logic. SearchIndex only observes post events; it is a read model that can be rebuilt from scratch.

Key flows

Interviewer: Walk me through a vote.

You: The vote is a small state machine with three states. Each arrow carries the reputation change for an answer.

stateDiagram-v2
  [*] --> None
  None --> Up : upvote, author +10
  None --> Down : downvote, author -2, voter -1
  Up --> None : retract, author -10
  Up --> Down : switch, author -12, voter -1
  Down --> None : retract, author +2, voter +1
  Down --> Up : switch, author +12, voter +1

1. The user clicks upvote. VoteService.cast(voter, post, UP) checks the voter is not the author and, for a downvote, that they hold the 125 privilege.
2. Atomically for that (voter, post) key, it reads the current state — NONE — and writes UP, bumping a version number.
3. It asks the rules for the points each state is worth: UP on an answer is worth 10 to the author, NONE is worth 0. The difference, +10, becomes a reputation event with an id built from the voter, post and version.
4. The ledger applies the event unless it has seen that id before. The post's score moves by the difference in vote weight: +1.
5. A VoteChanged event goes out; the search index and notification listeners update.

Interviewer: The user double-clicks upvote. Then their phone retries the request.

You: Nothing happens after the first. The second click asks to move from UP to UP: the difference is zero, so no event, no score change, no new version. The retry is the same. And if two different changes race — upvote then downvote — the atomic step on the key puts them in an order, and their differences add up: (UP − NONE) + (DOWN − UP) = DOWN − NONE. Whatever order they land in, the final reputation matches the final vote.

What's being probed: whether your vote is idempotent by design, not by luck.

Concept — store the state, derive the change. If you store "user clicked upvote" as an event and add 10 each time, every duplicate click or retry adds 10 more. If you store "this user's vote on this post is UP" and compute reputation as points(new) − points(old), repeating the request is harmless, because the difference from UP to UP is zero. It is the same idea as an idempotency key (R3), but built into the data shape: a unique key on (voter, post) makes a second vote impossible to store.

Takeaway: Key votes by (voter, post), compute deltas from old to new state, and give every reputation event a unique id.

Patterns used, and why

The core code

Interviewer: Show me the vote and reputation code.

You: Value types and the rules. A switch expression keeps the points table readable; the rules say what a state is worth, never what a click is worth.

public record UserId(String value) {}
public record PostId(String value) {}
public enum PostKind { QUESTION, ANSWER }
public enum PostStatus { OPEN, CLOSED, LOCKED, DELETED }
public record PostRef(PostId id, PostKind kind, UserId author, PostStatus status) {}

public enum VoteValue {
    NONE(0), UP(1), DOWN(-1);
    final int weight;
    VoteValue(int weight) { this.weight = weight; }
}

public final class ReputationRules {
    public static final int ACCEPTED_ANSWER = 15, ACCEPTER = 2, FLOOR = 1;

    public int authorPoints(PostKind kind, VoteValue v) {
        return switch (v) {
            case UP -> kind == PostKind.QUESTION ? 5 : 10;
            case DOWN -> -2;
            case NONE -> 0;
        };
    }
    public int voterPoints(PostKind kind, VoteValue v) {
        return v == VoteValue.DOWN && kind == PostKind.ANSWER ? -1 : 0;
    }
}

The ledger applies each event once. It stores the raw sum and clamps only when displaying, so reputation stays a pure sum of events that can be recomputed from history. That is a deliberate choice: clamping at write time would make the result depend on the order of events.

public record ReputationEvent(String eventId, UserId user, int delta, String reason) {}

public final class ReputationLedger {
    private final Set<String> applied = ConcurrentHashMap.newKeySet();
    private final ConcurrentHashMap<UserId, AtomicLong> raw = new ConcurrentHashMap<>();

    public void apply(ReputationEvent e) {
        if (!applied.add(e.eventId())) return;                    // seen before: ignore
        raw.computeIfAbsent(e.user(), u -> new AtomicLong(ReputationRules.FLOOR)).addAndGet(e.delta());
    }

    public long reputationOf(UserId u) {
        AtomicLong r = raw.get(u);
        return Math.max(ReputationRules.FLOOR, r == null ? ReputationRules.FLOOR : r.get());
    }
}

The vote service. ConcurrentHashMap.compute runs atomically per key, so for one (voter, post) the read of the old state and the write of the new one cannot interleave with another request. Different posts never block each other.

public final class VoteService {
    public record VoteKey(UserId voter, PostId post) {}
    private record VoteState(VoteValue value, long version) {}
    private record Transition(VoteValue from, VoteValue to, long version) {}

    private final ConcurrentHashMap<VoteKey, VoteState> votes = new ConcurrentHashMap<>();
    private final ConcurrentHashMap<PostId, AtomicLong> scores = new ConcurrentHashMap<>();
    private final PostRepository posts;
    private final PrivilegeChecker privileges;
    private final ReputationRules rules;
    private final ReputationLedger reputation;
    private final PostEvents events;
    // constructor elided; PostRepository, PostEvents and ActionRejected are plain collaborators

    public void cast(UserId voter, PostId postId, VoteValue desired) {
        PostRef post = posts.ref(postId);
        if (post.author().equals(voter)) throw new ActionRejected("cannot vote on your own post");
        if (post.status() == PostStatus.LOCKED || post.status() == PostStatus.DELETED) {
            throw new ActionRejected("post is locked or deleted");
        }
        if (desired == VoteValue.DOWN) privileges.require(voter, Privilege.DOWNVOTE);

        Transition t = transition(new VoteKey(voter, postId), desired);
        if (t.from() == t.to()) return;                           // duplicate click or retry

        String src = "vote:" + voter.value() + ":" + postId.value() + ":v" + t.version();
        int authorDelta = rules.authorPoints(post.kind(), t.to()) - rules.authorPoints(post.kind(), t.from());
        int voterDelta = rules.voterPoints(post.kind(), t.to()) - rules.voterPoints(post.kind(), t.from());
        if (authorDelta != 0) reputation.apply(new ReputationEvent(src + ":author", post.author(), authorDelta, "vote"));
        if (voterDelta != 0) reputation.apply(new ReputationEvent(src + ":voter", voter, voterDelta, "downvote cost"));

        scores.computeIfAbsent(postId, id -> new AtomicLong()).addAndGet(t.to().weight - t.from().weight);
        events.publish(new PostEvent.VoteChanged(postId, t.to()));
    }

    private Transition transition(VoteKey key, VoteValue desired) {
        Transition[] out = new Transition[1];
        votes.compute(key, (k, cur) -> {
            VoteState old = cur == null ? new VoteState(VoteValue.NONE, 0) : cur;
            if (old.value() == desired) { out[0] = new Transition(desired, desired, old.version()); return old; }
            VoteState next = new VoteState(desired, old.version() + 1);
            out[0] = new Transition(old.value(), desired, next.version());
            return next;
        });
        return out[0];
    }
}

Privileges are data, not scattered if statements. Moderation checks the same table.

public enum Privilege {
    COMMENT(50), DOWNVOTE(125), CLOSE_VOTE(3_000);
    final long required;
    Privilege(long required) { this.required = required; }
}

public final class PrivilegeChecker {
    private final ReputationLedger reputation;
    public PrivilegeChecker(ReputationLedger reputation) { this.reputation = reputation; }
    public void require(UserId u, Privilege p) {
        if (reputation.reputationOf(u) < p.required) throw new ActionRejected("needs " + p.required + " reputation");
    }
}

Accepting an answer follows the same shape: the question holds its accepted answer id under a lock on the question; changing it posts −15 to the old answerer and +15 to the new one, each event keyed by the question id and an acceptance version, and the asker's +2 is awarded only on the first acceptance.

Concurrency, edge cases and testing

Interviewer: You have many app servers and a database. How does the one-vote rule hold?

You: A primary key on (voter_id, post_id) makes a second row impossible. The tricky part is that you cannot lock a row that does not exist yet, so I insert a NONE row if missing, then lock it, then change it — all in one transaction with the reputation events and the score.

BEGIN;
INSERT INTO vote (voter_id, post_id, value, version) VALUES (:v, :p, 'NONE', 0)
  ON CONFLICT (voter_id, post_id) DO NOTHING;
SELECT value, version FROM vote WHERE voter_id = :v AND post_id = :p FOR UPDATE;
-- in Java: if value = desired, COMMIT and stop; otherwise compute the deltas
UPDATE vote SET value = :desired, version = version + 1 WHERE voter_id = :v AND post_id = :p;
INSERT INTO reputation_event (event_id, user_id, delta) VALUES (:eventId, :author, :delta)
  ON CONFLICT (event_id) DO NOTHING;
UPDATE post SET score = score + :scoreDelta WHERE id = :p;
COMMIT;

The unique event_id makes a replayed transaction harmless, and user reputation is either SUM(delta) or a counter updated in the same transaction.

A viral post turns UPDATE post SET score = ... into a queue of thousands of transactions on one row.

For hot posts I would move the score off the critical path: the vote row and reputation event commit together, and the score is a read model updated from those events in batches, a second or two behind. The vote stays exact; only the displayed number lags — which the requirements allow.

Tests: for any random sequence of vote clicks by many users, final reputation equals the reputation computed from the final vote states alone; duplicate and replayed requests change nothing; a hundred threads voting on one post produce exactly one vote per user.

Extensions the interviewer will ask for

Interviewer: Cap reputation from votes at 200 per user per day.

You: The cap makes reputation depend on order and date, so it belongs in the ledger, not the vote service. The ledger tracks each user's vote-earned total per day; an event beyond the cap is recorded with its full delta but an applied amount of zero. History stays complete, and a recompute gives the same answer because events have timestamps.

Interviewer: Detect serial voting — one user upvoting everything another user posts.

You: A fraud job reads vote events, finds suspicious pairs, and asks VoteService to reset those votes to NONE. The usual deltas reverse the reputation. No special undo path.

Interviewer: Badges, like "first accepted answer".

You: A BadgeService subscribes to post and reputation events (Observer). The vote and accept code are unchanged.

Interviewer: Edit history on posts.

You: A post holds a list of immutable Revision records; the current body is the latest. Moderators roll back by adding a revision that copies an older one — the same append-only habit as the ledger.

Quick reference

The 60-second version

The design treats a vote as a state, not an action: each (voter, post) pair is NONE, UP or DOWN, guarded by a unique key and changed atomically. Reputation is the difference between what the rules say the new state and the old state are worth, so a double click or a retry produces a zero change, and racing changes add up to the right total whatever their order. Every reputation change is an event with a unique id in a ledger, which makes it auditable, recomputable and safe to replay; the displayed floor of 1 is applied on read so the sum stays order-independent. In the database, insert a NONE row if missing, lock it, update it and write the events in one transaction. Rules, privileges, search and badges sit beside this core as a rules object, an enum of thresholds and Observer listeners, so new requirements land without touching the vote path.

Walkthrough 9 — Car rental: date ranges, pricing and the return desk

Building on Stack Overflow: the Q&A site kept two records in step — a vote and the reputation it moves. A car rental joins the scheduler's interval problem to Splitwise's money problem: a car must never be promised to two customers for overlapping days, and the bill must be computed from rules that change by season, add-on and how late the car comes back. It is also the first walkthrough where one record lives through a long lifecycle — held, confirmed, picked up, returned, closed — and each step changes what is allowed next.

Scope and requirements

Interviewer: Design the classes for a car rental company with branches across the country.

You: Two things decide the design: how we stop double-booking a car across date ranges, and how the price is computed both at booking and at return. Questions:

Interviewer: Customers book a type — hatchback, sedan, SUV — at a branch. The car is returned to the same branch for now. Daily rates per type, a higher rate on Saturdays and Sundays, and add-ons such as GPS and a child seat charged per day. We pre-authorise the card when booking; the hold lasts fifteen minutes. Late returns have a one-hour grace period, then an hourly charge, never more than a day's rate per late day. Damage is assessed by staff. Two hours of cleaning between rentals.

You: Requirements, then.

Functional:

• Search availability by branch, type and dates; get a price quote.
• Reserve a type for a date range: hold for fifteen minutes while the card is pre-authorised, then confirm.
• Cancel; mark no-shows.
• Pick up: the desk assigns or swaps the actual car, records odometer and fuel.
• Return: record time, odometer, fuel and damage; compute late, damage and fuel charges; close the invoice.

Constraints:

• A car is never reserved for overlapping periods, cleaning buffer included, even with concurrent bookings on several servers.
• Money in integer paise; quotes are reproducible from the rules in force at booking.
• Times are instants; each branch has a time zone, which decides what a "Saturday" is.

Assign a concrete car at booking time, so "no double-booking" becomes a simple overlap check on one car's timeline.

Interviewer: Why not just count — five SUVs at the branch, so allow five overlapping SUV bookings?

You: Counting can be made correct, but it is easy to get wrong. The right question is not "how many bookings overlap my period" — ten might, five on Monday and five on Friday — but "at the busiest moment of my period, how many cars are in use", and a car in maintenance or returned late silently breaks that number. Assigning a car makes every check local and exact. The cost is fragmentation: first-fit assignment can refuse a booking that a reshuffle would fit. Because customers book a type, not a car, future assignments can be moved, so on a refusal we try reassigning reservations not yet picked up before saying no.

What's being probed: choosing the unit of inventory so the correctness check stays simple.

Concept — the unit you lock is the unit you check. In reservation systems you can track inventory as a count ("5 SUVs") or as individual items ("SUV KA-01-1234"). Counts suit identical, interchangeable things over a single instant, like seats in a fare bucket. Items suit things with their own timeline, where availability depends on what happened before and after. R19's BookMyShow tracks individual seats for the same reason. Pick the unit where "is it free?" is one local question.

Takeaway: If availability depends on time ranges, reserve individual items and check overlaps on each item's timeline.

Entities and responsibilities

Interviewer: Classes?

You: Nouns: branch, vehicle, type, customer, reservation, period, quote, add-on, pickup, return, damage, invoice. Verbs: reserve (needs the fleet and every reservation for a car — a service), price (a rule that varies — a strategy), pick up and return (lifecycle moves on the reservation itself), charge (a calculator run at return).

Class diagram

classDiagram
  class Reservation {
    +ReservationId id
    +VehicleId vehicle
    +RentalPeriod period
    +RentalStatus status
    +Quote quote
    +moveTo(RentalStatus)
  }
  class PricingStrategy {
    <<interface>>
    +quote(VehicleType, RentalPeriod, ZoneId) Quote
  }
  Branch "1" *-- "many" Vehicle
  Vehicle "1" --> "many" Reservation : timeline
  Customer "1" --> "many" Reservation
  Reservation --> RentalPeriod
  Reservation --> RentalStatus
  Reservation "1" *-- "1" Invoice
  ReservationService --> PricingStrategy
  ReservationService --> PaymentGateway
  PricingStrategy <|.. DailyRatePricing
  PricingStrategy <|.. AddOnPricing
  AddOnPricing o-- PricingStrategy : wraps

The key relationships: a Vehicle has a timeline of reservations, and the overlap check only ever looks at one vehicle's timeline. AddOnPricing both implements and wraps PricingStrategy — the Decorator shape — so GPS and child seat stack on any base rate. The reservation owns its invoice and damage reports (one at pickup, one at return), which die with it.

Key flows

Interviewer: Walk me through a rental, end to end.

stateDiagram-v2
  [*] --> Held : car assigned, card pre-auth started
  Held --> Confirmed : pre-auth approved
  Held --> Expired : 15 minutes pass
  Confirmed --> Cancelled : customer cancels
  Confirmed --> NoShow : not collected in time
  Confirmed --> PickedUp : desk hands over keys
  PickedUp --> Returned : car back, charges computed
  Returned --> Closed : invoice captured
  Closed --> [*]

1. Hold. The customer asks for an SUV at the Koramangala branch, Friday 10:00 to Monday 10:00. The service locks the branch's SUV pool, finds an SUV with nothing overlapping that period plus cleaning, and creates a HELD reservation with a fifteen-minute expiry and the quote.
2. Confirm. The card pre-authorisation for the quote plus a deposit comes back approved. The reservation moves to CONFIRMED — but only if it is still HELD and unexpired.
3. Release. If the customer abandons, nobody needs to act: an expired hold no longer blocks the car (lazy expiry). A sweeper marks it EXPIRED and voids the pre-authorisation.
4. Pick up. The desk checks the licence, records odometer, fuel and existing scratches, and moves the reservation to PICKED_UP. If the assigned car is not ready, it swaps in another free SUV using the same overlap check.
5. Return. The desk records time, odometer, fuel and any new damage; ReturnCharges adds late, fuel and damage lines.
6. Close. The invoice captures against the pre-authorisation and charges any remainder separately.

These are R19's hold, confirm, release at class level: HELD with an expiry is the hold, the move to CONFIRMED is the confirm, and EXPIRED or CANCELLED is the release.

Patterns used, and why

The core code

Interviewer: Show me the overlap check, the lifecycle and the pricing.

You: The period. The cleaning buffer is added to the end of both periods before comparing, which is exactly "the next pickup must be at least two hours after the previous drop-off".

public record RentalPeriod(Instant pickup, Instant dropoff) {
    public RentalPeriod {
        if (!pickup.isBefore(dropoff)) throw new IllegalArgumentException("pickup must be before dropoff");
    }
    public boolean overlaps(RentalPeriod o, Duration buffer) {
        return pickup.isBefore(o.dropoff.plus(buffer)) && o.pickup.isBefore(dropoff.plus(buffer));
    }
    /** Each started 24 hours is a billable day; minimum one. */
    public long billableDays() {
        long minutes = Duration.between(pickup, dropoff).toMinutes();
        return Math.max(1, (minutes + 1439) / 1440);
    }
}

The lifecycle. The enum owns the transition table, so an illegal move like HELD straight to PICKED_UP is impossible. blocksVehicle is the lazy expiry: an expired hold simply stops counting.

public enum RentalStatus {
    HELD, CONFIRMED, PICKED_UP, RETURNED, CLOSED, EXPIRED, CANCELLED, NO_SHOW;

    private static final Map<RentalStatus, Set<RentalStatus>> NEXT = Map.of(
        HELD, EnumSet.of(CONFIRMED, EXPIRED, CANCELLED),
        CONFIRMED, EnumSet.of(PICKED_UP, CANCELLED, NO_SHOW),
        PICKED_UP, EnumSet.of(RETURNED),
        RETURNED, EnumSet.of(CLOSED));

    public boolean canMoveTo(RentalStatus to) { return NEXT.getOrDefault(this, Set.of()).contains(to); }
}

public final class Reservation {
    private final ReservationId id;
    private final CustomerId customer;
    private final BranchId branch;
    private final VehicleType type;
    private VehicleId vehicle;                       // may be swapped at pickup
    private final RentalPeriod period;
    private final Quote quote;
    private final Instant holdExpiresAt;
    private RentalStatus status = RentalStatus.HELD;
    // constructor and getters elided

    public synchronized void moveTo(RentalStatus to) {
        if (!status.canMoveTo(to)) throw new IllegalStateException(status + " cannot move to " + to);
        status = to;
    }

    public synchronized boolean blocksVehicle(Instant now) {
        return switch (status) {
            case CONFIRMED, PICKED_UP -> true;
            case HELD -> now.isBefore(holdExpiresAt);
            default -> false;
        };
    }
}

The reservation service. It takes one lock per (branch, type) pool, so two people booking SUVs at Koramangala are serialised, while sedans and other branches proceed in parallel. Inside the lock, find a car with no blocking overlap, then create the hold.

public final class ReservationService {
    private static final Duration CLEANING = Duration.ofHours(2), HOLD_TTL = Duration.ofMinutes(15);
    private record PoolKey(BranchId branch, VehicleType type) {}

    private final ConcurrentHashMap<PoolKey, Object> poolLocks = new ConcurrentHashMap<>();
    private final Fleet fleet;
    private final ReservationRepository reservations;
    private final PricingStrategy pricing;
    private final Clock clock;
    // constructor elided

    public Reservation hold(CustomerId customer, BranchId branch, VehicleType type, RentalPeriod period) {
        Object lock = poolLocks.computeIfAbsent(new PoolKey(branch, type), k -> new Object());
        synchronized (lock) {
            Instant now = clock.instant();
            Vehicle car = fleet.inService(branch, type).stream()
                .filter(v -> reservations.forVehicle(v.id()).stream()
                    .noneMatch(r -> r.blocksVehicle(now) && r.period().overlaps(period, CLEANING)))
                .findFirst()
                .orElseThrow(() -> new NoVehicleAvailable(branch, type, period));
            Quote quote = pricing.quote(type, period, fleet.zoneOf(branch));
            Reservation r = new Reservation(ReservationId.next(), customer, branch, type, car.id(),
                                            period, quote, now.plus(HOLD_TTL));
            reservations.save(r);
            return r;
        }
    }

    public void confirm(Reservation r) {
        Object lock = poolLocks.computeIfAbsent(new PoolKey(r.branch(), r.type()), k -> new Object());
        synchronized (lock) {
            if (!r.blocksVehicle(clock.instant())) throw new HoldExpired(r.id());   // void the pre-auth
            r.moveTo(RentalStatus.CONFIRMED);
        }
    }
}

Pricing: a base strategy that looks at each day in the branch's zone to decide weekday or weekend, and a decorator that adds a per-day line.

public record ChargeLine(String label, long paise) {}
public record Quote(List<ChargeLine> lines) {
    public long total() { return lines.stream().mapToLong(ChargeLine::paise).sum(); }
}

public interface PricingStrategy { Quote quote(VehicleType type, RentalPeriod p, ZoneId zone); }

public final class DailyRatePricing implements PricingStrategy {
    private final Map<VehicleType, Long> weekday, weekend;       // paise per day; constructor elided
    public Quote quote(VehicleType type, RentalPeriod p, ZoneId zone) {
        LocalDate first = p.pickup().atZone(zone).toLocalDate();
        long total = 0;
        for (long i = 0; i < p.billableDays(); i++) {
            DayOfWeek d = first.plusDays(i).getDayOfWeek();
            boolean isWeekend = d == DayOfWeek.SATURDAY || d == DayOfWeek.SUNDAY;
            total += (isWeekend ? weekend : weekday).get(type);
        }
        return new Quote(List.of(new ChargeLine(p.billableDays() + " days, " + type, total)));
    }
}

public final class AddOnPricing implements PricingStrategy {       // Decorator
    private final PricingStrategy inner;                           // the strategy being wrapped
    private final String name;
    private final long perDayPaise;                                // constructor elided
    public Quote quote(VehicleType type, RentalPeriod p, ZoneId zone) {
        List<ChargeLine> lines = new ArrayList<>(inner.quote(type, p, zone).lines());
        lines.add(new ChargeLine(name, Math.multiplyExact(perDayPaise, p.billableDays())));
        return new Quote(lines);
    }
}
// new AddOnPricing(new AddOnPricing(base, "GPS", 20_000), "Child seat", 15_000)

Return charges. The late fee is the smaller of "each started hour" and "a day's rate per started late day", after the grace period.

public final class ReturnCharges {
    private static final Duration GRACE = Duration.ofHours(1);

    public List<ChargeLine> compute(RentalPeriod booked, Instant returnedAt, long hourly, long daily,
                                    List<DamageItem> newDamage) {
        List<ChargeLine> lines = new ArrayList<>();
        Duration late = Duration.between(booked.dropoff(), returnedAt);
        if (late.compareTo(GRACE) > 0) {
            long hours = (late.toMinutes() + 59) / 60;
            long days = (hours + 23) / 24;
            lines.add(new ChargeLine("Late return, " + hours + " h", Math.min(hours * hourly, days * daily)));
        }
        newDamage.forEach(d -> lines.add(new ChargeLine("Damage: " + d.description(), d.assessedPaise())));
        return lines;                                               // fuel line elided
    }
}

A worked example, with assumed rates: sedan ₹2,000 on weekdays, ₹2,500 at weekends, ₹300 an hour.

Booked Fri 10:00 → Mon 10:00 IST = 72 h → 3 billable days: Fri, Sat, Sun
Base   = 200,000 + 250,000 + 250,000 = 700,000 paise (₹7,000)
GPS    = 20,000 × 3                  =  60,000 paise
Returned Mon 13:20 → 3 h 20 min late → beyond 1 h grace → 4 started hours
Late   = min(4 × 30,000, 1 × 200,000) = 120,000 paise
Total  = 880,000 paise (₹8,800)

Concurrency, edge cases and testing

Interviewer: Several servers. Your pool lock is in one JVM.

You: Then the pool lock moves into the database as a row: one fleet_pool row per (branch, type), locked with FOR UPDATE. Every booking for that pool queues on that row; then a new statement looks for a free car. Under Postgres's default READ COMMITTED level, each statement takes a fresh snapshot, so the search after the lock sees any reservation committed by the transaction that held the lock before us.

BEGIN;
SELECT 1 FROM fleet_pool WHERE branch_id = :b AND type = :t FOR UPDATE;   -- the mutex
SELECT v.id FROM vehicle v
 WHERE v.branch_id = :b AND v.type = :t AND v.in_service
   AND NOT EXISTS (
     SELECT 1 FROM reservation r
      WHERE r.vehicle_id = v.id
        AND (r.status IN ('CONFIRMED', 'PICKED_UP')
             OR (r.status = 'HELD' AND r.hold_expires_at > now()))
        AND r.pickup < :dropoff + interval '2 hours'
        AND :pickup < r.dropoff + interval '2 hours')
 ORDER BY v.id LIMIT 1;
INSERT INTO reservation (id, vehicle_id, pickup, dropoff, status, hold_expires_at, ...)
VALUES (:id, :vehicleId, :pickup, :dropoff, 'HELD', now() + interval '15 minutes', ...);
COMMIT;

Searching for a free car first and locking it afterwards is the classic check-then-act race; lock the pool, then search.

Serialising one branch's SUV bookings is fine: a busy branch takes a few bookings a minute, each holding the lock for milliseconds.

Tests: the overlap rule at the edges (drop-off at 10:00, next pickup at 11:59 is refused and at 12:00 accepted); every illegal status move throws; the worked pricing example above as a fixed test; and many threads holding the last SUV at once, where exactly one succeeds.

Extensions the interviewer will ask for

Interviewer: Allow one-way rentals — return to another branch.

You: A car's location now depends on time. Vehicle gains locationAt(instant), derived from its last reservation's return branch before that instant. The availability filter adds "is at this branch at pickup time". The lock moves from (branch, type) to (city, type), since a car can move between branches in the same city.

Interviewer: A loyalty discount of 10% on the base rate.

You: Another decorator, DiscountPricing, adding a negative line rounded to whole paise. The factory that builds the chain fixes the order: discount on the base, then add-ons.

Interviewer: Block cars for scheduled maintenance.

You: A car's timeline holds more than reservations. Introduce a sealed CalendarBlock with two records, Reservation and MaintenanceWindow, both with a period and blocksVehicle. The overlap check runs over blocks, unchanged.

Quick reference

The 60-second version

A car rental is an interval problem with money attached. The customer books a type, but the system assigns a concrete car at hold time, so preventing double-booking becomes an overlap check on one car's timeline, with the two-hour cleaning buffer added to each drop-off. A reservation follows R19's hold, confirm and release: HELD with a fifteen-minute expiry while the card is pre-authorised, CONFIRMED only if the hold is still alive, and expired holds simply stop blocking the car. The lifecycle continues through pickup, return and close, guarded by an enum that owns its transition table. Bookings for one branch and type are serialised by a lock — in memory for one process, a locked pool row followed by a fresh search in the database. Prices come from a pricing strategy that counts days in the branch's zone, with add-ons and discounts as decorators; late, damage and fuel charges are separate lines computed at return in integer paise.

Walkthrough 10 — Airline management: fares, seats and holds that expire

Building on car rental: the car rental held one car for one date range. An airline booking holds several things at once — a place in a fare class and a physical seat, on every flight of an itinerary — and must take all of them or none. The hold, confirm and release shape from R19 stays the same; what grows is the number of inventories a single booking touches, and the clean-up when one of them says no.

Scope and requirements

Interviewer: Design the classes for an airline's booking system.

You: An airline is a big domain — crew, baggage, check-in, loyalty. I would like to focus on flights, fares, seats and bookings unless you want otherwise. Questions:

Interviewer: Booking, seats and cancellations. Each flight has fare classes in economy and business, each with a number of seats it may sell. Connections are booked together, all or nothing. Hold for fifteen minutes while paying. Seats can be chosen at booking or later; extra-legroom seats cost more. Refund rules, as given here: Saver fares refund only the taxes; Flex fares refund everything minus a ₹2,000 fee if cancelled more than 24 hours before departure, otherwise only taxes. No overbooking for now.

You: Requirements, then.

Functional:

• Publish schedules ("XX-123 BLR→DEL daily at 06:15 local") and generate dated flight instances with an aircraft and seat map.
• Search flights; show fares by class with availability.
• Hold an itinerary for N passengers: a place in the chosen fare class on every segment, plus any chosen seats, for fifteen minutes.
• Confirm on payment: issue tickets. Release on expiry or abandonment.
• Assign or change seats after booking.
• Cancel a booking or one passenger; refund per the fare class rules.

Constraints:

• Never sell more seats in a fare class than it allows, and never give one physical seat to two passengers.
• An itinerary is held and ticketed as a whole.
• Money in integer paise. Times as instants; schedules in the origin airport's local time.
• A payment that succeeds must end in tickets or a full refund.

A booking draws on two inventories — a count in a fare bucket and a specific seat — and both must be held, confirmed and released together.

Interviewer: Why two? A seat is a seat.

You: Because they answer different questions. The fare bucket answers "may we sell another ticket at ₹4,500?" — it is a revenue rule, and the seats behind it are interchangeable, so a count is right. The seat map answers "which chair does this passenger sit in?" — each one is unique, so it needs item-level tracking, like BookMyShow's seats in R19. Many passengers book without choosing a seat; they consume the count now and get a seat at check-in. Keeping them separate lets each be simple.

Entities and responsibilities

Interviewer: Classes?

You: Nouns: airport, aircraft, seat map, schedule, flight, fare class, fare bucket, seat, passenger, booking, segment, ticket, payment, refund. The trap is "flight": the schedule "XX-123 daily" and the instance "XX-123 on 14 November" are different things — one is a rule, the other has an aircraft, seats and bookings. Verbs: hold, confirm, release belong to the inventory of a flight instance; book across segments belongs to a service that coordinates them; refund is a fare-class rule.

Class diagram

classDiagram
  class FlightSchedule {
    +String flightNo
    +LocalTime departsLocal
    +Set days
    +instanceOn(LocalDate) FlightInstance
  }
  class FlightInventory {
    +hold(BookingId, fare, count, seats, expiresAt) boolean
    +confirm(BookingId) boolean
    +release(BookingId)
    +unsell(BookingId)
  }
  class RefundPolicy {
    <<interface>>
    +refund(fare, taxes, beforeDeparture) long
  }
  FlightSchedule "1" --> "many" FlightInstance : generates
  FlightInstance "1" *-- "1" FlightInventory
  FlightInstance --> SeatMap
  FareClass --> RefundPolicy
  Booking "1" *-- "many" Segment
  Booking "1" *-- "many" Passenger
  Segment --> FlightInstance
  Segment --> FareClass
  BookingService --> FlightInventory
  BookingService --> PaymentService
  RefundPolicy <|.. SaverPolicy
  RefundPolicy <|.. FlexPolicy

The key relationships: a FlightSchedule generates instances but owns none of their state. Each FlightInstance owns exactly one FlightInventory, the only object allowed to change that flight's counts and seats — one guard per flight, as in the car rental's one timeline per car. A Booking references instances through its segments; it never edits their inventory directly, only through BookingService.

Key flows

Interviewer: Walk me through booking a connection, Bengaluru to London via Delhi.

sequenceDiagram
  participant C as Customer
  participant B as BookingService
  participant I1 as Inventory BLR-DEL
  participant I2 as Inventory DEL-LHR
  participant P as PaymentService
  C->>B: hold itinerary, 2 passengers, Saver
  B->>I1: hold booking, Saver, 2 seats, expires in 15 min
  I1-->>B: true
  B->>I2: hold booking, Saver, 2 seats, expires in 15 min
  I2-->>B: true
  B-->>C: booking HELD, pay within 15 min
  C->>P: pay
  P-->>B: payment succeeded
  B->>I1: confirm booking
  B->>I2: confirm booking
  B-->>C: TICKETED, e-tickets issued

1. The customer picks two flights and a Saver fare for two passengers. BookingService creates a booking id and asks each flight's inventory, in turn, to hold two Saver places (and any chosen seats) until fifteen minutes from now.
2. If the second leg says no — Saver sold out on DEL→LHR — the service releases the first leg's hold at once and reports the failure. The customer never owns half an itinerary.
3. With both legs held, the booking is HELD with an expiry. Nothing is sold yet.
4. On payment success, the service confirms each leg. Each inventory turns the hold into a sale, but only if the hold is still alive.
5. Both confirmed: the booking is TICKETED and tickets are issued from an event. If the customer walks away instead, the holds expire inside the inventories on their own, and a sweeper marks the booking EXPIRED for tidiness.

Interviewer: Holding the legs one after another is not atomic. Another customer could see the first leg's seats taken for a moment and give up.

You: True, and acceptable. For a few milliseconds the first leg shows two fewer places; if the second leg fails, they come straight back. What matters is that no customer ends up owning half an itinerary, and the release guarantees that. In one database it can be a single transaction instead — lock both flights' bucket rows in a fixed order, by flight id, so two bookings crossing the same pair of flights cannot deadlock.

What's being probed: all-or-nothing across several resources, without pretending it is free.

Concept — compensation versus atomicity. When one action touches several independent guards, you either take them all inside one transaction (atomic, but they must live in one database and be locked in a fixed order), or take them one by one and undo the earlier ones if a later one fails (compensation — the saga idea from R5). Compensation briefly exposes a partial state, so it fits when that partial state is harmless — a hold that nobody has paid for. R2 compares the two.

Takeaway: Take every leg or none: one ordered transaction when you can, prompt release of earlier holds when you cannot.

Patterns used, and why

The core code

Interviewer: Show me the inventory and the booking service.

You: Schedules turn into instances in the origin airport's zone. XX-123 leaving Bengaluru at 06:15 local is 00:45 UTC; the arrival is shown in the destination's zone.

public record Airport(String code, ZoneId zone) {}
public record FlightInstanceId(String flightNo, LocalDate localDate) {}
public record FlightInstance(FlightInstanceId id, Instant departs, Instant arrives) {}

public record FlightSchedule(String flightNo, Airport origin, Airport destination,
                             LocalTime departsLocal, Duration blockTime, Set<DayOfWeek> days) {
    public Optional<FlightInstance> instanceOn(LocalDate localDate) {
        if (!days.contains(localDate.getDayOfWeek())) return Optional.empty();
        Instant dep = ZonedDateTime.of(localDate, departsLocal, origin.zone()).toInstant();
        return Optional.of(new FlightInstance(new FlightInstanceId(flightNo, localDate), dep, dep.plus(blockTime)));
    }
}

The inventory of one flight instance. A Claim is a booking's take of one fare bucket and some seats; it lives either in holds (with an expiry) or in sold. Availability counts both, so a held place cannot be sold twice. Every public method first drops expired holds — lazy expiry, so correctness never waits for a background job.

public final class FlightInventory {
    private record Claim(String fareCode, int count, Set<SeatNo> seats, Instant expiresAt) {}

    private final Map<String, Integer> bucketCapacity;            // seats sellable per fare code
    private final Map<BookingId, Claim> holds = new HashMap<>();
    private final Map<BookingId, Claim> sold = new HashMap<>();

    public FlightInventory(Map<String, Integer> bucketCapacity) { this.bucketCapacity = Map.copyOf(bucketCapacity); }

    public synchronized boolean hold(BookingId b, String fare, int count, Set<SeatNo> seats,
                                     Instant expiresAt, Instant now) {
        dropExpired(now);
        if (holds.containsKey(b) || sold.containsKey(b)) return true;    // idempotent retry
        if (available(fare) < count || !seats.stream().allMatch(this::seatFree)) return false;
        holds.put(b, new Claim(fare, count, Set.copyOf(seats), expiresAt));
        return true;
    }

    public synchronized boolean confirm(BookingId b, Instant now) {
        dropExpired(now);
        if (sold.containsKey(b)) return true;                              // duplicate callback
        Claim c = holds.remove(b);
        if (c == null) return false;                                       // hold lapsed
        sold.put(b, c);
        return true;
    }

    public synchronized void release(BookingId b) { holds.remove(b); }
    public synchronized void unsell(BookingId b)  { sold.remove(b); }      // cancellation

    private int available(String fare) {
        int taken = Stream.concat(holds.values().stream(), sold.values().stream())
                          .filter(c -> c.fareCode().equals(fare)).mapToInt(Claim::count).sum();
        return bucketCapacity.getOrDefault(fare, 0) - taken;
    }

    private boolean seatFree(SeatNo s) {
        return Stream.concat(holds.values().stream(), sold.values().stream())
                     .noneMatch(c -> c.seats().contains(s));
    }

    private void dropExpired(Instant now) { holds.values().removeIf(c -> !now.isBefore(c.expiresAt())); }
    // seat-change after ticketing, cabin checks against the seat map, and indexes for speed elided
}

The booking service takes every leg or none, and on a late payment tries once more before refunding.

public final class BookingService {
    private static final Duration HOLD_TTL = Duration.ofMinutes(15);
    private final InventoryRegistry inventories;
    private final BookingRepository bookings;
    private final PaymentService payments;
    private final BookingEvents events;
    private final Clock clock;
    // constructor elided

    public Booking hold(List<SegmentRequest> segments, List<Passenger> pax) {
        Instant now = clock.instant(), expires = now.plus(HOLD_TTL);
        BookingId id = BookingId.next();
        List<FlightInventory> held = new ArrayList<>();
        for (SegmentRequest s : segments) {
            FlightInventory inv = inventories.of(s.flight());
            if (!inv.hold(id, s.fareCode(), pax.size(), s.seats(), expires, now)) {
                held.forEach(h -> h.release(id));                          // compensate
                throw new SoldOut(s.flight(), s.fareCode());
            }
            held.add(inv);
        }
        return bookings.save(Booking.held(id, segments, pax, expires));
    }

    public Booking onPaymentSucceeded(BookingId id, PaymentId payment) {
        Booking b = bookings.get(id);
        synchronized (b) {
            if (b.status() == BookingStatus.TICKETED) return b;           // duplicate callback
            Instant now = clock.instant();
            List<FlightInventory> confirmed = new ArrayList<>();
            for (Segment s : b.segments()) {
                FlightInventory inv = inventories.of(s.flight());
                boolean ok = inv.confirm(id, now)
                          || (inv.hold(id, s.fareCode(), b.passengerCount(), s.seats(), now.plusSeconds(5), now)
                              && inv.confirm(id, now));                    // late payment: try again
                if (!ok) {
                    confirmed.forEach(c -> c.unsell(id));
                    b.moveTo(BookingStatus.EXPIRED);
                    payments.refundInFull(payment, "refund:" + id.value());
                    return b;
                }
                confirmed.add(inv);
            }
            b.moveTo(BookingStatus.TICKETED);
            events.publish(new BookingEvent.Ticketed(id));
            return b;
        }
    }
}

Refund rules are strategies on the fare class. The rules are the interviewer's, not any real airline's.

public interface RefundPolicy {
    long refundPaise(long farePaise, long taxesPaise, Duration beforeDeparture);
}

public record SaverPolicy() implements RefundPolicy {
    public long refundPaise(long fare, long taxes, Duration before) { return taxes; }
}
public record FlexPolicy(long feePaise, Duration cutoff) implements RefundPolicy {
    public long refundPaise(long fare, long taxes, Duration before) {
        return before.compareTo(cutoff) > 0 ? Math.max(0, fare - feePaise) + taxes : taxes;
    }
}
// new FlexPolicy(200_000, Duration.ofHours(24))

Cancellation is the reverse path: for each segment, unsell, compute the refund with that segment's fare class policy, and refund through the payment service with the idempotency key refund:{bookingId}:{passenger} so a retried cancel never refunds twice (R3).

Concurrency, edge cases and testing

Interviewer: In production this is a database, not a synchronized map.

You: Two guards per flight, each made atomic in the database. The fare bucket uses lock-then-check, as in the car rental: lock the bucket row, count live holds in a fresh statement, then insert. Seats use BookMyShow's conditional update with the row count as the verdict.

BEGIN;
SELECT capacity, sold FROM fare_bucket
 WHERE flight_id = :f AND fare_code = :c FOR UPDATE;              -- several legs: lock in flight_id order
SELECT COALESCE(SUM(pax_count), 0) FROM inventory_hold
 WHERE flight_id = :f AND fare_code = :c AND expires_at > now();
-- in Java: if capacity - sold - held < :n, ROLLBACK and report sold out
INSERT INTO inventory_hold (booking_id, flight_id, fare_code, pax_count, expires_at)
VALUES (:b, :f, :c, :n, now() + interval '15 minutes');
UPDATE flight_seat SET status = 'HELD', booking_id = :b, hold_expires_at = now() + interval '15 minutes'
 WHERE flight_id = :f AND seat_no IN ('14A', '14B')
   AND (status = 'AVAILABLE' OR (status = 'HELD' AND hold_expires_at < now()));
-- rows updated must equal seats requested, otherwise ROLLBACK
COMMIT;

A payment can succeed after its hold has expired; the confirm must be conditional, and the fallback is a refund, never a double sale.

Tests: the bucket never goes negative under hundreds of concurrent holds; one seat is never held by two bookings; a two-leg hold where the second fails leaves the first leg's availability unchanged; a payment that arrives one second after expiry is either ticketed (inventory still free) or refunded, never both.

Extensions the interviewer will ask for

Interviewer: Allow overbooking — sell 3% more economy seats than physically exist.

You: Fare-bucket capacity is already separate from physical seats, so the bucket capacities simply add up to more than the cabin. Seat assignment stays strict. A DeniedBoardingHandler at check-in deals with the rare case where everyone turns up. No change to hold, confirm or release.

Interviewer: A waitlist when Saver is sold out.

You: The inventory publishes PlacesReleased on release, expiry and unsell (Observer). A waitlist service subscribes and offers the place to the next person as a fresh hold with its own expiry.

Interviewer: Revenue management wants nested fare buckets — a cheaper class must never take places kept for a dearer one.

You: available(fare) becomes a policy: a BucketPolicy strategy that, for nested buckets, counts claims in the fare and every cheaper fare against the fare's limit. The inventory calls the policy; hold, confirm and release do not change.

Quick reference

The 60-second version

An airline booking is R19's hold, confirm and release applied to several inventories at once. Schedules are rules in the origin's local time that generate dated flight instances, and each instance owns one inventory guarding two things: a count per fare bucket, because places at a price are interchangeable, and specific seats, because chairs are not. A booking holds a fare-class place and any chosen seats on every leg for fifteen minutes; if any leg refuses, the earlier holds are released at once. Expired holds stop counting the moment they lapse, so no background job is needed for correctness. On payment, every leg is confirmed only if its hold is still alive; a late payment tries once more and otherwise unsells the confirmed legs and refunds in full. In the database, the fare bucket is a locked row checked in a fresh statement and seats use a conditional update with the row count as the verdict. Refund rules are strategies on the fare class, and refunds carry idempotency keys.

What to say in the interview

"Whatever the object — an ATM, an elevator, a chessboard, an expense or a seat — I follow the same rhythm: clarify the few use cases that matter, find the classes from the nouns and the methods from the verbs, draw the relationships, walk the central flow, then code the core. Lifecycles become State classes, changeable policies become Strategies, actions that must be queued or undone become Commands, and side effects reach the outside world through Observers or an outbox. Where money or bookings are involved, I keep amounts in integer minor units, make every operation idempotent, and decide double-booking in one atomic step — a lock around one object's timeline, or a conditional write in the database. And I finish by adding a new requirement as a new class, to show the design is open for extension and closed for modification."