Simulation

A simulation problem asks you to carry out a described process step by step: move a robot, evolve a grid, run a queue of customers, format text. There is usually no clever insight; the difficulty is getting every rule, boundary and update order exactly right under time pressure. These problems are especially common in online assessments, where long statements test careful implementation.

Intuition

Treat the statement as a specification and translate it into a small state machine:

1. State: what fully describes the world at one moment (position and direction, the grid, a queue, the clock).
2. Step: a pure rule that maps one state to the next.
3. Stop condition: when to halt and what to report.

Most bugs come from mixing these up, for example reading cells you have already overwritten in the current step, or checking the stop condition one step too late. Plan the steps on paper first, put repeated concepts into helper functions, and convert every quantity into one unit as soon as you read it (times into minutes, dates into day numbers, coordinates into 0-based indices).

When to use it in interviews / OAs

• The statement describes a process with explicit rules: "each second...", "repeat until...", "the robot turns right when...".
• Grids with movement or rotation: spiral traversal, rotating a matrix, snake games, robots following instructions.
• Cellular automata: Game of Life, cells that depend on their neighbors.
• Queues and turns: ticket lines, round-robin, card games, senate voting.
• Many OA "implementation" tasks: text formatting, calendars, bank transactions, inventory or parking systems.
• When the number of steps is huge (10^9), the problem is still simulation, but you must find a closed form or a cycle instead of running every step.

Template

Direction vectors on a grid

Keep the four directions in a list ordered clockwise, so turning right is d = (d + 1) % 4. Spiral order walks straight until the next cell is outside the grid or already visited, then turns:

def spiral_order(matrix: list[list[int]]) -> list[int]:
    if not matrix or not matrix[0]:
        return []
    rows, cols = len(matrix), len(matrix[0])
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up (clockwise)
    seen = [[False] * cols for _ in range(rows)]
    r = c = d = 0
    out = []
    for _ in range(rows * cols):
        out.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dirs[d][0], c + dirs[d][1]
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4  # blocked: turn clockwise
            nr, nc = r + dirs[d][0], c + dirs[d][1]
        r, c = nr, nc
    return out

Updating every cell "at the same time"

In Game of Life every cell's next value depends on the current values of its neighbors. Writing new values directly would corrupt neighbors that have not been processed yet. Either build a new grid, or encode both generations in one integer: bit 0 holds the current state and bit 1 the next state. A final pass shifts the next state into place:

def game_of_life(board: list[list[int]]) -> None:
    """Advance one generation in place."""
    rows, cols = len(board), len(board[0])
    for r in range(rows):
        for c in range(cols):
            live = 0
            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:
                        live += board[r + dr][c + dc] & 1  # read the current bit only
            if live == 3 or (live == 2 and board[r][c] & 1):
                board[r][c] |= 2  # mark: alive in the next generation
    for r in range(rows):
        for c in range(cols):
            board[r][c] >>= 1

Simulate first, then look for a formula

A worm at the bottom of a well of depth n climbs u inches, then slides d inches while resting, and repeats. How many climbs until it reaches the top? The direct simulation is obviously correct:

def climbs_simulated(n: int, u: int, d: int) -> int:
    height, climbs = 0, 0
    while True:
        height += u
        climbs += 1
        if height >= n:  # reaching the top exactly also counts
            return climbs
        height -= d  # slides back while resting


def climbs_formula(n: int, u: int, d: int) -> int:
    """Same answer in O(1). Assumes u >= n or u > d, otherwise the worm never escapes."""
    if u >= n:
        return 1
    # after k climbs the worm is at k*u - (k-1)*d, which must be >= n
    return 1 + -(-(n - u) // (u - d))  # ceiling division

If n can be 10^18, the loop is too slow and the formula is required. Writing the simulation first and checking the formula against it is a safe way to get there.

Fast-forwarding with cycle detection

When a deterministic process has few possible states but you must run it n = 10^9 times, it has to repeat. Record the step at which each state first appeared; at the first repeat you know the cycle start and length and can jump straight to the answer:

def state_after(start, step, n: int):
    """Apply `step` n times to `start`. States must be hashable (use tuples, not lists)."""
    seen = {}      # state -> first step index where it appeared
    history = []   # history[i] = state after i steps
    state = start
    for i in range(n):
        if state in seen:
            first = seen[state]
            cycle = i - first
            return history[first + (n - first) % cycle]
        seen[state] = i
        history.append(state)
        state = step(state)
    return state

Normalize units immediately

def to_minutes(hhmm: str) -> int:
    hours, minutes = map(int, hhmm.split(":"))
    return hours * 60 + minutes

After this, time differences, sorting and wrap-around ((b - a) % 1440) are plain integer arithmetic.

Complexity

Simulation costs (number of steps) × (cost per step). Check it against the constraints before you write anything:

• spiral_order and game_of_life: O(rows * cols) time; the in-place encoding needs O(1) extra space.
• climbs_simulated: O(n / (u - d)) time; climbs_formula: O(1).
• state_after: O(min(n, S)) steps, where S is the number of distinct states, plus O(S) memory for the history.

Common pitfalls

• Overwriting state you still need. Use a copy, double buffering, or a bit encoding when all cells update simultaneously.
• Stop condition off by one. Is it >= or >? Is the check made before or after the move? Trace the smallest example by hand.
• Boundary checks. Test 0 <= r < rows before indexing, and remember that Python's negative indices fail silently instead of raising an error.
• Aliased rows. [[0] * cols] * rows creates rows that share one list. Use a list comprehension.
• Too many steps. If the step count is up to 10^9, look for a closed form, a cycle, or a way to skip idle time (jump the clock to the next event).
• Floating point for money or time. Store cents and minutes as integers.
• Tie-breaking rules buried in the statement. Re-read the statement for "if several...", "in case of a tie..." before submitting.

Interview variations

• Spiral and rotation: spiral order, filling a spiral, rotating a matrix 90 degrees (transpose, then reverse each row).
• Robot instructions: decide whether a robot stays within a circle by simulating the instruction string up to four times.
• Cellular automata: Game of Life (in place), prison cells after N days (cycle detection).
• Queue and stack processes: asteroid collisions (stack), round-robin and voting games (queue), time needed to buy tickets (simulate or count directly).
• Event-driven simulation: process events in time order with a heap, jumping the clock from one event to the next instead of ticking every second.
• Text processing: text justification, log formatting; split into helper functions for each rule.