## Problem Two players alternate turns on an N x M grid. Each cell is either empty (`.`) or a mine (`*`). A player places their token on the grid and must move it exactly one step (up, down, left, right) on their turn. A player loses if they step on a mine or have no valid moves. Both play optimally. Given the starting position and whose turn it is, determine whether the first player wins or loses. ```python def mine_game(grid: list[str], start_r: int, start_c: int) -> str: # Returns "WIN" if first player wins, "LOSE" otherwise pass ``` **Example:** ``` grid = [ "...", ".*.", "..." ] start_r, start_c = 0, 0 -> "WIN" grid = [".*", ".."], start_r=0, start_c=0 -> "WIN" # first player can avoid the mine ``` ## Follow-ups 1. What game-theory concept underpins this problem, and what is the time complexity of the minimax approach? 2. How would you use memoization to avoid recomputing states you have already visited? 3. What if a player can move 1 OR 2 steps in a single turn? How does the state space change? 4. Can you detect cycles (infinite games) and handle them as a draw rather than a win/loss?

InterviewDB Experience

Mine Game: Determine Winning Strategy in a Two-Player Minefield Traversal Game

Onsite

Interview Experience

Problem Two players alternate turns on an N x M grid. Each cell is either empty (.) or a mine (*). A player places their token on the grid and must move it exactly one step (up, down, left, right) on their turn. A player loses if they step on a mine or have no valid moves. Both play optimally. Given the starting position and whose turn it is, determine whether the first player wins or loses. Example: Follow-ups What game-theory concept underpins this problem, and what is the time complexity of t…

Full Details

🔒

Unlock all Applied Intuition questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a candidate experience report from a applied intuition interview during the onsite round.

It covers the following topics: Matrix, Coding, Onsite, Dynamic Programming .

Topics

Matrix Coding Onsite Dynamic Programming

Mine Game: Determine Winning Strategy in a Two-Player Minefield Traversal Game

Interview Experience

Full Details

About This Question

Topics

More Applied Intuition Interview Questions