## Problem Two players alternate turns. There is a token on integer position `pos` on a number line. Each turn the current player moves the token left or right by any value in a given set `moves` (e.g., `{1, 3}`). A player who moves the token to position 0 wins. A player who cannot move (or is forced to move off the line) loses. Given `pos` and `moves`, determine if the first player wins with optimal play. ```python def first_player_wins(pos: int, moves: set[int]) -> bool: ... ``` ``` moves = {1, 3}, pos = 4 Winning positions (W) vs losing positions (L): pos=0: W (you just won) pos=1: W (move 1 -> 0) pos=2: L (can go to 1 or ... 1 is W for opponent; -1 invalid) pos=3: W (move 3 -> 0) pos=4: L (move 1->3 W for opp, move 3->1 W for opp) Output: False (first player loses) ``` ## Follow-ups 1. This is a combinatorial game theory problem. Describe the DP recurrence for `is_winning(pos)`. 2. What is the time complexity of your DP solution, and what is the memoization base case? 3. How does the problem change if moves can also increase `pos` (bidirectional movement)? 4. Extend to a 2D grid: the token is at `(r,c)`, allowed moves are `{up, down, left, right}`. The player who reaches `(0,0)` wins. How do you adapt your solution?

InterviewDB Experience

Line Game: Optimal Strategy for a Positional Token-Moving Game on a Number Line

phone

Interview Experience

Problem Two players alternate turns. There is a token on integer position pos on a number line. Each turn the current player moves the token left or right by any value in a given set moves (e.g., {1, 3}). A player who moves the token to position 0 wins. A player who cannot move (or is forced to move off the line) loses. Given pos and moves, determine if the first player wins with optimal play. Follow-ups This is a combinatorial game theory problem. Describe the DP recurrence for is_winning(pos).…

Full Details

🔒

Unlock all Hudson River Trading 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 hudson river trading interview during the phone round.

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

Topics

Coding Phone Matrix Dynamic Programming

Line Game: Optimal Strategy for a Positional Token-Moving Game on a Number Line

Interview Experience

Full Details

About This Question

Topics

More Hudson River Trading Interview Questions