ATM Machine

Design a cash machine: card, PIN with three tries, balance, withdraw, deposit and receipt. The machine's states and the way notes are chosen are the two ideas the interviewer wants to see.

Design an ATM. A customer inserts a card and enters a PIN. After three wrong PINs the card is blocked. A signed-in customer can check the balance, withdraw cash, deposit money and get a receipt. The ATM pays out the largest notes first from a limited stock of notes. The bank's computer is a separate system that the ATM calls.

Questions to ask first

Which notes does the machine hold? Assume values of 500, 200 and 100, each with a count that staff load. A withdrawal must be a multiple of 100.
How is a note mix chosen? Assume largest notes first, as many as the amount and the stock allow, then the next smaller note. This is the simple rule most people expect.
How many PIN tries? Assume three in a row for one card insertion. After the third wrong try the machine keeps the card and the bank blocks it.
Who keeps the balance? Assume the bank does. The ATM asks the bank for the balance and tells it to debit or credit. We design the ATM, not the bank.
What does a deposit do? Assume the customer enters an amount, the bank credits the account and the receipt records it. The cash does not refill the notes the machine pays out.
What if two machines use one account at once? Assume the bank makes debit atomic, so the ATM must treat a refused debit as a refused withdrawal.

Requirements

Accept a card and refuse a card that is unknown or blocked.
Check the PIN with the bank. Allow three wrong tries in a row, then block the card and keep it.
After a good PIN, show the balance, withdraw cash and deposit money until the customer takes the card back.
Withdraw: refuse an amount that is not a positive multiple of 100, refuse when the balance is too low, and refuse when the machine cannot make the amount from its notes.
Dispense the largest notes first from a finite stock, and take notes out of the stock only when the withdrawal goes through.
Keep a receipt of the last withdrawal or deposit.
Refuse every action that does not fit the machine's current state, such as a withdrawal before the PIN.

Out of scope

Card readers, screens, keypads and cash-slot hardware.
The bank's own design: accounts, limits and fraud checks.
Network failures between the ATM and the bank.
Cheque deposits and cash that is counted into the machine on deposit.
Printing a paper receipt: the receipt is text.

Entities

Atm: the machine; insertCard(card), enterPin(pin), balance(), withdraw(amount), deposit(amount), ejectCard()
AtmState: one object per state; each action is allowed or refused by the state
IdleState, HasCardState, AuthenticatedState: the three states
Session: the card in the machine and its count of wrong PINs
Bank: an interface to the bank's computer; checkPin, balance, debit, credit, block
CardStatus: ACTIVE, BLOCKED, UNKNOWN
NoteDispenser: the stock of notes; plan(amount), commit(plan)
DispenseHandler and NoteHandler: the chain, one link for each note value
Receipt: kind, amount and balance after

Classes in the model design

Atm (class)
AtmState (interface)
IdleState (class)
HasCardState (class)
AuthenticatedState (class)
Session (class)
Bank (interface)
CardStatus (enum)
NoteDispenser (class)
DispenseHandler (interface)
NoteHandler (class)
Receipt (class)

The main use case, step by step

A customer inserts a card. The caller runs `atm.insertCard("1111")`. `Atm` does no checking itself. It passes the call to its current state, which is `IdleState`.
`IdleState` asks the `Bank` for the card's status. A card that is UNKNOWN or BLOCKED is refused. Otherwise the state starts a `Session` for the card and moves the machine to `HasCardState`.
The customer enters a PIN. `HasCardState` asks the bank to check it. A good PIN moves the machine to `AuthenticatedState`. A wrong PIN adds one to the session's count and says how many tries are left. The third wrong PIN blocks the card at the bank and returns the machine to `IdleState`.
The customer asks for 1200. `AuthenticatedState.withdraw` checks that the amount is a positive multiple of 100. Then it asks the bank for the balance and refuses if the balance is lower than the amount.
Next it asks `NoteDispenser.plan(1200)`. The first `NoteHandler` takes as many 500 notes as the stock allows. It passes the rest to the 200 handler, then the 100 handler. The result is a plan, such as two 500 notes and one 200 note. No stock has changed yet.
If a plan exists, the state asks the bank to debit 1200. Only when the debit works does it call `commit(plan)` to take the notes out of the stock. It then saves a `Receipt` and returns the notes. Any refusal before this point leaves the money and the notes untouched.

Patterns used

State: AtmState with IdleState, HasCardState and AuthenticatedState. Atm passes every action to its current state.. What a button does depends on the machine's state. Each state class holds its own rules and moves the machine on, so Atm has no long if chains and no flags that can disagree.
Chain of responsibility: DispenseHandler with one NoteHandler for each note value, linked from the largest value to the smallest.. Each link takes what it can and passes the rest on. A new note value is a new link, and the dispensing rule is in one place.
Dependency inversion: Atm depends on the Bank interface, not on a bank class.. The real bank is far away and slow. A fake bank with a few cards lets you test every path, and a change in the bank leaves the ATM unchanged.

Key code

The state interface, the Atm and the idle state

public interface AtmState {
    default String insertCard(Atm atm, String card) { return "NOT_ALLOWED"; }
    default String enterPin(Atm atm, String pin) { return "NOT_ALLOWED"; }
    default String balance(Atm atm) { return "NOT_ALLOWED"; }
    default String withdraw(Atm atm, int amount) { return "NOT_ALLOWED"; }
    default String deposit(Atm atm, int amount) { return "NOT_ALLOWED"; }
    default String eject(Atm atm) { return "NOT_ALLOWED"; }
}

public final class Atm {
    private AtmState state = new IdleState();
    // bank, dispenser, session and lastReceipt are fields too

    public String insertCard(String card) { return state.insertCard(this, card); }
    public String enterPin(String pin) { return state.enterPin(this, pin); }
    public String withdraw(int amount) { return state.withdraw(this, amount); }
    // balance, deposit and ejectCard pass on to the state in the same way

    void moveTo(AtmState next) { this.state = next; }
}

public final class IdleState implements AtmState {
    @Override
    public String insertCard(Atm atm, String card) {
        CardStatus status = atm.bank().status(card);
        if (status == CardStatus.UNKNOWN) return "UNKNOWN_CARD";
        if (status == CardStatus.BLOCKED) return "CARD_BLOCKED";
        atm.startSession(card);
        atm.moveTo(new HasCardState(3));
        return "OK";
    }
}

Checking the PIN and withdrawing

public final class HasCardState implements AtmState {
    private final int maxWrongPins;
    public HasCardState(int maxWrongPins) { this.maxWrongPins = maxWrongPins; }

    @Override
    public String enterPin(Atm atm, String pin) {
        String card = atm.session().card();
        if (atm.bank().checkPin(card, pin)) {
            atm.moveTo(new AuthenticatedState());
            return "OK";
        }
        int wrong = atm.session().recordWrongPin();
        if (wrong < maxWrongPins) return "WRONG_PIN " + (maxWrongPins - wrong) + " left";
        atm.bank().block(card);                  // the machine keeps the card
        atm.endSession();
        atm.moveTo(new IdleState());
        return "CARD_BLOCKED";
    }
}

public final class AuthenticatedState implements AtmState {
    @Override
    public String withdraw(Atm atm, int amount) {
        String card = atm.session().card();
        if (amount <= 0 || amount % 100 != 0) return "INVALID_AMOUNT";
        if (atm.bank().balance(card) < amount) return "INSUFFICIENT_FUNDS";
        var plan = atm.dispenser().plan(amount);          // nothing is taken from the stock yet
        if (plan == null) return "CANNOT_DISPENSE";
        if (!atm.bank().debit(card, amount)) return "INSUFFICIENT_FUNDS";
        atm.dispenser().commit(plan);                     // only now do the notes leave the stock
        atm.record(new Receipt("WITHDRAW", amount, atm.bank().balance(card)));
        return "DISPENSED " + NoteDispenser.describe(plan);
    }
}

The chain of note handlers

public interface DispenseHandler {
    void setNext(DispenseHandler next);
    /** Fills the plan with notes for this amount. False if some amount is left over. */
    boolean plan(int amount, Map<Integer, Integer> plan);
    void remove(Map<Integer, Integer> plan);
}

public final class NoteHandler implements DispenseHandler {
    private final int value;                 // 500, 200 or 100
    private int stock;
    private DispenseHandler next;            // the next smaller note, or null

    public NoteHandler(int value) { this.value = value; }
    public void add(int count) { stock += count; }
    @Override public void setNext(DispenseHandler next) { this.next = next; }

    @Override
    public boolean plan(int amount, Map<Integer, Integer> plan) {
        int take = Math.min(amount / value, stock);      // as many as fit and as many as we have
        if (take > 0) plan.put(value, take);
        int left = amount - take * value;
        if (left == 0) return true;
        return next != null && next.plan(left, plan);    // pass the rest on
    }

    @Override
    public void remove(Map<Integer, Integer> plan) {
        stock -= plan.getOrDefault(value, 0);
        if (next != null) next.remove(plan);
    }
}

Deep dives

Modelling the machine's states

Weak: Boolean flags hasCard and pinAccepted, and an if at the top of every method. Each new rule adds a flag, and some flag combinations make no sense, such as a PIN accepted with no card. A bug lets withdraw run in a state where it should not.

Good: An enum AtmStatus with IDLE, HAS_CARD and AUTHENTICATED, and a switch in each method. A state is one value, so nonsense combinations are gone. The cost is that the rules for one state are spread over six methods.

Great: The state pattern. AtmState has one method for each action and refuses by default. IdleState, HasCardState and AuthenticatedState override only what they allow, and they move the machine to the next state themselves. The rules for one state sit together in one class. A new state, such as OUT_OF_SERVICE, is a new class that refuses everything.

Trade-off: With three states and six actions an enum and a switch is shorter and entirely fine. The state classes pay off when states grow, hold their own data, or change often. Say which you chose and draw the state diagram: interviewers check that every arrow has a trigger.

Choosing the notes

Weak: Nested if statements for 500, then 200, then 100, with the values written in each one. A new note value edits every branch, and the stock is changed while the amount is still being worked out. A refused withdrawal can leave the stock half taken.

Good: A loop over the note values from largest to smallest, taking as many as fit and as many as are in stock. It is short and correct for this problem. Make it return a plan first and change the stock afterwards.

Great: A chain of responsibility. One NoteHandler for each value takes what it can of the amount and passes the rest to the next. A new value is a new link, so the loop and the if chain both disappear. The plan is built with no side effects, and commit removes the notes only after the bank has debited the account.

Trade-off: Largest-first is simple but can fail when stock is limited. With one 500 note and three 200 notes, 600 fails: the machine takes the 500 note and is left with 100. Three 200 notes would have worked. A search that tries other mixes (backtracking) finds it, at the cost of more code. State the rule you pick and ask the interviewer which they want.

Keeping money and notes in step

Weak: The ATM keeps its own copy of each balance and subtracts from it. Two machines can then pay out the same money, and the ATM and the bank disagree after a restart.

Good: The balance lives at the bank behind a Bank interface. The ATM asks for the balance and then debits. A fake bank in tests lets you try each path: wrong PIN, blocked card, low balance.

Great: Order the steps so that a refusal never leaves a mess. Check the amount, check the balance, plan the notes (no changes), debit at the bank, then take the notes out of the stock and write the receipt. The bank's debit returns false when the balance is too low, so two machines cannot overdraw one account even when both read the same balance first. If the cash drawer jams after the debit, the ATM sends a credit back. This is a compensating action.

Trade-off: The full order needs a plan step and a commit step, which is more code than debit-and-dispense in one go. The payoff is that every refusal changes nothing, and that is easy to test. A real bank also needs a reference number for each debit so that a retry does not charge twice. Mention it, and leave it out of the first design.

Now add one more feature

Now add a 2000 note. Call `loadNotes(2000, 1)`. The dispenser inserts a handler at the front of the chain. No state class and no withdraw code changes, because the chain finds the order by value.
Now limit each withdrawal to 1000, or each card to 5000 a day. Add a check in `AuthenticatedState.withdraw` with a new refusal such as LIMIT_EXCEEDED. A daily total belongs to the bank or to a `WithdrawalPolicy` object that the state asks, so the limit can change without editing the state.
Now take the machine out of service when the cash is low or staff open it. Add an `OutOfServiceState` that refuses every action, and a way for staff to move the machine in and out of it. `Atm` and the other states do not change.
Now make deposits of real notes. The customer inserts notes, the machine counts them, and the notes join the stock. The deposit reads a count for each value, credits the total, and calls `dispenser.load` for each value. Dispensing now uses recycled notes.

What each level is expected to show

SDE-1: Clear states with the correct transitions, three PIN tries, an Atm that never reaches the bank except through an interface, and a dispense rule that takes the largest notes first from a finite stock. Every wrong action is refused.

SDE-2: All of SDE-1, plus the plan and commit order, so that a refusal changes nothing, and a debit that can fail at the bank. Knows the limit of the largest-first rule with finite stock. Gives a reason for an enum or the state pattern. Handles extensions by naming the one class that changes.

Common mistakes

Putting the PIN, balance, note and state logic in one Atm class with flags and long if chains.
Letting an action run in the wrong state, such as a withdrawal with a card in but no PIN accepted.
Taking notes out of the stock while still working out the amount, so a refused withdrawal loses notes.
Subtracting from the balance before the notes are confirmed, or after, with no way to undo.
Keeping the balance inside the ATM instead of asking the bank, so two machines disagree.
Counting PIN tries across all cards or forever, instead of the tries for one card insertion.
Writing the note values 500, 200 and 100 into the withdraw code, so a new note edits it.