Skip to content
Hari KharelStudy

State machines

coreCommon atStripeAnthropicOpenAIAmazonRead firstHash mapsClass design and invariantsPractise in the Sandbox →

A state machine says an object is always in exactly one of a few named states, and only certain events move it between them. Write the legal moves down as a transition table (state, event) → next state. Anything missing from the table is illegal, so you reject it in one place instead of sprinkling if checks everywhere. Each event costs one O(1) lookup.

The idea in plain words

Section titled “The idea in plain words”

Think of a parcel. It is created, picked up, in transit, out for delivery, and finally delivered. You cannot deliver a parcel nobody has picked up, and you cannot cancel one that is already on a truck. Those rules are the whole point of the object.

The naive way to code that is a handful of booleans: is_picked_up, is_delivered, is_canceled. Three booleans allow eight combinations, and most of them are nonsense (“delivered and canceled”). Every method has to guard against the nonsense, and one forgotten guard is a bug.

A state machine replaces the booleans with one field that holds one named state, plus a table of the moves that are allowed:

  • State: where the object is in its life. Exactly one at a time.
  • Event: something that happens to it (pick_up, cancel). Your public methods usually are the events.
  • Transition: a row in the table, “in state S, event E moves you to state T”.
  • Guard: an extra condition on a transition (“only if attempts < 2”).
  • Terminal state: a state with no outgoing rows. Once there, every event is rejected.

The design win is that “is this allowed?” becomes a lookup, not a judgment call buried in each method.

See it

Section titled “See it”

Pick a machine, then click events. Highlighted arrows are legal from the current state. Click an illegal event anyway and watch it get rejected with the state unchanged. On the shipment, fire miss a few times: the same event goes to a different state once the guard flips.

Fire events at a state machine
sandbox
pick_upcanceldepartloadmiss [attempts < 2]miss [attempts ≥ 2]delivercreatedpicked_upin_transitout_for_deliverydeliveredreturnedcanceledstart
statecreated
attempts0
legal_events2 of 6
A lifecycle with terminal states, an event that is only legal early (cancel), and a guarded event (miss) whose target depends on a counter.
current statelegal from hereterminal (reached)not legal now
Click an event. Illegal ones are allowed to be clicked: watch how they are rejected.

When to reach for it

Section titled “When to reach for it”
The problem says… Why a state machine fits
“a request / order / job / charge moves through statuses” Statuses are states. The prompt’s list of statuses is your enum.
“return False (or an error) if it isn’t pending / already finished” That’s an illegal transition. One table lookup answers it.
“once X happens, it can never Y” X leads to a terminal state, or to a state with no Y row.
a lifecycle diagram with arrows in the prompt The diagram is the transition table. Copy it in literally.
parsing input character by character A tokenizer is a machine whose events are character classes.
later level: “add a new status” A table grows by rows. Scattered if chains grow by bugs.

How it works

Section titled “How it works”
  1. List the states as an enum (or a string union). Include terminal states. Pick a start state.
  2. Write the transition table as a map from (state, event) to the next state. If the prompt has a diagram, copy every arrow.
  3. Fire an event by looking up (current, event). If there’s no row, or its guard fails, reject before mutating anything: return False, return an error value, or throw, matching the API.
  4. Change state in exactly one place, then run the transition’s side effects (timestamps, counters, history).
print_job.py
from enum import Enum




class Job(Enum):
    QUEUED = "queued"
    PRINTING = "printing"
    PAUSED = "paused"
    DONE = "done"
    CANCELED = "canceled"




# 1. The whole lifecycle is one table: (state, event) -> next state.
#    Anything not in the table is illegal by construction.
TRANSITIONS: dict[tuple[Job, str], Job] = {
    (Job.QUEUED, "start"): Job.PRINTING,
    (Job.QUEUED, "cancel"): Job.CANCELED,
    (Job.PRINTING, "pause"): Job.PAUSED,
    (Job.PRINTING, "finish"): Job.DONE,
    (Job.PAUSED, "resume"): Job.PRINTING,
    (Job.PAUSED, "cancel"): Job.CANCELED,
}




class IllegalTransition(Exception):
    pass




class PrintJob:
    def __init__(self) -> None:
        self.state = Job.QUEUED  # 2. one field holds the state; no flag soup
        self.history: list[Job] = [self.state]


    def fire(self, event: str) -> Job:
        nxt = TRANSITIONS.get((self.state, event))
        if nxt is None:  # 3. reject before mutating anything
            raise IllegalTransition(f"{event!r} not allowed in {self.state.value}")
        self.state = nxt  # 4. the only place state ever changes
        self.history.append(nxt)
        return nxt




if __name__ == "__main__":
    job = PrintJob()
    for ev in ["start", "pause", "resume", "finish"]:
        job.fire(ev)
    assert job.state is Job.DONE
    try:
        job.fire("cancel")  # done is terminal: no row starts from it
        raise AssertionError("expected IllegalTransition")
    except IllegalTransition:
        pass
    assert job.state is Job.DONE and len(job.history) == 5
    print("ok")

Because the table is plain data, you also get a second use for free: replay. Folding a log of events through the table rebuilds the state at any point in time. Replaying a prefix of the log gives the state “as of” that event, which is the core of event sourcing.

replay.py
# Rebuild a state by folding an event log through a transition table.
# Same table shape as before; here the "machine" is just a pure function.
TABLE: dict[tuple[str, str], str] = {
    ("draft", "submit"): "review",
    ("review", "approve"): "published",
    ("review", "reject"): "draft",
    ("published", "archive"): "archived",
}




def replay(events: list[str], start: str = "draft") -> tuple[str, list[int]]:
    """Return the final state and the indexes of events that were illegal."""
    state, rejected = start, []
    for i, ev in enumerate(events):
        nxt = TABLE.get((state, ev))  # 1. look up (state, event)
        if nxt is None:
            rejected.append(i)  # 2. record and skip: the state does not move
            continue
        state = nxt  # 3. legal: advance
    return state, rejected




if __name__ == "__main__":
    log = ["submit", "reject", "submit", "approve", "approve", "archive"]
    assert replay(log) == ("archived", [4])  # second approve: already published
    assert replay([]) == ("draft", [])
    assert replay(["approve"]) == ("draft", [0])  # cannot approve a draft
    # Replaying a prefix gives the state at that point in history.
    assert replay(log[:2]) == ("draft", [])
    print("ok")

What it costs

Section titled “What it costs”
Time per event Space Adding a state or event
Boolean flags + if chains O(1), but every method re-checks O(1) edit every method that cares
switch / match on state inside each method O(1) O(1) edit each method’s switch
Transition table (map) O(1) lookup O(rows) add rows
State pattern (one class per state) O(1) virtual call O(states) objects add a class

The table form wins in interviews for a practical reason: you can read the whole lifecycle in six lines and check it against the prompt’s diagram. A switch spreads the same information across every method.

The State pattern (from the Gang of Four book) gives each state its own class with a method per event. It shines when each state has a lot of distinct behavior, not just different legal moves. For a status field with a few rules, it’s usually more code than the problem needs.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Guarded transitions. The same (state, event) can lead to different states depending on data: a retry goes back to the queue until the attempt limit, then to a dead state. Store a list of candidate rows and take the first whose guard passes.
  • Self-transitions. An event that is legal but doesn’t change the state (a heartbeat, a coin into an unlocked turnstile). Decide whether it still runs side effects, and say so.
  • Time-driven transitions. “A pending request expires after 48 hours.” No one fires an expire event; you compute it when the object is next touched. See TTL and expiry.
  • Hierarchical states (statecharts). “Any active state can be canceled.” Instead of a cancel row per state, group states under a parent with one shared row. David Harel’s statecharts formalized this.
  • Tokenizers. Character-by-character parsing is a machine whose states are “in a number”, “after the sign”, “in whitespace”. Same table idea, events are character classes.
  • Event sourcing. Store the events, not the state. The state is replay(events). Great for audit history and point-in-time queries.

Pitfalls

Section titled “Pitfalls”
  • Mutating before validating. Update the amount, then discover the transition is illegal, and the object is now half-changed. Check first, mutate second.
  • Forgetting terminal states. If done has no rows, every event on a done object is rejected. If you implemented transitions with if state != canceled, you probably forgot done.
  • Two sources of truth. A status field and a refunded boolean that can disagree. Derive one from the other, or drop one.
  • Silent no-ops. An illegal event that returns nothing and changes nothing looks like success to the caller. Make rejection visible: False, an error string, or an exception, whatever the API specifies.
  • Spec drift in later levels. A new level adds a status (“disputed”). Re-read every existing row: does refund still apply to it?

In the interview

Section titled “In the interview”
  • When the prompt lists statuses, draw the diagram first, even as ASCII in a comment. Say: “Let me write the legal transitions as a table so I can check them against your description.”
  • Ask about the edges of the diagram: “Can a canceled order be reopened? What should happen if capture is called twice: error or no-op?” Idempotent repeats are a classic follow-up.
  • State the invariant: “status is always one of these five values, and it only changes inside fire.”
  • Expect follow-ups: add a state, add a guard based on time, keep a history of transitions, or answer “what was the status at time T?” (replay or versioning).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
An object has three booleans: is_started, is_paused, is_finished. How many combinations exist, and how many are probably meaningful?
Check yourself
pick one
A refund comes in for a charge. Your code subtracts the amount from the balance, then checks the transition table and finds the charge is canceled. What went wrong?
Check yourself
pick one
A new level says 'any non-terminal order can be put on hold, and resumes to the state it was in'. What's the cleanest change?

Practice on your own

Section titled “Practice on your own”

These are classic exercises, not gym questions:

  • A traffic light with a pedestrian button that shortens the green phase, but never below a minimum.
  • A vending machine: insert coins, select an item, get change, refund on cancel. Which events are legal with zero credit?
  • A tokenizer that splits x1 = 42 + y into identifiers, numbers and operators using a character-class table.
  • A TCP-style connection: closed → listen → established → closing → closed, rejecting send unless established.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Class design and invariantsThe state field is your strongest invariant.
TTL and expiryTransitions that fire because time passed.
ParsingTokenizers are state machines over characters.
IdempotencyWhat a repeated event should do.