← Create New Paste

Game Theory and Minimax DP in Coding Interviews: Stone Game, Predict the Winner and Nim

5 views
"Two players take turns, both play optimally, who wins?" This family of questions confuses many candidates because it feels like it needs a new kind of thinking. It doesn't. Almost every two-player game question in interviews reduces to one of three tools: a minimax recursion with memoization, a "score difference" DP, or a mathematical pattern such as Nim. The core idea: think in score difference Take LeetCode 486, Predict the Winner. Players pick from either end of an array; the larger total wins. The tempting approach tracks two scores, which gets messy. Instead, define dp(i, j) as the best score difference the player to move can achieve on nums[i..j]. The current player takes one end, and then the opponent gets the best difference on what's left, which counts against us: from functools import lru_cache def predict_the_winner(nums): @lru_cache(None) def dp(i, j): if i > j: return 0 return max(nums[i] - dp(i + 1, j), nums[j] - dp(i, j - 1)) return dp(0, len(nums) - 1) >= 0 This one line, "my gain minus the opponent's best result," is the key insight. Once you see it, Stone Game (877), Stone Game II (1140) and Stone Game III (1406) all follow the same template with different move rules. That's O(n^2) states with O(1) transitions for the interval version. Win/lose states for boolean games When the game has no score, just win or lose, define win(state) = True if there is any move leading to a state where the opponent loses: def can_win(state): return any(not can_win(next_state) for next_state in moves(state)) Can I Win (464) uses this with a bitmask of used numbers as the state, giving 2^n states. Mention the bitmask early. Interviewers like candidates who notice that the order of moves doesn't matter, only the set of used numbers. When math replaces DP Some games have closed-form answers, and interviewers sometimes want you to discover them: - Nim Game (292): you lose exactly when n is a multiple of 4. Derive it by computing small cases with the win/lose recursion, spotting the pattern, then proving it. - Classic multi-pile Nim: the first player wins exactly when the XOR of the pile sizes is nonzero. - Stone Game (877) with an even number of piles: the first player always wins, because they can choose to take all even-indexed or all odd-indexed piles. A good strategy in an interview is to write the brute-force recursion first, run it mentally on small inputs, and then say "I notice a pattern; let me try to prove it." That shows both rigor and insight. How to communicate 1. Define the state precisely, including whose turn it is or that values are relative to the player to move. 2. State the recurrence in words before coding. 3. Add memoization and give the state count times transition cost. 4. Check base cases, such as an empty interval or no moves left. These problems reward calm, structured thinking far more than memorization, and that is exactly what slips when you're nervous on a live call. Practicing out loud helps; some candidates also use Linkjob AI (https://linkjob.ai) for real-time help during live technical interviews to keep their reasoning organized. Once "my gain minus their best" clicks, the whole category becomes much less intimidating.
Created Nov 15, 2026 07:55 Expires Nov 15, 2027 07:55