Design a Vending Machine
A finite-state machine done right — idle, selecting, dispensing, and refunding, with inventory and change.
Problem Statement
Design the object model for a vending machine that accepts payment, lets a customer select a product, dispenses it when the payment and stock are valid, and returns change or refunds when the flow cannot continue.
The interview is about the machine lifecycle. A good solution makes illegal transitions impossible: you cannot dispense before selecting, you cannot select without payment, and an out-of-stock item should not corrupt the customer transaction.
The base reference implementation uses coins, products, inventory counts, a change bank, and explicit machine states. Notes, cards, and richer payment providers are natural extensions behind the same payment and change seam.
Business context
Vending Machine is a classic beginner LLD question at Amazon, Microsoft, Adobe, and Oracle because it is small enough to finish in one interview but rich enough to expose design maturity.
Interviewers are looking for a finite-state model instead of scattered boolean flags, a single source of truth for inventory, and a payment/change policy that can evolve from coins to notes or cashless methods without rewriting the machine flow.
Functional Requirements
Display products with price and availability.
Accept supported coins and track the inserted amount for the active transaction.
Allow a customer to select a product only after payment has started.
Reject a product selection when stock is unavailable or the inserted amount is insufficient.
Dispense exactly one unit of the selected product after successful validation.
Return exact change when the inserted amount exceeds the product price.
Refund inserted coins when the customer cancels or when exact change cannot be produced.
Allow an admin to refill inventory by adding products and counts.
Non-Functional Requirements
State correctness
Every public action should be interpreted by the current state, so invalid sequences fail early and consistently.
Inventory consistency
Stock must decrement only after the machine is ready to dispense, never during a failed selection or refund.
Payment accuracy
Inserted value, refunds, and change must be computed in cents to avoid floating-point rounding errors.
Extensibility
New products, coin denominations, notes, and payment policies should be additive changes around small interfaces or isolated algorithms.
Low latency
Selection and dispensing should be in-memory operations with predictable constant-time or small linear-time behavior.
Requirement Clarification
QDo we support both coins and notes in the base design?
The reference implementation uses coins as the concrete payment unit. Model notes as the same kind of monetary input or as a future payment strategy; do not let that choice leak into the state flow.
QShould the machine require exact change from the customer?
No. The machine accepts overpayment and attempts to return exact change. If it cannot make change, it refunds the inserted coins and resets.
QCan the customer cancel at any time?
Cancellation is meaningful before dispensing. Idle cancel returns nothing, HasMoney and OutOfStock cancel refund inserted coins, and Dispensing rejects cancellation because the transaction is already committed.
QWho refills products and change?
Admin refill is modeled through the inventory and change-bank responsibilities. The reference code exposes Inventory.addProduct for product refill; a production version would add authenticated admin methods for loading change.
QDo we persist transactions or inventory to a database?
Not in the interview core. Keep the domain in memory, then call out where repositories or hardware adapters would be attached for production durability.
UML Class Diagram
Sequence Diagram
Entity Identification
VendingMachine
Aggregate root and public facade. Holds the current State, inserted coins, selected product, change bank, and the shared inventory reference.
State
Lifecycle interface for actions that vary by phase: insert coin, select product, dispense, and cancel.
IdleState
Waiting state. Accepts the first coin and moves the machine to HasMoney; selection and dispensing are invalid here.
HasMoneyState
Active payment state. Accepts more coins, validates selection, prepares change, and moves to Dispensing only when the transaction can complete.
DispensingState
Committed state. Blocks further input, decrements inventory for the selected product, clears transaction data, and returns to Idle.
OutOfStockState
Recovery state after an unavailable selection. Allows refund or selecting a different stocked product without losing inserted money.
Inventory
Single source of truth for product catalog and stock counts. Admin refill adds products and increments counts; dispensing decrements counts.
Product
Immutable product metadata: id, display name, and price in cents.
Coin
Supported monetary denomination. Values are stored as integer cents for exact payment and change calculations.
Design Patterns Used
The machine lifecycle is modeled by State implementations. Each state decides which actions are legal and when to move to another state, avoiding a large conditional block inside VendingMachine.
Inventory is treated as the single source of truth for one physical machine. The reference code keeps it injectable for testing, but the object graph should create one shared Inventory instance and route all stock reads, refills, and decrements through it.
Payment and change are isolated from the state flow. The reference code ships a greedy change algorithm behind prepareChange; in a fuller implementation that seam becomes a ChangeStrategy or PaymentStrategy without changing Idle, HasMoney, or Dispensing behavior.
Step-by-Step Design
1Start with the lifecycle, not the data tables
Model the vending machine as a finite-state workflow: Idle, HasMoney, Dispensing, and OutOfStock. Each state receives the same public actions but handles only the actions valid for that phase.
public interface State { void insertCoin(VendingMachine machine, Coin coin); void selectProduct(VendingMachine machine, String productId); void dispense(VendingMachine machine); List<Coin> cancel(VendingMachine machine); }2Keep the machine as a thin orchestrator
VendingMachine exposes insertCoin, selectProduct, dispense, and cancel, then delegates each call to currentState. It owns transaction fields such as inserted amount, selected product, and last change, but it does not decide every branch itself.
3Use HasMoneyState as the transaction validator
Product selection belongs in HasMoneyState because that is the first point where the machine has payment and a requested item. It validates stock, verifies sufficient funds, asks for change, and only then moves to Dispensing.
public void selectProduct(VendingMachine machine, String productId) { Product product = machine.getInventory().find(productId); if (!machine.getInventory().hasStock(product)) { machine.setSelectedProduct(product); machine.moveTo(machine.outOfStockState()); throw new IllegalStateException("selected product is out of stock"); } if (machine.getInsertedAmount() < product.getPrice()) { throw new IllegalStateException("insufficient funds"); } }4Make inventory the stock authority
Inventory owns both product metadata and counts. Admin refill increments counts through addProduct, while dispensing calls decrement only after the transaction is committed.
public void addProduct(Product product, int count) { if (count < 0) { throw new IllegalArgumentException("count cannot be negative"); } products.put(product.getId(), product); counts.put(product.getId(), counts.getOrDefault(product.getId(), 0) + count); }5Treat change-making as a payment policy seam
The reference code uses a greedy descending coin scan inside VendingMachine.takeChange. Keep that algorithm isolated so a richer design can swap in a different strategy for notes, cashless refunds, or denominations where greedy is not optimal.
6Commit only in DispensingState
Do not decrement inventory during selection. DispensingState is the commit point: it has a selected product, decrements stock, clears transaction data, and returns the machine to Idle.
Complete Java Implementation
Explanation of Every Class
Coin
Enumeration of supported denominations: ONE, FIVE, TEN, and TWENTY_FIVE. Each coin stores its value in cents so payment arithmetic stays integer-based.
Product
Immutable product data with id, name, and price. The constructor validates that id is present and price is positive, which keeps invalid catalog entries out of the machine.
Inventory
Catalog plus stock counter. addProduct supports admin refill, find validates product ids, hasStock answers availability, and decrement enforces the no-negative-stock invariant.
State
Lifecycle interface implemented by every machine state. It gives the same action surface to IdleState, HasMoneyState, DispensingState, and OutOfStockState.
VendingMachine
Public facade and transaction holder. It delegates actions to currentState, records inserted coins and amount, manages the change bank, stores the selected product, and exposes collectChange after a successful purchase.
IdleState
Initial waiting state. The first coin is accepted and the machine moves to HasMoneyState; selecting or dispensing before payment throws a clear error.
HasMoneyState
Payment-active state. It accepts additional coins, validates selected product and funds, prepares exact change, refunds when change cannot be made, and moves to DispensingState on success.
DispensingState
Committed state. It rejects new input, decrements inventory for the selected product, clears the transaction, and resets the machine to IdleState.
OutOfStockState
Recovery state for unavailable selections. It can accept more coins, retry a different product by returning through HasMoneyState, or cancel and refund the inserted coins.
Dry Run
Sample input
Inventory has A1 Cola priced at 125¢ with count 1. Customer inserts six TWENTY_FIVE coins, selects A1, dispenses, then collects change.
| Step | Action | State before | Transaction data | Result |
|---|---|---|---|---|
| 1 | insertCoin(25¢) | Idle | amount 0¢, selected none | Coin accepted, state HasMoney |
| 2 | insert five more 25¢ coins | HasMoney | amount 25¢ | amount 150¢ |
| 3 | selectProduct(A1) | HasMoney | amount 150¢, price 125¢ | change 25¢ prepared, state Dispensing |
| 4 | dispense() | Dispensing | selected A1, stock 1 | stock 0, transaction cleared, state Idle |
| 5 | collectChange() | Idle | lastChange 25¢ | customer receives one TWENTY_FIVE coin |
The important ordering is selection before commit: HasMoneyState prepares change first, and only DispensingState decrements inventory.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| insertCoin | O(1) | O(1) | Adds one coin to the transaction list and increments its denomination count in the change bank. |
| selectProduct | O(D) | O(D) | D is number of coin denominations. Product lookup is map-based; preparing change scans denominations and may return a change list. |
| dispense | O(1) | O(1) | Decrements one inventory counter and clears transaction fields. |
| admin refill | O(1) | O(1) | Inventory.addProduct updates product and count maps for one product id. |
| cancel | O(C) | O(C) | C is inserted coins for the active transaction; the refund list copies those coins. |
The interview-grade model is effectively constant time because the number of denominations is tiny. If the product catalog becomes large, product display and search need pagination or indexing, but the transaction state machine remains unchanged.
Extensibility
New denomination or notes
Add a new money type or generalize Coin into a PaymentUnit. Keep values in cents and route change-making through the same policy seam.
Digital payments
Introduce a PaymentStrategy that authorizes and captures externally, while the State flow still decides when selection and dispensing are legal.
Admin operations
Add authenticated refill methods for products and change bank loading. Inventory remains the stock authority; hardware adapters call into it.
Product categories and discounts
Add metadata to Product and inject a pricing or promotion strategy before comparing inserted amount with final price.
Telemetry
Emit events on selection failures, refunds, stock depletion, and successful dispenses without changing state behavior.
Alternative Designs
Single class with enum state
Keep an enum field such as IDLE or HAS_MONEY and use switch statements inside VendingMachine methods.
Tradeoffs
It is shorter for a toy demo, but every new state or transition edits the same large methods and invalid actions become easy to miss.
Explicit ChangeStrategy interface
Extract takeChange into a ChangeStrategy with a greedy implementation, a dynamic-programming implementation, or a provider-specific refund strategy.
Tradeoffs
This is cleaner for production and aligns strongly with Strategy, but it adds another interface that may be unnecessary for a beginner interview unless payments are emphasized.
Static singleton Inventory
Expose Inventory.getInstance so every machine and admin panel uses the same process-wide catalog.
Tradeoffs
It demonstrates Singleton directly, but constructor injection is easier to test and safer when modeling multiple physical machines.
Common Mistakes
- ×
Using boolean flags such as hasMoney and isDispensing instead of explicit State objects.
- ×
Decrementing inventory during selection before payment and change validation have succeeded.
- ×
Forgetting to refund inserted coins when exact change cannot be made.
- ×
Letting OutOfStock discard the customer payment instead of allowing cancel or another selection.
- ×
Using floating-point money values instead of integer cents.
- ×
Hard-coding coin logic throughout every state instead of keeping it inside the machine or a payment strategy seam.
- ×
Making Inventory mutable from the outside by exposing its internal maps.
Follow-up Interview Questions
QHow would you support notes in addition to coins?
Generalize Coin into a MoneyUnit with denomination value, or add a PaymentStrategy that accepts both notes and coins. The state flow does not need to know which instrument was inserted.
QHow do you handle a selected product that is out of stock?
Move to OutOfStockState, preserve inserted payment, and allow either cancel for refund or selecting another stocked product.
QWhy not decrement stock immediately when the customer selects a product?
Selection can still fail because of insufficient funds or inability to make change. Stock should decrement only at the committed dispense step.
QHow would you make the change algorithm robust for arbitrary denominations?
Extract a ChangeStrategy and use dynamic programming or bounded coin search when greedy is not guaranteed to find a valid solution.
QWhat happens if the machine loses power after taking payment?
Production systems persist transaction state and inserted value before moving to dispensing. On restart, reconcile pending transactions by refunding or completing dispense with an audit trail.
Production Considerations
Hardware adapters
Coin acceptors, bill validators, card readers, and dispensers should be adapters around the domain. The core model should not perform device I/O directly.
Durability and reconciliation
Persist inventory, cash-bank balances, and in-flight transactions so the machine can recover after power loss without losing money or stock.
Security
Admin refill and cash collection require authentication, tamper detection, and auditable events.
Operational monitoring
Track stockouts, failed change attempts, refunds, coin-bank levels, and dispenser errors so operators can service machines before customers are affected.
Concurrency
A physical vending machine is usually single-user, but admin refill, telemetry, and remote price updates can race with purchases. Use a transaction lock or repository transaction around commit.
What Interviewers Look For
Did you lead with a State model rather than a pile of conditionals?
Does each invalid action fail in the state where it is invalid?
Is Inventory the single source of truth for product counts?
Do payment and change calculations use integer cents?
Can you explain where Strategy fits for change-making or external payments?
Did you preserve inserted money across recoverable failures and refund on cancellation?
Quiz
0/5 answered
1.Why is the State pattern a strong fit for a vending machine?
2.When should inventory be decremented?
3.What should happen if exact change cannot be produced?
4.How does Inventory relate to the Singleton idea in this design?
5.Where is the best seam for supporting cards, notes, or a different change algorithm?
Practice Variants
Add a ChangeStrategy interface
BeginnerExtract the greedy change code into an interface and add a bounded-search implementation for arbitrary denominations.
Support notes and card payments
IntermediateGeneralize payment input so coins, notes, and card authorization all feed the same transaction flow.
Add remote admin refill and pricing
IntermediateCreate admin operations for refill, product disablement, and price changes, with validation so active purchases remain safe.
Handle hardware failures
AdvancedModel dispenser failure after payment authorization. Decide whether to refund, retry, or mark the slot unavailable.
Flashcards
Cheat Sheet
Entities: VendingMachine, State, IdleState, HasMoneyState, DispensingState, OutOfStockState, Inventory, Product, Coin.
Patterns: State for lifecycle, Singleton-style Inventory as one stock authority, Strategy seam for payment and change.
Flow: insert coin, move Idle to HasMoney, select product, validate stock and amount, prepare change, move to Dispensing, decrement inventory, clear transaction, return to Idle.
Invariants: no dispense without selection, no stock decrement before commit, no accepted sale without exact change, refund returns inserted coins before reset.
Complexity: insertCoin O(1), selectProduct O(D), dispense O(1), cancel O(C), where D is denominations and C is inserted coins.
Extend: add notes or cards through payment strategy, add admin refill around Inventory, add robust change-making behind a strategy interface.
References
- BookDesign Patterns: Elements of Reusable Object-Oriented Software — Gamma, Helm, Johnson, Vlissides
- BookHead First Design Patterns — Freeman & Robson
- DocsRefactoring Guru: State Pattern
- DocsRefactoring Guru: Strategy Pattern