Card Games & Probability — From Bitmask DP to Expectation

♠️ Why Card & Number Games Matter

Card and number games are a unique breed of interview problems. They combine:

• State space reasoning — tracking which numbers/cards are used
• Optimal play — both players act to maximize their win probability
• Probability theory — randomness adds an expectation layer
• DP optimization — from bitmask memoization to sliding window probability

These problems appear at Google, Meta, Amazon, and Jane Street interviews. The "I've seen this before" advantage is REAL — understanding the pattern transforms seemingly impossible probability puzzles into solvable DP problems.

1. Can I Win — Bitmask DP Game Tree

Problem: Two players take turns picking numbers from 1 tomaxChoosableInteger. Each number can be used at most once. The player who makes the running sum reach or exceed desiredTotal wins. Determine if the first player can force a win.

The Challenge: 2²⁰ States

With maxChoosableInteger ≤ 20, there are up to 2²⁰ = 1,048,576 possible states. That's too many for a naive recursive search without memoization. But it's perfectly manageable with bitmask DP — use an integer where bit i = 1 means number i has been used.

🔍 Real-Time Thinking — What Do I Know?

"OK, so maxChoosableInteger is at most 20. That's small enough for bitmask DP. Each state is defined by (mask, currentSum). If I memoize by mask, I don't even need to track currentSum separately — I can compute it from the mask. At each state, try every unused number. If picking it makes sum ≥ desiredTotal, I win immediately. Otherwise, if my opponent LOSES from the resulting state, I win. If no winning move exists, I lose. This is a classic DP with optimal play."

Algorithm

function canIWin(maxChoosable, desiredTotal) {
  // Quick check: if total sum < desiredTotal, no one can win
  const sumAll = (maxChoosable * (maxChoosable + 1)) / 2;
  if (sumAll < desiredTotal) return false;

  const memo = new Map();

  function dfs(mask, sum) {
    if (memo.has(mask)) return memo.get(mask);

    for (let i = 1; i <= maxChoosable; i++) {
      const bit = 1 << i;
      if (mask & bit) continue; // already used

      // If I can win immediately, or opponent loses from next state
      if (sum + i >= desiredTotal || !dfs(mask | bit, sum + i)) {
        memo.set(mask, true);
        return true;
      }
    }

    memo.set(mask, false);
    return false;
  }

  return dfs(0, 0);
}

📋 Edge Cases to Consider

• Total sum < desiredTotal: Neither player can reach the target. Return false.
• Max choosable ≥ desiredTotal: First player picks desiredTotal on turn 1. Instant win!
• Even/odd parity trick: Some versions have a mathematical shortcut — check if the total sum of all numbers is enough, then use symmetry.
• Memoization key: Using just mask (not sum) works because sum is derivable from the mask.

2. 24 Game — Expression Tree Search

Problem: Given 4 numbers, determine if you can make 24 using addition, subtraction, multiplication, and division, using each number exactly once.

The Expression Tree Approach

The key insight: any valid expression with 4 numbers can be represented as abinary tree where leaves are numbers and internal nodes are operators. The search space is: pick 2 numbers → apply an operator → reduce to 3 numbers → repeat until 1 number remains. Check if that number equals 24.

🔍 Real-Time Thinking — What Do I Know?

"4 numbers, 4 operators, each number used exactly once. The expression can be parenthesized arbitrarily. A binary tree with 4 leaves has a fixed shape: ((a ○ b) ○ c) ○ d or (a ○ b) ○ (c ○ d) or (a ○ (b ○ c)) ○ d, etc. Instead of generating all tree shapes explicitly, I can just pick any two numbers, apply all operators, and recurse on the reduced set. Division gives floating point — I need an epsilon comparison, not exact equality."

Algorithm

function judgePoint24(nums) {
  if (nums.length === 1) return Math.abs(nums[0] - 24) < 1e-6;

  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (i === j) continue;

      const candidates = [];
      const a = nums[i], b = nums[j];

      candidates.push(a + b, a * b, a - b, b - a);
      if (Math.abs(a) > 1e-6) candidates.push(b / a);
      if (Math.abs(b) > 1e-6) candidates.push(a / b);

      const rest = nums.filter((_, k) => k !== i && k !== j);
      for (const val of candidates) {
        if (judgePoint24([...rest, val])) return true;
      }
    }
  }
  return false;
}

📋 Edge Cases to Consider

• Floating point precision: Division produces fractions. Use epsilon = 1e-6.
• Division by zero: Check |denominator| > 1e-6 before dividing.
• Commutative operators: + and × are commutative, but − and ÷ are not. Include both orders.
• Same numbers: If nums has duplicates, the algorithm still works — it tries each pair by index.
• Zero as a number: [0, 0, 0, 0] → impossible. Algorithm correctly returns false.

3. New 21 Game — DP with Probability & Sliding Window

Problem: You draw points from [1, W] uniformly at random. You stop drawing when your cumulative sum ≥ K. You win if your final sum ≤ N. Compute the probability of winning.

The DP Probability Distribution

This is a one-player game with randomness. We computedp[i] = probability of reaching exactly sum i. The transition: from any state i (where i < K), you draw a number from 1 to W with equal probability 1/W, moving to state i + draw.

The naive DP is O(K × W). But we can optimize to O(N) using asliding window: dp[i] = (windowSum) / W, where windowSum = dp[i-1] + dp[i-2] + ... + dp[i-W].

🔍 Real-Time Thinking — What Do I Know?

"This is a probability DP. I need to find the probability that my final sum is between K and N. I start at sum 0 with probability 1. For each sum i < K, I can transition to i+1, i+2, ..., i+W with equal probability 1/W. So dp[i] = sum of dp[i-W]...dp[i-1] / W. That's a sliding window! I can maintain a running window sum. For i ≥ K, I stop drawing, so dp[i] accumulates into the answer if i ≤ N. The answer is the sum of dp[K] through dp[N]."

Algorithm

function new21Game(N, K, W) {
  if (K === 0) return 1.0; // Already stopped, always win (0 ≤ N)

  const dp = new Array(N + W + 1).fill(0);
  dp[0] = 1;
  let windowSum = 1; // dp[0]
  let result = 0;

  for (let i = 1; i <= N + W; i++) {
    dp[i] = windowSum / W;

    if (i >= K) {
      // Terminal state — stop drawing
      if (i <= N) result += dp[i];
    } else {
      // Still drawing — add to sliding window
      windowSum += dp[i];
    }

    // Remove dp[i-W] from window (it's now out of range)
    if (i - W >= 0) windowSum -= dp[i - W];
  }

  return result;
}

📋 Edge Cases to Consider

• K = 0: Game stops before it starts. Sum = 0 ≤ N, so return 1.0.
• N ≥ K + W - 1: You can never bust — the maximum sum before stopping is K + W - 1. If N is large enough, you always win.
• Large N vs K: If N < K, you can never win (you stop at sum ≥ K, but win needs sum ≤ N < K). Answer = 0.
• Sliding window boundaries: Be careful with array bounds — your DP array must go up to N + W to handle overflow states.

4. Flower Game — Alice, Bob & Parity Strategy

Problem: Alice and Bob play a game with a row of flowers. Each flower has a number. Players take turns picking from either end of the row. The player with the higher total sum wins. Determine if Alice can win (or force a draw).

The Parity Strategy

This is a classic optimal play problem. Alice can always compute her maximum guaranteed score using DP: dp[i][j] = maximum score the current player can achieve from subarray nums[i..j].

function flowerGame(nums) {
  const n = nums.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));

  // Base: single flower
  for (let i = 0; i < n; i++) dp[i][i] = nums[i];

  // Fill DP table: gap from 1 to n-1
  for (let gap = 1; gap < n; gap++) {
    for (let i = 0; i + gap < n; i++) {
      const j = i + gap;
      // Pick left: nums[i] + opponent's best from rest
      const pickLeft = nums[i] - dp[i + 1][j];
      // Pick right: nums[j] + opponent's best from rest
      const pickRight = nums[j] - dp[i][j - 1];
      dp[i][j] = Math.max(pickLeft, pickRight);
    }
  }

  // If dp[0][n-1] ≥ 0, Alice wins or draws
  return dp[0][n - 1] >= 0;
}

📋 Edge Cases to Consider

• Odd/even length: With even length and optimal play, Alice can force a win if total sum > 0.
• Draw condition: If both players end with equal totals, Alice wins? Depends on problem statement.
• Single element: Alice takes it and wins (or draws if the target is 0).
• All zeros: Both players end with 0. Draw (or Alice wins depending on rules).

5. Bag of Mice — Probability with Recursive Expectation

Problem: A bag contains w white mice andg gray mice. Alice and Bob take turns drawing one mouse each at random. Alice wins if she draws a white mouse. Bob wins if he draws a white mouse. After each pair of draws (Alice then Bob), one random mouse from the bag escapes (is removed). Determine Alice's win probability.

The Recursive Probability Tree

At state (w, g) on Alice's turn:

• Alice draws white with probability w / (w+g) → Alice wins immediately.
• Alice draws gray with probability g / (w+g) → Bob gets a turn.

If Alice drew gray, it's Bob's turn at state (w, g-1):

• Bob draws white → Bob wins (Alice loses).
• Bob draws gray → one random mouse escapes → state reduces → Alice's turn again.

🔍 Real-Time Thinking — What Do I Know?

"This is a recursive probability problem. At each state (w, g), Alice's win probability P(w, g) depends on: (1) she draws white now, or (2) she draws gray AND Bob draws gray AND Alice wins from the resulting state. The escape step after each round reduces total mice by 3 (Alice draws 1, Bob draws 1, 1 escapes). The state space is bounded by w, g ≤ 1000, so memoization is essential."

Algorithm

function bagOfMice(w, g) {
  const memo = new Map();

  function dfs(white, gray) {
    if (white <= 0) return 0;      // No white mice left — Alice can't win
    if (gray < 0) return 0;        // Invalid state
    if (gray === 0) return 1;      // Only white left — Alice wins for sure

    const key = white + "," + gray;
    if (memo.has(key)) return memo.get(key);

    const total = white + gray;

    // Alice draws white immediately
    let prob = white / total;

    // Alice draws gray, then Bob draws, then escape
    if (gray >= 2) {
      // Bob draws white
      const bobWhite = (gray / total) * (white / (total - 1));
      // Bob draws gray, then escape
      const bobGray = (gray / total) * ((gray - 1) / (total - 1));

      // If Bob draws gray, one mouse escapes (could be white or gray)
      // Escape white: state becomes (white-1, gray-2)
      const escapeWhite = bobGray * (white / (total - 2));
      // Escape gray: state becomes (white, gray-3)
      const escapeGray = bobGray * ((gray - 2) / (total - 2));

      prob += escapeWhite * dfs(white - 1, gray - 2);
      prob += escapeGray * dfs(white, gray - 3);
    }

    memo.set(key, prob);
    return prob;
  }

  return dfs(w, g);
}

📋 Edge Cases to Consider

• No white mice (w = 0): Alice can never win. Return 0.
• No gray mice (g = 0): Alice always draws white. Return 1.
• Single mouse (w + g = 1): Alice draws it. Wins if white, loses if gray.
• Gray < 2 after Alice's draw: Bob can't draw gray, so if Alice drew gray, Bob draws white → Alice loses.
• Double counting: The escape step reduces total by 3. Ensure w, g don't go negative.

🎯 More Card & Number Game Problems

Beyond the five core problems above, here are additional card and number game problems that test similar concepts:

🎯 Interview Cheat Sheet

📝 Key Takeaways

1. Bitmask DP (Can I Win) — 2²⁰ states at most, mask tracks used items, memoize for speed
2. Expression Trees (24 Game) — Pick 2 numbers, apply operator, recurse; use epsilon for division
3. Sliding Window DP (New 21 Game) — Probability averages → maintain running window sum
4. Optimal Play DP (Flower Game) — dp[i][j] = max(nums[i] − dp[i+1][j], nums[j] − dp[i][j−1])
5. Recursive Probability (Bag of Mice) — Immediate win + recursive expectation with memoization
6. Difference scoring elegantly handles two-player zero-sum games without tracking turns
7. Look for mathematical shortcuts — parity, divisibility, closed-form solutions
8. State space is everything — define it clearly before writing any code
9. Practice! — The only way this becomes intuitive is by solving problems. The Playground is your dojo 🥋