Simulation Coding Problems: 88 Questions with Solutions

How simulation works, step by step

1. The robot starts at (0, 0) facing north. G steps one cell forward unless an obstacle (#) or the edge of the grid is in the way; L and R turn 90° on the spot. No cleverness is needed: following the rules exactly is the solution.
2. G: facing north, a step adds (0, 1) to the position. (0, 1) is free, so the robot moves there.
3. Another G, still facing north: (0, 2) is free too, so the robot moves again.
4. R at (0, 2) turns the robot from north to east without moving. Headings are an index into [north, east, south, west], so R is +1 and L is −1, mod 4.
5. G: now facing east, a step adds (1, 0) instead, and (1, 2) is free, so the robot moves there.
6. G at (1, 2): the cell ahead, (2, 2), holds an obstacle, so the robot stays put. The command is used up, but the position does not change.
7. L at (1, 2) turns the robot from east to north without moving. Only the heading changes, so the next G goes a new way.
8. G: now facing north, a step adds (0, 1) instead, and (1, 3) is free, so the robot moves there.
9. G at (1, 3): the cell ahead, (1, 4), is off the grid, so the wall stops the robot exactly as an obstacle would.
10. All 8 commands are done: the robot ends at (1, 3) facing north, after 2 blocked steps. With the obstacles in a hash set each command is O(1), so the run is O(n) for n commands.

Simulation study plan

12 of the 88 Simulation problems (4 easy, 7 medium and 1 hard) over 6 days, about 6 h 30 min in all — the pattern first, then easiest to hardest. After that, the other 76 in the full list below are practice at your own pace. Then move on to Enumeration.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

• Concatenation of Array Easy
• Build Array from Permutation Easy
• Baseball Game Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

• Transpose Matrix Easy
• Spiral Matrix Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Game of Life Medium
• Multiply Strings Medium

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Asteroid Collision Medium
• Count and Say Medium

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Spiral Matrix II Medium
• Diagonal Traverse Medium

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

• Meeting Rooms III Hard

Next topic: Enumeration

Simulation: the essentials

When to reach for it

The statement describes a process step by step — a robot's moves, a game's turns, rounds of an operation on an array — and the limits make running it affordable: steps × cost per step should stay within about 10⁷–10⁸ simple operations. If the number of steps is huge (10⁹ rounds), the state must repeat or follow a formula; find that instead of running every step.

The pattern

Write down the full state first, every variable that changes between steps, then a function from one state to the next. When all cells or players update "at the same time", compute the new state from an untouched copy of the old one, or encode old and new together in each cell. Keep each rule on its own line, in the statement's order.

def life_step(board):
    R, C = len(board), len(board[0])
    old = [row[:] for row in board]     # read the old, write the new
    for r in range(R):
        for c in range(C):
            live = sum(old[i][j]
                       for i in range(max(0, r - 1), min(R, r + 2))
                       for j in range(max(0, c - 1), min(C, c + 2))) - old[r][c]
            board[r][c] = int(live == 3 or (live == 2 and old[r][c] == 1))

Cost

Steps × cost per step. Copying the state each step adds O(size) space; encoding both values in one cell (say, 2 for "alive, about to die") removes it.

Common mistakes

• Updating in place when the rules are simultaneous, so later cells see half-updated neighbours.
• Applying rules in a different order from the statement, or one rule twice in a step.
• An off-by-one in the number of rounds — whether the initial state counts as round 0.
• Running 10⁹ steps of a state that repeats; detect the cycle and skip ahead.

Start with

• Baseball Game: one record, one rule per operation.
• Spiral Matrix: a walk whose turning rule needs care.
• Game of Life: a simultaneous update over a grid.

All simulation problems

Easy (48)

• Find the Losers of the Circular Game Array, Hash Table
• Delete Greatest Value in Each Row Array, Matrix, Sorting
• Find the Encrypted String String
• Distribute Elements Into Two Arrays I Array
• Separate the Digits in an Array Array
• Find the Child Who Has the Ball After K Seconds Math
• Matrix Similarity After Cyclic Shifts Array, Matrix
• Determine the Winner of a Bowling Game Array
• Maximum Height of a Triangle Array, Greedy, Enumeration
• Take Gifts From the Richest Pile Array, Heap, Greedy
• Defuse the Bomb Array, Sliding Window
• Count Total Number of Colored Cells Math
• Count Distinct Numbers on Board Math, Number Theory
• Number of Lines To Write String Array, String
• Divide a String Into Groups of Size k String
• Minimum Number Game Array, Sorting
• Minimum Operations to Collect Elements Array, Hash Table
• Find the Array Concatenation Value Array, Two Pointers
• Count Tested Devices After Test Operations Array, Counting
• Ant on the Boundary Array, Prefix Sum
• Count Integers With Even Digit Sum Math
• Sum of Digits of String After Convert String
• Count of Matches in Tournament Math
• Count Operations to Obtain Zero Math
• Teemo Attacking Array
• Distribute Candies to People Array, Math
• Water Bottles Math
• XOR Operation in an Array Math, Bit Manipulation
• Minimum String Length After Removing Substrings String, Stack
• Number of Students Unable to Eat Lunch Array, Stack, Queue
• Time Needed to Buy Tickets Array, Queue
• Baseball Game Array, String, Stack
• Find Winner on a Tic Tac Toe Game Array, Hash Table, Matrix
• Convert 1D Array Into 2D Array Array, Matrix
• Cells with Odd Values in a Matrix Array, Math
• Shift 2D Grid Array, Matrix
• Flipping an Image Array, Two Pointers, Matrix
• Reshape the Matrix Array, Matrix
• Apply Operations to an Array Array, Two Pointers
• Create Target Array in the Given Order Array
• Decompress Run-Length Encoded List Array
• Concatenation of Array Array
• Build Array from Permutation Array
• Add Strings Math, String
• Add Binary Math, String, Bit Manipulation
• Add Digits Math, Number Theory
• Transpose Matrix Array, Matrix
• Fizz Buzz Math, String

Medium (39)

• Find the Winner of an Array Game Array
• Queries on a Permutation With Key Array, Binary Indexed Tree
• Find the Winner of the Circular Game Array, Math, Recursion
• Minimum Operations to Exceed Threshold Value II Array, Heap (Priority Queue)
• Water Bottles II Math
• Process Tasks Using Servers Array, Heap (Priority Queue)
• Total Cost to Hire K Workers Array, Two Pointers, Heap (Priority Queue)
• Number of Orders in the Backlog Array, Heap (Priority Queue)
• Magic Squares In Grid Array, Matrix
• Check Knight Tour Configuration Array, Matrix, Depth-First Search
• Rotating the Box Array, Matrix, Two Pointers
• Spiral Matrix III Array, Matrix
• Where Will the Ball Fall Array, Matrix, Depth-First Search
• Difference Between Ones and Zeros in Row and Column Array, Matrix
• Find the N-th Value After K Seconds Array, Math, Prefix Sum
• Number of People Aware of a Secret Queue, Dynamic Programming
• Find Three Consecutive Integers That Sum to a Given Number Math
• Count Collisions on a Road String, Stack, Greedy
• Find the Student That Will Replace the Chalk Array, Binary Search, Prefix Sum
• Watering Plants II Array, Two Pointers
• Push Dominoes String, Two Pointers, Dynamic Programming
• Clumsy Factorial Math, Stack
• Smallest Value After Replacing With Sum of Prime Factors Math, Number Theory
• Equal Row and Column Pairs Hash Table, Matrix
• Number of Steps to Reduce a Number in Binary Representation to One String, Bit Manipulation
• Concatenation of Consecutive Binary Numbers Math, Bit Manipulation
• Remove All Occurrences of a Substring String, Stack
• Removing Stars From a String String, Stack
• Reveal Cards In Increasing Order Array, Queue, Sorting
• Validate Stack Sequences Array, Stack
• Build an Array With Stack Operations Array, Stack
• Rearrange Array Elements by Sign Array, Two Pointers
• Game of Life Array, Matrix
• Diagonal Traverse Array, Matrix
• Spiral Matrix II Array, Matrix
• Count and Say String
• Spiral Matrix Array, Matrix
• Asteroid Collision Array, Stack
• Multiply Strings String, Math

Hard (1)

• Meeting Rooms III Array, Sorting, Heap (Priority Queue)

Companies that ask simulation problems

• Amazon 78 problems on simulation
• Google 34 problems on simulation
• Adobe 31 problems on simulation
• Microsoft 18 problems on simulation
• TCS 13 problems on simulation
• Infosys 6 problems on simulation
• Zoho 6 problems on simulation
• Meta 5 problems on simulation
• Accenture 4 problems on simulation
• Cognizant 4 problems on simulation
• Capgemini 3 problems on simulation
• Flipkart 3 problems on simulation

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Bit Manipulation 83 problems
• Sliding Window 71 problems