InterviewDB
Experience
Game Sequence: Determine the Winner of an Optimal Token-Taking Game
Onsite
Interview Experience
Problem
Two players alternate taking tokens from a pile. On each turn a player may take between 1 and k tokens (inclusive). The player who takes the last token wins. Given the initial pile size n and k, determine who wins assuming both play optimally —
return "Player 1" or "Player 2".
python
def game_winner(n: int, k: int) -> str:
pass
**Input**: n = 4, k = 3
Output: "Player 2"
# Whatever P1 takes (1,2,3), P2 can take (3,2,1) to finish.
# If P1 takes 1 -> 3 left, P2 takes 3 -> wins.
**Input**: n = 5, k = 3
Output: "Player 1"
# P1 takes 1 -> 4 left -> P2 is now in losing position.
**Input**: n = 7, k = 2
Output: "Player 1"
Follow-ups
- What is the closed-form condition for Player 2 winning in terms of
nandk? - How does Sprague-Grundy theory generalize this to sums of such games?
- Modify the rules so the player who takes the LAST token LOSES (misere game) — how does the winner change?
- If each player may also choose to skip their turn once, how does that affect the analysis?
Full Details
Problem
Two players alternate taking tokens from a pile. On each turn a player may take between 1 and k tokens (inclusive). The player who takes the last token wins. Given the initial pile size n and k, determine who wins assuming both play optimally —
return "Player 1" or "Player 2".
python
def game_winner(n: int, k: int) -> str:
pass
**Input**: n = 4, k = 3
Output: "Player 2"
# Whatever P1 takes (1,2,3), P2 can take (3,2,1) to finish.
# If P1 takes 1 -> 3 left, P2 takes 3 -> wins.
**Input**: n = 5, k = 3
Output: "Player 1"
# P1 takes 1 -> 4 left -> P2 is now in losing position.
**Input**: n = 7, k = 2
Output: "Player 1"
Follow-ups
- What is the closed-form condition for Player 2 winning in terms of
nandk? - How does Sprague-Grundy theory generalize this to sums of such games?
- Modify the rules so the player who takes the LAST token LOSES (misere game) — how does the winner change?
- If each player may also choose to skip their turn once, how does that affect the analysis?
Free preview. Unlock all Decagon questions →
About This Question
This is a candidate experience report from a decagon interview during the onsite round.
More Decagon Interview Questions
1p3a
decagon tech phone screen interview: cooking app cart implementation
InterviewDB
Function Time: Compute Exclusive Execution Time of Each Process
InterviewDB
Grid Guessing: Minimum Queries to Locate a Hidden Cell in a Matrix
InterviewDB
Mado Average: Sliding Window Average with Variable Window Size
InterviewDB
Decagon SWE Phone - Skyline Buildings (Stack/Geometry)