Low-level design · Games and state machines
Vending machine with object-oriented design
- Reported once
- Internship (year not stated)
- State
- Strategy
- 1 source
One candidate write-up. Treat it as a single data point.
Design a vending machine using object-oriented design. The report says only that various parameters were given and does not list them, so this answer fixes its own scope: products in coded slots with a price and a quantity, cash in whole units, change from a limited float, and a separate state for each situation the machine can be in.
Restated in our own words, not a quote from Groww or any page. The answer below is written for this site.
Clarify first
Pin the scope down before you name a single class.
The report gives no parameters, so asking is the whole job. Questions to ask first:
- What does the machine accept: coins only, notes, cards? Assume cash in whole units (1, 2, 5 and 10), and keep payment behind one insert call so other methods can be added.
- Does the customer pay first or choose first? Assume pay first, then select.
- Where does change come from? Assume a limited float of coins in the machine, plus the coins the customer just inserted.
- What if change cannot be made, or the product jams? Assume that when change cannot be made nothing is taken and the customer keeps their credit, can refund or insert more. When the product jams the inserted coins are returned at once.
- Who restocks? Assume an operator can restock and take the machine out of service.
Out of scope: card payment, prices that change, network reporting and concurrent customers.
Entities and relationships
Who owns what, and who talks to whom.
- VendingMachine is the context. It owns the slots, the coin float, the coins inserted in the current session, the injected change strategy and dispenser, and a reference to the current state.
- State objects (IdleState, HasCreditState, OutOfServiceState) each implement
insert,selectandrefund. They decide what the action means and which state comes next. - Slot is a code with a product name, a price and a quantity.
- ChangeStrategy is an interface with
make(amount, stock).GreedyChangeandBacktrackingChangeimplement it. - Dispenser is the hardware collaborator with
release(code), which can fail. A scripted fake stands in for it in tests. - Coin counts are plain maps from a denomination to a count. Money is whole numbers, never fractions.
The design
The class map, the main flow and the patterns that earn their place.
- The customer inserts money or selects a slot code.
- The machine forwards the call to whichever state object is current.
- In the credit state, the change strategy is asked for coins worth credit minus price.
- The dispenser is asked to release the product, and only then is anything committed.
Open on the whiteboardAll 3 diagrams on one tidy board, with a step-by-step walkthrough.
State pattern. The same call means different things depending on the situation: select before paying is an error, after paying it may sell, and out of service it is refused. Writing this as one method full of if (state === ...) branches grows with every new state. Instead the machine holds a current state object and forwards insert, select and refund to it. Each state class holds only its own rules and moves the machine with setState. Adding a state, such as a maintenance mode, adds a class rather than editing every method.
Selecting a product in HasCreditState runs checks in a fixed order, and nothing changes until all pass:
- The slot code exists, the slot is not sold out, and the credit covers the price.
- Pool the machine's float with the coins just inserted, because the customer's own coins can come back as change. Ask the change strategy for coins worth
credit - price. No answer means "cannot make change". - Ask the dispenser to release the product. If that fails, return the inserted coins and stay consistent.
- Only now commit: replace the float with the pool minus the change, empty the inserted coins, decrement the quantity and move to idle.
Validating before mutating gives the important property that every failure path leaves stock, float and credit exactly as they were, or refunds the exact coins. A strategy's answer is trusted only if it adds up to the amount and fits inside the pool, so a faulty strategy reads as "cannot make change" instead of corrupting the float. resume only leaves the out-of-service state, so calling it mid-session cannot strand a customer's credit.
Strategy for change. Greedy takes the biggest coin first. It is simple, and optimal for common coin systems with unlimited coins, but with a limited float it can fail when an answer exists: to return 6 from one 5 and three 2s, greedy takes the 5 and is stuck. BacktrackingChange tries the largest use of each denomination first and steps back when the rest cannot be paid, so it finds the 2 + 2 + 2 answer. Its search depth is the number of denominations, which is small, though the worst case still grows with large amounts and big floats.
Refund returns exactly the inserted coins and never touches the float. Concurrency is not modelled because a physical machine serves one session; a software kiosk would guard the machine with one lock.
The code
Runnable JavaScript, with the checks it passes.
const DENOMINATIONS = [10, 5, 2, 1];
function fail(reason) {
return { ok: false, reason };
}
function total(counts) {
return Object.keys(counts).reduce((sum, value) => sum + Number(value) * counts[value], 0);
}
function merge(a, b) {
const out = { ...a };
Object.keys(b).forEach((value) => {
out[value] = (out[value] || 0) + b[value];
});
return out;
}
function subtract(a, b) {
const out = { ...a };
Object.keys(b).forEach((value) => {
out[value] -= b[value];
});
return out;
}
function valuesDescending(stock) {
return Object.keys(stock)
.map(Number)
.sort((x, y) => y - x);
}
class GreedyChange {
make(amount, stock) {
const out = {};
let left = amount;
for (const value of valuesDescending(stock)) {
const use = Math.min(Math.floor(left / value), stock[value]);
if (use > 0) out[value] = use;
left -= use * value;
}
return left === 0 ? out : null;
}
}
class BacktrackingChange {
make(amount, stock) {
const values = valuesDescending(stock);
const out = {};
const search = (index, left) => {
if (left === 0) return true;
if (index === values.length) return false;
const value = values[index];
for (let use = Math.min(Math.floor(left / value), stock[value]); use >= 0; use -= 1) {
if (use > 0) out[value] = use;
else delete out[value];
if (search(index + 1, left - use * value)) return true;
}
return false;
};
return search(0, amount) ? out : null;
}
}
class ScriptedDispenser {
constructor(outcomes) {
this.outcomes = outcomes.slice();
}
release() {
return this.outcomes.length > 0 ? this.outcomes.shift() : true;
}
}
class IdleState {
constructor(machine) {
this.machine = machine;
this.name = "idle";
}
insert(value) {
this.machine.inserted = { [value]: 1 };
this.machine.setState("credit");
return { ok: true, credit: value };
}
select() {
return fail("insert money first");
}
refund() {
return { ok: true, returned: {} };
}
}
class HasCreditState {
constructor(machine) {
this.machine = machine;
this.name = "credit";
}
insert(value) {
this.machine.inserted = merge(this.machine.inserted, { [value]: 1 });
return { ok: true, credit: total(this.machine.inserted) };
}
select(code) {
const machine = this.machine;
const slot = machine.slots.get(code);
if (!slot) return fail("unknown slot");
if (slot.quantity === 0) return fail("sold out");
const credit = total(machine.inserted);
if (credit < slot.price) return fail("insufficient credit");
const pool = merge(machine.float, machine.inserted);
const change = machine.changeStrategy.make(credit - slot.price, pool);
const fits = change && total(change) === credit - slot.price && Object.keys(change).every((v) => change[v] <= pool[v]);
if (!fits) return fail("cannot make change");
if (!machine.dispenser.release(code)) return { ...fail("dispense failed"), refund: this.refund().returned };
machine.float = subtract(pool, change);
machine.inserted = {};
slot.quantity -= 1;
machine.setState("idle");
return { ok: true, product: slot.name, change };
}
refund() {
const returned = this.machine.inserted;
this.machine.inserted = {};
this.machine.setState("idle");
return { ok: true, returned };
}
}
class OutOfServiceState {
constructor(machine) {
this.machine = machine;
this.name = "outOfService";
}
insert() {
return fail("out of service");
}
select() {
return fail("out of service");
}
refund() {
return { ok: true, returned: {} };
}
}
class VendingMachine {
constructor({ slots, coins, changeStrategy, dispenser }) {
for (const [code, slot] of Object.entries(slots)) {
if (!Number.isInteger(slot.price) || slot.price < 1) throw new Error("price of " + code + " must be a positive integer");
if (!Number.isInteger(slot.quantity) || slot.quantity < 0) throw new Error("quantity of " + code + " must be 0 or more");
}
this.slots = new Map(Object.entries(slots).map(([code, slot]) => [code, { ...slot }]));
this.float = { ...coins };
this.inserted = {};
this.changeStrategy = changeStrategy;
this.dispenser = dispenser;
this.states = {
idle: new IdleState(this),
credit: new HasCreditState(this),
outOfService: new OutOfServiceState(this),
};
this.state = this.states.idle;
}
setState(name) {
this.state = this.states[name];
}
insert(value) {
return DENOMINATIONS.includes(value) ? this.state.insert(value) : fail("coin not accepted");
}
select(code) {
return this.state.select(code);
}
refund() {
return this.state.refund();
}
restock(code, quantity) {
const slot = this.slots.get(code);
if (!slot) throw new Error("unknown slot " + code);
if (!Number.isInteger(quantity) || quantity < 1) throw new Error("quantity must be a positive integer");
slot.quantity += quantity;
}
takeOutOfService() {
const result = this.refund();
this.setState("outOfService");
return result;
}
resume() {
if (this.state.name === "outOfService") this.setState("idle");
}
}
Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Extend it
The change requests an interviewer throws next.
- How would you add card or UPI payment next to cash so every method goes through the same selection flow?
- How would you return the credit automatically if the customer walks away, and how would you test it without sleeping?
- How would you let the customer choose a product before paying, and which state would that add?
- How do you survive a power failure in the middle of a sale without losing or returning money twice?
- How would an operator refill slots and collect cash without breaking a customer's session in progress?
Where candidates slip
The mistakes this problem punishes.
This problem punishes these slips:
- One large class with nested conditions on a status string instead of State objects, which is what the question is testing.
- Mutating stock or the coin float before the dispenser has succeeded, so a jam loses the sale and the money.
- Making change only from the machine's float and forgetting the customer's own coins, or the reverse and spending coins that are not there.
- Using greedy change and not noticing it fails with a limited float.
- Storing money as floating-point numbers.
- Swallowing the customer's money when change is impossible, instead of keeping credit and offering a refund.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.