Find the Winning Player in Coin Game

Find the Winning Player in Coin Game

1. What is this problem about?

The Find the Winning Player in Coin Game interview question is a game theory problem with constraints. You have a pile of coins with values 75 and 10. In each turn, a player must pick coins that sum up to exactly 115. Usually, this means picking one 75-coin and four 10-coins. Two players take turns, and the one who cannot make a move loses. You need to determine who wins (Alice or Bob).

2. Why is this asked in interviews?

Bloomberg asks the Find the Winning Player coding problem to test a candidate's ability to simplify a game into a parity check. It evaluations whether you can identify the "limiting factor" in a resource-based game. It’s an introductory Math interview pattern that checks for logical deduction and simple simulation.

3. Algorithmic pattern used

This problem follows the Game Theory and Limiting Resource pattern.

• Rule: Each move consumes 1 coin of 75 and 4 coins of 10.
• Number of Moves: The maximum number of moves possible is min(count75, count10 / 4).
• Winner: If the total number of moves is odd, the first player (Alice) wins. If even, the second player (Bob) wins.

4. Example explanation

$count75 = 2, count10 = 7$.

• Turn 1 (Alice): Needs 1 (75) and 4 (10). She has them.
  • Remaining: $count75 = 1, count10 = 3$.
• Turn 2 (Bob): Needs 1 (75) and 4 (10). He has the 75, but only 3 of the 10s.
• Bob cannot move. Alice wins. Calculation: min(2, 7/4) = min(2, 1) = 1. 1 is odd, so Alice wins.

5. Common mistakes candidates make

• Actually simulating: While okay for small numbers, actually looping through turns is slower than the direct min calculation.
• Rounding errors: Not using integer division when checking the 10-coins ($7/4$ should be 1).
• Incorrect Parity: Mixing up whether Alice or Bob wins on even/odd counts.

6. Interview preparation tip

Whenever a game has fixed resource costs, the total number of turns is fixed regardless of player strategy. In such "impartial games," the outcome is simply a matter of turn count parity. This is a common Game Theory interview pattern shortcut.