Card Gambling with Perfect Stops

This interview question presents a finite-horizon gambling game based on drawing red and black cards without replacement from a shuffled deck. The candidate is allowed to stop at any time and lock in the cumulative gain or loss, and is asked to determine both the optimal stopping strategy and the game's fair entry price. It probes how you think about path-dependent payoffs and dynamic decisions when the underlying randomness is simple but the decision space is large. Variants and related ideas often appear in quant trading and derivatives roles, where you must decide when to exit positions under evolving but fully specified distributions.

Solving it leans heavily on optimal stopping, dynamic programming, and martingale-style reasoning. The key challenge is handling a Markov state that evolves deterministically given the history, yet with transition probabilities that change as the deck is depleted. A strong answer organizes the state space cleanly, sets up backward induction over all possible compositions of remaining cards, and recognizes symmetry or value-function structure to avoid brute force. Interviewers look for clear formulation, correct conditioning on future paths, and an ability to justify stopping rules qualitatively, not just numerically.

What it tests

This problem class is governed by the principle of optimal stopping in sequential decision processes, where the future is uncertain but the state evolves deterministically with each action. The core structure is that, at each decision point, you compare the immediate reward from stopping to the expected value of continuing, given the probabilistic transitions to future states. The optimal strategy is to stop whenever the current state's deterministic value exceeds or equals the expected value of all possible continuations. This maximizes expected payoff by ensuring you never risk a favorable position for a statistically worse one. The pattern holds because, in any finite Markov process with known transitions and rewards, backward induction guarantees that the optimal choice at each step is determined by maximizing between stopping and the expected continuation value.