Skip to content
Hari KharelStudy

Step-by-step simulation

coreCommon atAnthropicStripeAmazontrading firmsRead firstMatrices and gridsHeapsQueues and dequesPractise in the Sandbox →

A simulation applies a system’s rules to its state, one step at a time, until a stop condition. There are two loop shapes: clock-driven (advance time by a fixed tick and update everything) and event-driven (keep future events in a min-heap by time and jump straight to the next one). The hard parts are not algorithms but exactness: update from a consistent snapshot (double buffering), break ties with a fixed rule, and define precisely when the loop stops. Cost is O(ticks × work per tick) or O(events × log events).

The idea in plain words

Section titled “The idea in plain words”

Many interview problems don’t hide a clever trick. They describe a little world (a board game, a queue at a bank, a spreading fire, an elevator) and ask what it looks like after some time. The skill is turning the English rules into code that does exactly what they say, in the right order, every time.

Two ways to move time forward:

  • Clock-driven (time-stepped). A loop where every iteration is one tick. Each tick, look at everything and apply the rules. Like a board game where each round every player moves. Easy to write; you pay for every tick, even empty ones.
  • Event-driven (discrete-event). Keep a list of “things that will happen at time t”, ordered by time. Pop the earliest, update the state, and maybe schedule new future events. Time jumps from event to event. Like a calendar: you don’t check it every second, you look at the next appointment.

Three words that come up:

  • State: everything you need to know to compute the next step (grid contents, who’s in line, the clock).
  • Deterministic: the same input always gives the same output. That requires fixed iteration order and fixed tie-breaks, not “whatever order the hash map gives”.
  • Double buffering: compute the next state into a fresh copy while reading only the current one, then swap. Every update sees the same moment in time.

See it

Section titled “See it”

A clock-driven grid. Conway’s Game of Life: each cell lives or dies from its 8 neighbours. Click cells, then step or run. Switch the update rule to in place and step a Blinker: updating cells in the same grid you’re reading lets later cells see a half-finished tick, and the pattern breaks immediately.

A tick loop: compute every cell, then swap boards
click cells, then run
●
●
●
●
●
tick0
alive5
born next2
die next2
● alive, survives● alive, dies next tickempty, born next tick
Each tick reads only the current board and writes a brand-new one, so every cell sees the same moment in time. The order of the scan no longer matters, and the run is fully deterministic.

Clock vs events. One cashier, one line. Each customer is arrival:service. Run both loops on the same input and compare the work: the clock version spends an iteration on every quiet tick between t = 16 and t = 30; the event version jumps over them.

Clock-driven vs event-driven: one cashier, one line
step through
ABCDEFt=0
cashier
idle
line (front first)
(empty)
event heap (next first)
t0 arrive At1 arrive Bt2 arrive Ct12 arrive Dt13 arrive Et30 arrive F
clock0
events handled0
in line0
ticks the clock version needs33
waiting in linebeing servedarrival / current time
Event-driven: schedule every arrival up front in a min-heap keyed by time. The clock never ticks on its own; it jumps to the next event.
1 / 14

When to reach for it

Section titled “When to reach for it”
The problem says… Why simulation fits
“after k rounds / minutes / generations, what does the board look like?” Apply the rule k times. Check whether k is small enough.
“each round, every cell updates from its neighbours” A tick-based cellular automaton with double buffering.
“requests arrive at these times and take this long; when does each finish?” Event-driven: a heap of future events.
“process these commands in order and report the state” A state machine with a command loop; the rules are the code.
“the robot moves, turns, bounces” Position + direction state, one step per instruction.
a long horizon (10⁹ ticks) Don’t tick. Jump with events, or find a cycle and skip ahead.

How it works

Section titled “How it works”

Clock-driven loop

Section titled “Clock-driven loop”
  1. Allocate the next state as a fresh buffer.
  2. Compute each element of next from the current state only.
  3. Apply the rule for that element.
  4. Swap: next becomes current. Repeat until the tick limit or a stop condition (nothing changed, everyone done).
life_step.py
Grid = list[list[int]]




def life_step(grid: Grid) -> Grid:
    """One tick of Conway's Game of Life. Cells outside the grid count as dead."""
    rows, cols = len(grid), len(grid[0]) if grid else 0
    nxt = [[0] * cols for _ in range(rows)]          # 1. write into a NEW buffer
    for r in range(rows):
        for c in range(cols):
            alive = sum(                             # 2. read only the OLD buffer
                grid[r + dr][c + dc]
                for dr in (-1, 0, 1) for dc in (-1, 0, 1)
                if (dr or dc) and 0 <= r + dr < rows and 0 <= c + dc < cols
            )
            # 3. the rule: survive with 2-3 neighbours, be born with exactly 3
            nxt[r][c] = 1 if alive == 3 or (grid[r][c] and alive == 2) else 0
    return nxt                                       # 4. swap: the new buffer is the new state




def run(grid: Grid, ticks: int) -> Grid:
    for _ in range(ticks):                           # a fixed number of ticks: deterministic
        grid = life_step(grid)
    return grid




if __name__ == "__main__":
    blinker = [[0, 0, 0], [1, 1, 1], [0, 0, 0]]
    assert life_step(blinker) == [[0, 1, 0], [0, 1, 0], [0, 1, 0]]
    assert run(blinker, 2) == blinker                # period 2
    block = [[1, 1], [1, 1]]
    assert life_step(block) == block                 # still life
    print("ok")

Event-driven loop

Section titled “Event-driven loop”
  1. Put the initial events in a min-heap keyed by (time, tie-break).
  2. Pop the earliest event and set the clock to its time.
  3. Update the state, and push any follow-up events it causes (a service start schedules a departure).
  4. Stop when the heap is empty or the clock passes the horizon.
single_server.py
import heapq
from collections import deque


ARRIVE, DEPART = 1, 0          # at equal times, departures sort first: a fixed tie-break




def single_server(customers: list[tuple[int, int]]) -> list[int]:
    """customers[i] = (arrival, service). Returns each customer's wait in a FIFO line."""
    events = [(t, ARRIVE, i) for i, (t, _) in enumerate(customers)]
    heapq.heapify(events)                        # 1. future events, earliest first
    line: deque[int] = deque()
    busy = False
    wait = [0] * len(customers)
    while events:
        now, kind, i = heapq.heappop(events)     # 2. jump the clock straight to the next event
        if kind == ARRIVE:
            line.append(i)
        else:
            busy = False
        if not busy and line:                    # 3. update state; schedule follow-up events
            j = line.popleft()
            wait[j] = now - customers[j][0]
            busy = True
            heapq.heappush(events, (now + customers[j][1], DEPART, j))
    return wait                                  # 4. stop when no events remain




if __name__ == "__main__":
    # A busy start, then a gap, then a tie: C departs at 7 exactly when D arrives.
    assert single_server([(0, 3), (1, 2), (2, 2), (7, 1)]) == [0, 2, 3, 0]
    assert single_server([(5, 1), (0, 10)]) == [5, 0]   # input need not be sorted
    assert single_server([]) == []
    print("ok")

What it costs

Section titled “What it costs”
Loop Time Space Good when
Clock-driven, N cells O(T · N) for T ticks O(N), two buffers dense activity, small T, everything changes every tick
Clock-driven, only “active” cells O(T · active) O(N) sparse changes; keep a set of cells that might change
Event-driven with a heap O(E log E) for E events O(pending events) sparse activity, long or continuous time
Cycle detection + skip O(cycle length · N) O(states seen) huge T on a small, repeating state space

The trap is T. A “simulate 10⁹ seconds” prompt is a hint that you must jump, skip, or find a pattern, not tick. Always ask for the bounds on time, not just on input size.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Frontier-only updates. If only cells next to recent changes can change, keep a set of candidate cells instead of rescanning the whole grid every tick.
  • Cycle detection. Hash each state; when one repeats, the system is periodic. Fast-forward with (T − start) mod period.
  • Fixed-point stop. Stop when a tick changes nothing.
  • Multiple event types and priorities. Encode the tie-break order in the heap key: (time, priority, sequence_number). A sequence number also keeps equal events in insertion (FIFO) order.
  • Seeded randomness. If the rules involve chance, pass a seeded RNG so runs are reproducible in tests.
  • Simulated clocks in systems code. Rate limiters, timers and schedulers are tested with an injected fake clock instead of real time. See event-driven design and time handling.

Pitfalls

Section titled “Pitfalls”
  • Updating in place when the rule reads neighbours (see the viz).
  • Unspecified order within a tick. Do arrivals happen before departures at the same time? Does a cell changed this tick affect its neighbours in the same tick? Ask, then encode it in one place.
  • Iterating a hash set or map for “everyone acts in turn”: insertion order is guaranteed for Python dicts and JS Map/Set, but not for .NET HashSet<T>/Dictionary<K,V>. Sort when order matters.
  • Off-by-one in time. Is the start time 0 or 1? Is the answer “the tick when it happened” or “how many ticks elapsed”? Write a 2-step example by hand.
  • Mutating a collection while iterating it. Collect changes, then apply them.
  • Floating-point time. Use integers (milliseconds, ticks) when you can; equal times must compare equal.
  • No stop condition when the state stops changing but the target is never reached. Detect “nothing changed this tick” and return the failure value.

In the interview

Section titled “In the interview”
  • Restate the rules as a numbered list and get agreement on the ambiguous ones: order of operations within a step, simultaneous events, boundaries, what “done” means.
  • Choose the loop out loud: “Activity is sparse and time is long, so I’ll jump between events with a heap.”
  • Separate concerns: a step(state) -> state function, a loop, and a stop condition. It’s easier to test each.
  • Walk one small example by hand before coding, and turn it into your first test.
  • Expected follow-ups: make it faster for huge T, add a new entity type or event, make the order of simultaneous events configurable, or make the simulation pausable and resumable.

Check yourself

Section titled “Check yourself”
Check yourself
pick one
A Game of Life implementation loops over cells in row-major order and writes each new value straight into the same grid. What's wrong?
Check yourself
pick one
200 jobs arrive over a simulated year, measured in milliseconds. Each takes a few seconds. Clock-driven or event-driven?
Check yourself
pick one
Two events are due at exactly t = 50: a departure and an arrival. Why does it matter which goes first?

Practice on your own

Section titled “Practice on your own”

These are classic textbook exercises, not gym questions:

  • Rotate a matrix 90° in place, layer by layer.
  • Simulate a robot on an infinite grid that follows L, R, G commands and decide whether it stays in a bounded circle.
  • Simulate falling stones in a grid: each stone falls until it rests on an obstacle or the floor.
  • Game of Life on an unbounded board, storing only live cells in a set.
  • A bank with k tellers: compute the average wait for a list of arrivals and service times.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Event-driven designEvent loops, timers and injected clocks in real systems.
Breadth-first searchLayer-by-layer exploration, the other way to model rounds.
HeapsThe future-event list.
State machinesExplicit states and transitions for each entity.