New 21 Game

New 21 Game

What is this problem about?

The New 21 Game is a probability problem. A player starts with 0 points. Each round, they draw a number from 1 to maxPts uniformly at random and add it to their score. They stop when their score reaches at least n. Find the probability that their final score is at most maxScore. This New 21 Game coding problem combines probability reasoning with dynamic programming and a sliding window optimization.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it requires translating a probability problem into DP with a clever sliding window optimization. Understanding how to express transition probabilities cleanly and then optimize the summation window is the key challenge. The math, sliding window, probability, and dynamic programming interview pattern is at the core.

Algorithmic pattern used

DP with sliding window. dp[i] = probability of reaching exactly score i before stopping. For scores 0 to n-1 (still drawing), dp[i] = (sum of dp[i-maxPts..i-1]) / maxPts. For scores n to maxScore (stopped), accumulate them into the answer. Maintain a rolling window sum to avoid O(maxPts) inner computation per state, achieving O(n + maxScore) total time.

Example explanation

n=10, maxPts=10, maxScore=21. Start at 0. Can draw 1-10 each round. dp[0]=1. For i=1 to 9: dp[i] = windowSum/10. For i=10 to 21: these are stopped scores — add dp[i] to answer if i ≤ maxScore. Answer = sum of dp[n..maxScore] = probability ≈ 1.0 (most draws stay within 21 here, depends on parameters).

Common mistakes candidates make

• Not using the sliding window optimization (O(n * maxPts) naive DP TLEs).
• Incorrectly computing the window boundary (slides from i-maxPts to i-1).
• Confusing when the player stops (at score ≥ n, not > n).
• Forgetting to handle edge cases: n=0 (probability=1), maxScore ≥ n+maxPts (probability=1).

Interview preparation tip

Probability DP problems translate "probability of event X" into dp[state] = P(reaching state) and compute transitions as weighted sums. The sliding window optimization here is the key performance insight — recognize when a DP transition is a sum over a fixed-size window and apply the +new/-old sliding window pattern. Practice this combination of probability reasoning + DP + sliding window as a compound skill — it appears in card game, lottery, and scoring problems across top-company interviews.