Before you start

Welcome to LLD problems. You've done 25 lessons of foundation work. Now you use them.

Every lesson in this module has ONE shape:

1. Read the requirements.
2. Ask the questions a strong interviewer would want to hear.
3. Decide on entities, patterns, and trade-offs.
4. WRITE THAT DOWN in design.md.
5. Implement in main.py.

The tests grade BOTH. Design without implementation fails. Implementation without design also fails.

Why we grade design.md too

Every design interview asks two things:

1. Can you build it? (implementation)
2. Can you defend it? (justification)

Half of candidates fail on #2 — they built something that works but can't explain why they made the choices they made. "I used Factory because... um... it seemed right?" is a common interview failure.

The design.md forces you to say the reasoning out loud BEFORE the interviewer asks. That's not busy-work; that's the interview rehearsal.

The interview flow this simulates

In a real 45-minute design interview:

• Minutes 0-5 — read the problem, ask clarifying questions
• Minutes 5-15 — find the classes, sketch them, name the patterns you plan to use
• Minutes 15-40 — implement
• Minutes 40-45 — walk the interviewer through your design and defend the choices

Modules 1-3 taught the ingredients. Module 4 teaches the flow.

Reading the requirements

Read them TWICE. First pass: understand what the machine does. Second pass: mark things up. Look for:

• State transitions. "In idle, it accepts coins. When dispensing, all actions return 'busy'." → State pattern signal.
• Swappable behavior. "New denominations are added over time." → Registry / dispatch signal.
• Cross-cutting rules. "Every successful dispense must decrement stock." → An invariant to enforce in ONE place.
• Growth axes. "Later we'll add UPI payments." → Design for extension NOW, not later.

Write those observations down BEFORE picking patterns. The patterns fall out of the observations.

How to write a good design.md

Don't try to write it top-to-bottom in one pass. Iterate:

1. First pass, 3 minutes. Skeleton — one line per section with your gut answer.
2. Second pass, 5 minutes. Fill in why. For patterns, ask yourself the module-3 questions ("is this the family rule?" for Abstract Factory, "does state transition?" for State, etc.).
3. Third pass, after implementing. Add anything you learned while coding. Your first-pass choices may have shifted.

The tests check:

• Every section has real content (60+ chars beyond the stub).
• No placeholder strings (TODO, YOUR ANSWER HERE, etc.) survive.
• The Patterns section mentions at least one module-1-3 pattern OR explicitly justifies plain classes.

Meeting all three is a low bar for interview-quality design justification.

For this specific problem — hints without spoiling

The vending machine has signals for at least ONE behavioral pattern (think: what changes over time?) and one structural or creational pattern (think: what do you build based on data?).

Don't reach for patterns you don't need. If a plain class does the job — say so and defend that. Over-engineering is also a design failure.

What the AI Code Review adds

The grader checks structure. It can't tell whether your Patterns section's REASONING is good — only that reasoning exists. That's what the "Ask Claude for a code review" button after grading is for. Claude reads your design.md AND main.py and comments on the actual quality of your choices.

Use it. That feedback loop is worth more than three more lessons of drill.

Structure of the whole module

12 problems, ordered roughly by difficulty:

1. Vending Machine (this lesson)
2. Parking Lot
3. Tic-Tac-Toe
4. Snake and Ladder
5. Elevator
6. Splitwise
7. Movie Booking
8. LRU Cache
9. Rate Limiter
10. File System
11. Chess
12. Ride Matching

Same template throughout: design.md + main.py, both graded.

Welcome to the LLD problems module. Every lesson here has the same shape:

1. A problem statement (requirements only, no design hints)
2. Questions to ask about the requirements (what a strong candidate asks before coding)
3. Design goals — what makes this design "good"
4. Two files to submit:
   • design.md — explain your entities, patterns, trade-offs
   • main.py — the implementation
5. Both are graded.

In modules 1-3 we told you which pattern to use. Not anymore. Here, YOU decide. And you have to explain why — because in an interview, choosing the pattern is only half the answer. Defending the choice is the other half.

The problem

Build a vending machine.

Products:

• Each product has a name, price (int, in ₹), and initial stock.
• Products are added at initialization time.

Money:

• Users insert coins in denominations of ₹1, ₹5, ₹10, ₹20, ₹50. The machine tracks the CURRENT BALANCE inserted this transaction.
• A user can insert multiple coins before selecting.
• Denominations outside the allowed set are rejected without adding to balance.

Selection:

• User selects a product by name.
• If balance >= price AND stock > 0: dispense the product, return change (balance - price), decrement stock, reset balance to 0.
• If balance < price: reject (return an "insufficient funds" marker), keep the balance, do NOT dispense.
• If stock == 0: reject (return "out of stock"), keep the balance, do NOT dispense.
• If product doesn't exist: reject (return "unknown product"), keep the balance.

Cancel:

• User can cancel at any time. Returns the current balance, resets to 0.

Refill (admin action):

• Admin can add stock to any product by name.
• Adding stock for an unknown product raises ValueError.

Reject if the machine is in the middle of a dispense — actions during dispense return "busy" and no state changes happen.

Questions to ask about the requirements

These are the questions you'd ask in an interview. We've picked the answers for you so the tests have fixed results:

1. Change-making policy? — Return balance minus price as one lump. Don't worry about coin decomposition for MVP.
2. What if two users interact concurrently? — Single- user for MVP. No threading concerns.
3. Should coins be validated on insert? — Yes. Rejected denominations don't count.
4. Should the machine remember state across a "power cycle"? — No persistence. State is in-memory only.
5. Can prices change? — Not for MVP. Prices are fixed at initialization.

Design goals

Your design should be:

• Easy to extend. Adding a new denomination shouldn't mean rewriting every method. Adding a new payment type (like UPI in v2) should be a manageable change.
• Clean state management. The three phases (idle, has-money, dispensing) should be first-class in your code, not scattered boolean flags.
• Rules that hold. Stock never goes negative. Balance never goes negative. Selling a product ALWAYS decrements the stock exactly once.

Your task

You'll submit TWO files. Both are graded.

1. design.md — explain your design

The file lives in your starter dir with a template. Fill in each section with real content. If you leave sections empty or leave the placeholder text in place, the grader will reject your submission.

Required sections (exact header text):

## Entities
## Patterns
## Trade-offs
## Invariants

• Entities — list every class you created and its responsibility (one line each). Show you thought about what belongs where.
• Patterns — for each design pattern you used (from modules 1-3), say:
  • Which pattern
  • Which requirement made it right
  • Why NOT some other option that seems reasonable
• Trade-offs — at least one real choice you made (e.g., "I chose to store balance as int, not float, because money in ₹ is integer and I avoid rounding errors").
• Invariants — the rules your design enforces at all times (stock >= 0, balance >= 0, etc.), and HOW your code enforces each.

2. main.py — the implementation

Public API tests will assume:

from main import VendingMachine, Product

vm = VendingMachine([
    Product(name="cola", price=25, stock=3),
    Product(name="chips", price=15, stock=5),
])

vm.insert_coin(10)             # returns None or a status
vm.insert_coin(20)             # balance is now 30
result = vm.select("cola")     # returns dict with keys:
                               #   status: "dispensed"|"insufficient"|
                               #           "out_of_stock"|"unknown"|"busy"
                               #   product: <name> or None
                               #   change: <int> or 0
change = vm.cancel()           # returns balance, resets to 0
vm.refill("cola", 5)           # admin only, adds stock

Refer to the tests for the exact shapes expected.

Click Submit to run the tests. Green = both design and implementation passed.

What we're NOT giving you

We deliberately don't tell you which patterns to use. Read the requirements, ask yourself the recognition questions from modules 1-3, decide, and JUSTIFY in design.md.

Hint: the requirements have signals for at least ONE behavioral pattern and ONE structural pattern from module 3. Which ones? That's your call.