State machine

What it is

A state machine problem asks you to model something that moves between a small, fixed set of situations over time, where what happens next depends only on which situation you're currently in — never on the full history that got you there. In a coding/DP context, this means defining a handful of named states per step (holding a share versus not, which color the previous item used) and a recurrence for how each state's best value updates from the states it can legally follow. In a system-design/LLD context, it means the same idea made literal: named state classes, each exposing only the operations legal in that state, with everything else rejected by default. Both are the same discipline — enumerate the states, then enumerate exactly which transitions between them are allowed.

When it applies

• A DP problem has a rule that couples one step to the next (a cooldown after selling, no two adjacent picks sharing a value) where a single running best isn't enough because "what you could do next" depends on more than just "the best total so far" — it depends on which situation produced that total.
• You're modeling an object whose legal operations change depending on what has already happened to it (a machine that has money inserted versus one that doesn't, a connection that's open versus closing) and illegal operations in the wrong situation must be rejected, not silently ignored.
• It does not apply when a single scalar running value fully captures everything relevant about the past — that's a plain 1D DP, not a state machine, and adding named states where a single number would do just adds unnecessary bookkeeping.
• It also isn't the right frame for modeling something where almost every operation is legal in almost every situation — state machines earn their keep specifically when the set of legal next moves varies meaningfully by situation.

Tells in the problem

• "After selling you must wait one day before buying again" or any rule that makes an action's legality depend on how recently a different action happened — a state machine where "just did X" is its own state, distinct from "free to do X."
• "No two adjacent items may share a property" with more than a binary yes/no distinction (e.g. three colors, not two) — one state per possible value of the constrained property, with a transition that excludes matching the previous one.
• "Design a machine/object with buttons or inputs; entering money, selecting an item, canceling" — a literal state-pattern or transition-table design question, where the actual grading criterion is whether illegal sequences are rejected cleanly.
• A prompt that explicitly asks you to draw states and transitions before writing code, or asks "why can't these two states be merged" — a direct signal that the interviewer wants the state enumeration reasoned about, not just the final code.
• "What happens if a new kind of state needs to be added later without touching existing code" — asking whether your design (state pattern, or a dict[(state, event)] transition table) isolates each state's behavior instead of scattering if branches through every method.

The classic mistake

The recurring DP-side mistake is collapsing two states that look similar into one and missing the specific transition that distinguishes them — for example, treating "sold today" and "free to buy" as the same "not holding a share" situation, when the entire cooldown rule lives in the one-day delay between them. The fix is to ask, for every pair of states that seem mergeable, whether there's an edge allowed from one but not the other; if such an edge exists, they must stay separate. The recurring LLD-side mistake is the opposite failure mode: building one state class or enum branch per possible input rather than per situation, so the code ends up with the same if chain repeated in every method instead of each state class simply omitting (or rejecting by default) the operations that don't apply to it.

Questions to start with

• Paint House — three states (the color of the current house) with the simplest possible transition rule: exclude whatever the previous state was.
• Best Time to Buy and Sell Stock with Cooldown — the case where two states that look mergeable (both "not holding") must stay separate because of a one-day-delayed transition.
• Vending Machine — the same discipline applied to real code: named state classes, illegal operations rejected by default, and an explicit discussion of when a state pattern earns its complexity over a plain enum.