Stone Game

Stone Game

What is this problem about?

In the Stone Game coding problem, two players, Alice and Bob, play a game with an even number of piles of stones arranged in a row. Each pile has a positive number of stones. The players take turns taking all the stones from either the first or the last pile in the current row. Alice goes first. The goal is to determine if Alice can win (collect more stones than Bob).

Why is this asked in interviews?

This is a famous problem that tests both Dynamic Programming and mathematical observation. While it can be solved with DP, there's a mathematical "trick" that guarantees the first player always wins under specific conditions (even number of piles, total stones is odd). Companies like Meta and Google ask this to see if you can provide the formal DP solution while also being observant enough to find the constant-time mathematical proof.

Algorithmic pattern used

The formal Algorithmic pattern is Dynamic Programming or Game Theory with Memoization. You define a state dp(i, j) as the maximum relative score Alice can get from the piles between index $i$ and $j$. For her turn, she chooses between piles[i] - dp(i+1, j) and piles[j] - dp(i, j-1). This minimax approach is standard for two-player zero-sum games.

Example explanation (use your own example)

Piles: [3, 9, 1, 2].

• Alice can pick 3 or 2. If she picks 3, Bob gets to pick from [9, 1, 2].
• However, notice that if Alice picks all the "even-indexed" piles (indices 0 and 2) or all the "odd-indexed" piles (indices 1 and 3), she can control the entire game.
• Sum of even indices: $3 + 1 = 4$.
• Sum of odd indices: $9 + 2 = 11$. Since Alice goes first and the number of piles is even, she can always ensure she picks either all even or all odd piles by making the right first move. Therefore, she can always pick the larger set and win.

Common mistakes candidates make

• Overcomplicating the DP: Not realizing the state space can be simplified.
• Ignoring the Mathematical Trick: Failing to see that with even piles, the first player has a winning strategy by picking all odd or all even piles.
• Greedy approach: Assuming picking the largest available pile at each step is optimal (it's not).
• Off-by-one errors: In the DP table transitions.

Interview preparation tip

For Game Theory interview pattern problems, always check if there's a symmetry or a parity argument that allows the first player to win. If not, fall back to the Minimax or Dynamic Programming approach.