Simulation Problems on LeetCode — Tic Tac Toe, Candy Crush, and Beyond

Simulation problems ask you to implement the logic of a system, game, or process exactly as described. There is no clever algorithm to discover, no recurrence to derive, no graph to traverse. You read the rules, and you implement them. This sounds straightforward — and that is precisely why simulation problems are so dangerous in technical interviews.

The difficulty in simulation problems is not conceptual. It is implementation. The rules of Tic Tac Toe, Candy Crush, or the Snake Game are simple enough to explain to a child. But translating those rules into clean, bug-free, efficient code under interview pressure — while managing shared state, handling edge cases, and avoiding mutation bugs — is exactly the skill that separates polished candidates from those who struggle.

Simulation problems are popular at Meta because they evaluate implementation accuracy and requirement-translation skills. Meta's engineering culture prizes writing correct, readable code quickly. A simulation problem with five edge cases is a direct test of that discipline: do you handle the edge cases, or do you implement only the happy path?

Google uses simulation problems to test what they call 'coding fluency' — the ability to convert a precise written spec into working code without ambiguity. Amazon and Microsoft use simulation problems in the design track, where the question is framed as 'design a system that does X' and the implementation is a direct translation of the design.

This guide covers every major simulation category: board games (#348, #289, #794), grid cascades (#723, #699, #735), and state machines (#353, #1603). For each category you will learn the core pattern, the common bugs, and the approach that lets you implement correctly on the first attempt. The 4-step simulation method at the end of this guide works for every problem in every category.

A simulation problem gives you a system with defined state and defined transition rules. Your job is to implement those rules faithfully: update the state correctly for each event, check invariants accurately, and return the right output at the right time. The problem is fully specified — there is no room for clever shortcuts, only room for correct implementation.

Simulation problems split into four categories based on what kind of system you are modeling. Board game simulations (Tic Tac Toe, Game of Life, Connect Four) require you to manage a fixed-size grid and check win conditions efficiently. Grid cascade simulations (Candy Crush, Falling Squares, Asteroid Collision) require you to apply repeated transformations to a grid or array until a stable state is reached. State machine simulations (Snake Game, Parking System, LRU Cache) require you to track current state and handle valid and invalid transitions. Event-driven simulations (Task Scheduler, Meeting Rooms, Car Pooling) require you to process a sequence of events in order and maintain running state.

Interviewers use simulation problems for three reasons. First, a simulation problem has an unambiguous correct answer — the spec is the spec, and an incorrect implementation fails clearly. This makes grading objective. Second, simulation problems reveal whether a candidate reads carefully: many bugs in simulation problems come from misreading the spec, not from algorithmic errors. Third, simulation problems expose implementation habits: do you define state cleanly? Do you separate reading state from writing state? Do you handle the edge cases first or last?

The most common failure mode in simulation problems is mutating state while iterating — the fix: always read from one copy and write to another. In Game of Life, for example, updating cells in-place means later cells see already-updated neighbors instead of original neighbors. This produces wrong output for every board with adjacent transitions. The fix is always the same: snapshot the current state, compute the next state into a fresh copy, then replace.

Simulation problems are rarely Hard algorithmically — most are Medium on LeetCode. But they are Hard to implement correctly under pressure. The candidate who has studied the simulation pattern can reliably finish in 20-25 minutes. The candidate who has not may spend 40 minutes debugging state mutation issues that a two-line fix would have prevented.

Board game simulations share a common structure: a fixed-size grid, a set of legal moves, and a win condition. The implementation challenge is writing an efficient win-check and keeping state minimal. Naive approaches that scan the entire board after every move produce correct but slow code. The pattern for board game simulations is: maintain just enough state to make win detection O(1) or O(board_dimension), never O(board_size^2).

Design Tic-Tac-Toe (#348) is one of the most common simulation questions at Meta. The naive approach scans the full board after each move to check rows, columns, and diagonals — O(n) per move. The optimal approach maintains running totals: an array of row counts and column counts for each player, plus two diagonal counters. Each move increments the relevant counters in O(1). A win is detected when any counter reaches n. The insight is that you never need to re-read the board — you only need the count of marks in each line.

Game of Life (#289) is the canonical example of the state-mutation pitfall. The board must be updated simultaneously: all cells read the current generation, all cells write the next generation. If you update in-place left-to-right top-to-bottom, cells in the top-left affect counts for cells in the bottom-right. The standard fix is to compute the full next state into a separate grid. The in-place optimization uses two extra state values (was alive, now dead) and (was dead, now alive) encoded as integers to avoid the extra O(mn) space, but the logic is identical.

Valid Tic-Tac-Toe State (#794) tests whether a given board configuration could be reached by valid play. This is a constraint-checking simulation: count X's and O's, verify the count invariant (X plays first, so countX == countO or countX == countO + 1), then verify at most one player has won and only the right player can have won given the counts. The problem is not about simulating play — it is about reasoning backward from a state to whether it is reachable. This reversal (state-to-validity rather than moves-to-state) is a common simulation variant.

The pattern for board game simulations: (1) define the minimal state representation — not the full board if a summary suffices; (2) update state incrementally on each move rather than recomputing from scratch; (3) detect win conditions from the summary state, not from a full board scan; (4) for simultaneous-update games like Game of Life, always snapshot before writing.

Grid cascade simulations model systems where applying a rule once may trigger further applications of the same rule — a cascade. The key pattern is the simulation loop: apply the rule, check if any changes occurred, and if so, apply the rule again. Repeat until no changes occur (a fixed point). The temptation is to try to compute the final state analytically. Resist it — simulate round by round.

Candy Crush (#723) is the definitive grid cascade problem. The rules: mark all horizontally and vertically adjacent groups of 3+ same-value cells, then crush all marked cells simultaneously, then drop remaining cells downward due to gravity. If any cells were crushed, repeat from the marking step. The simultaneous-crush rule is the mutation trap: you must mark all crushable cells before removing any. Removing first and marking second produces incorrect cascades. The implementation uses two passes per round: one pass to mark, one pass to remove and compact.

Asteroid Collision (#735) is a cascade simulation on an array rather than a grid. Moving right (+) and left (-) asteroids collide when a right-moving asteroid is followed by a left-moving asteroid. The collision resolution itself can trigger further collisions as a larger surviving asteroid collides with the next one. A stack naturally models this: push right-moving asteroids, pop when a left-moving asteroid arrives and the top of the stack collides. The simulation is complete when the stack stabilizes. This is the cascade pattern on a 1D sequence.

Falling Squares (#699) places squares on a number line and asks for the maximum height after each placement. Each square lands on top of existing squares it overlaps. The state is a list of (left, right, height) intervals. For each new square, find all existing intervals it overlaps, take the max height of those intervals, then add the new square's side length to get the new interval's height. A segment tree optimizes this to O(log n) per query, but the O(n^2) simulation — iterate over all intervals, check overlap, take max — is sufficient for most interview contexts.

The cascade simulation pattern: define a single round of transformation, run it repeatedly until the board reaches a fixed point (no changes in a full round), and always apply the full round atomically before checking for cascades. The most common bug is checking for cascades mid-round, which breaks the simultaneous-update semantics. Always complete the full round before deciding whether to cascade.

A useful debugging technique for cascade problems: add a round counter and print the board state after each round. In interviews you will not print — but thinking through the first two rounds manually before coding reveals edge cases that are invisible until the cascade triggers. Specifically, ask: 'What happens if two cascade-triggering conditions are adjacent?' and 'What happens if a cascade produces a new cascade-triggering condition?' The answers determine whether your round boundary logic is correct.

State machine simulations model systems with discrete states and defined legal transitions between those states. The implementation requires: (1) an explicit representation of the current state, (2) a function that takes the current state and an event and returns the next state, and (3) validation that each transition is legal given the current state.

Snake Game (#353) is the canonical state machine simulation. The snake's state is the sequence of cells it occupies (a deque, with the head at the front and the tail at the end), plus the set of occupied cells for O(1) collision detection. Each move transitions the state: remove the tail (unless food was just eaten), add the new head in the movement direction, check if the new head hits a wall or the snake's body. The legal-transition check is: new head must be within bounds and not in the occupied set. If food is present at the new head, do not remove the tail, and update the food pointer.

Parking System (#1603) is a minimal state machine: three counters (big, medium, small), each decremented on the corresponding parking request. A request is illegal if the counter is already zero. The state transition is a simple decrement-and-check. This problem appears trivial — and it is — but it illustrates the state machine pattern at its minimum viable complexity: defined state, defined events, defined legal transitions.

The state machine pattern generalizes to more complex problems: LRU Cache (#146) is a state machine where the state is a doubly-linked list plus a hash map, and each get/put operation is a defined state transition. Design Twitter (#355) is a state machine where the state is a user-to-tweet map and a follow graph, and each post/follow/unfollow/getNewsFeed operation is a defined transition. Both problems become straightforward once the state and transitions are explicitly defined before any code is written.

The most common mistake in state machine simulations is conflating state with derived properties. In Snake Game, the set of occupied cells is derived from the deque — you can always recompute it by iterating the deque. Maintaining it separately as a set is an optimization for O(1) collision detection, not a separate piece of state. Keeping this distinction clear prevents bugs where the deque and set get out of sync.

Every simulation problem, regardless of category, responds to the same preparation. The four steps are: define state, enumerate transitions, handle edge cases first, simulate in order. Candidates who internalize this method produce correct simulation code reliably. Candidates who code immediately — before defining state — produce code that requires significant rework when the first edge case fails.

Define state means: what is the minimum information needed to answer every query and apply every transition? For Tic Tac Toe, the minimum state is row counts, column counts, and diagonal counts — not the full board. For Snake Game, the minimum state is the cell deque and the occupied cell set. For Candy Crush, the minimum state is the full grid (no shortcut is available because any cell can be affected by any crush). Writing down the state type before writing any function forces precision.

Enumerate transitions means: for each type of event the simulation can receive, write the exact state update. This is the most important step because bugs in simulations are almost always transition bugs — you updated the wrong field, updated in the wrong order, or forgot to update one field. Writing out all transitions in pseudocode or comments before implementing them gives you a checklist to verify against.

Handle edge cases first means: write the guard clauses at the top of every function before the main logic. Game over (snake out of bounds, snake eats itself)? Return -1 at the top. No food left in Candy Crush cascade? Return at the top. Board already in valid state? Return true at the top. Putting edge cases first instead of last ensures that the main logic path is never reached with invalid state — which is where the hardest-to-debug errors appear.

Simulate in order means: never look ahead, never retroactively fix state, never batch-process events out of sequence. Apply each event to the current state, produce the next state, then move to the next event. If a cascade is required (Candy Crush, Asteroid Collision), complete the current event fully before triggering the cascade. This constraint forces your code into a clean pipeline where each step's output is the next step's input.

The top three bugs in simulation interviews: (1) mutating state during iteration — always separate the read phase from the write phase; (2) forgetting to reset temporary state between rounds — in Candy Crush, the 'marked' set must be cleared each round; (3) off-by-one in boundary checks — when is a position out-of-bounds? Write helper functions for bounds checking so the boundary condition is defined once.

Simulation problems are the category that most clearly rewards pre-coding discipline. The candidate who spends the first five minutes defining state, listing transitions, and identifying edge cases will write clean, correct code in the next fifteen. The candidate who starts coding immediately will produce partially correct code and spend the last twenty minutes in a difficult debugging session.

The problems covered in this guide — Design Tic-Tac-Toe (#348), Game of Life (#289), Valid Tic-Tac-Toe State (#794), Candy Crush (#723), Falling Squares (#699), Asteroid Collision (#735), Snake Game (#353), and Parking System (#1603) — represent the full range of simulation patterns. Each one has appeared in real FAANG interviews within the last two years. Solving all eight, with clean implementations, prepares you for every simulation problem you are likely to encounter.

Simulation problems are popular at Meta because they evaluate implementation accuracy and requirement-translation skills. When a Meta interviewer gives you a simulation problem, they are watching whether you read the spec carefully, whether your first implementation is correct or requires debugging, and whether you handle the edge cases proactively. These are exactly the qualities Meta values in production engineers.

The tic tac toe leetcode problem family — Design Tic-Tac-Toe (#348), Valid Tic-Tac-Toe State (#794), and the conceptually adjacent Game of Life (#289) — is particularly important because it appears across multiple interview levels. Entry-level interviews ask for basic implementation. Mid-level interviews ask for the O(1) win detection optimization. Senior-level interviews ask for the concurrency-safe version. Knowing all three versions makes you prepared at any level.

YeetCode helps you recognize simulation cues in problem statements: phrases like 'simultaneously', 'in rounds', 'until stable', 'track position', and 'valid state' are the keywords that mark a simulation problem. Training yourself to identify these cues and immediately apply the 4-step simulation method — define state, enumerate transitions, handle edge cases first, simulate in order — is the practice that makes simulation problems fast, reliable, and professionally implemented.

Simulation problems look easy. They are not. But they are learnable. The pattern is consistent across all four categories, the common bugs are well-defined, and the 4-step method eliminates most of them before a single line of code is written. Master this pattern and you will walk into any simulation interview with a reliable, reproducible process — which is exactly what the interviewer is hoping to see.