Debug and optimize a card-drawing strategy
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a simplified card game engine with unit tests. The game is played using a **table** of face-up cards; each card has an integer value.
On each turn, a player **draws exactly 3 cards from the table** (removing them from the table). A turn **scores 1 point** if the three drawn card values sum to **15**; otherwise it scores **0**. The game ends when fewer than 3 cards remain.
### Part 1 — Debugging
A unit test fails because the current `draw_three_cards()` (or equivalent) method sometimes returns cards that were **not present on the table** at the moment of drawing.
**Task:** Fix the draw method so that **all three cards are always selected from the current table state**, and the selected cards are removed from the table.
### Part 2 — Implement a naive strategy
Implement a simple baseline strategy for selecting three cards each turn.
Example of an acceptable baseline:
- Repeatedly choose **any** triple of currently available cards whose values sum to 15 (if such a triple exists); otherwise draw any three cards.
### Part 3 — Measure strategy quality by simulation
Define a way to evaluate a strategy by simulation:
- Simulate many random initial deals / shuffles.
- Compute the fraction of games where the strategy achieves a “perfect score” (i.e., scores 1 on every possible turn), and/or compute average total score.
**Task:** Implement the evaluation harness and report the metric(s).
### Part 4 — Improve the strategy
Improve the strategy to maximize total score.
**Task:** Implement an optimized strategy (e.g., search/backtracking over possible sequences of draws) that attempts to maximize total points over the whole game.
### What to clarify during the interview
If not already specified in the provided code/tests, state reasonable assumptions for:
- How the initial table is generated (deck composition, table size).
- Whether card values can repeat.
- Determinism vs randomness in drawing.
- What constitutes a “perfect score” in the test harness.
Quick Answer: This question evaluates debugging and implementation skills, combinatorial search and optimization, and the ability to design and interpret simulation-based metrics, and is commonly asked to verify correctness of stateful operations and effectiveness of different selection strategies.
Part 1: Draw Three Cards From the Current Table
You are fixing a buggy card-drawing method. The table is a list of face-up card values. A draw removes exactly 3 cards, one at a time, from the current table state. You are given the table and a list of 3 indices. Each index must be interpreted on the table after all previous removals have already happened. Return the 3 drawn card values in draw order, and the remaining table.
If the table starts with fewer than 3 cards, no draw happens and the table stays unchanged.
Assumptions for this standalone problem: card values are integers, values may repeat, and when the table has at least 3 cards, the provided indices are valid at the moment they are used.
Constraints
- 0 <= len(table) <= 100000
- len(pick_indices) = 3
- Card values may repeat
- If len(table) >= 3, each pick index is valid for the current table at the time it is applied
Examples
Input: ([4, 5, 6, 7, 8], [1, 2, 0])
Expected Output: ([5, 7, 4], [6, 8])
Explanation: Remove index 1 -> 5, then from [4,6,7,8] remove index 2 -> 7, then from [4,6,8] remove index 0 -> 4.
Input: ([10, 20, 30], [2, 1, 0])
Expected Output: ([30, 20, 10], [])
Explanation: All 3 cards are removed, leaving an empty table.
Input: ([], [0, 0, 0])
Expected Output: ([], [])
Explanation: Edge case: fewer than 3 cards means no draw occurs.
Input: ([5, 5, 5, 5], [0, 1, 1])
Expected Output: ([5, 5, 5], [5])
Explanation: Repeated values are allowed; indices are interpreted on the shrinking table.
Hints
- Do not read all three cards from the original table first; the table changes after each removal.
- Using pop on the live list naturally keeps every later pick aligned with the current table state.
Part 2: Implement a Naive 15-Sum Strategy
A table contains face-up cards represented by integers. On each turn, you must remove exactly 3 cards. That turn scores 1 point if the removed values sum to 15; otherwise it scores 0. The game ends when fewer than 3 cards remain.
Implement a deterministic baseline strategy:
1. On each turn, if there exists at least one triple of current cards whose values sum to 15, choose the triple with the lexicographically smallest index tuple (i, j, k) using the current table order.
2. Otherwise, remove the first 3 cards.
3. Repeat until fewer than 3 cards remain.
Return the list of drawn triples by value, the total score, and the remaining cards.
Values may repeat.
Constraints
- 0 <= len(table) <= 30
- Card values are integers and may repeat
- Use the current table order to break ties deterministically
Examples
Input: ([])
Expected Output: ([], 0, [])
Explanation: Edge case: no cards means no turns and no score.
Input: ([8, 1, 6])
Expected Output: ([[8, 1, 6]], 1, [])
Explanation: The only triple sums to 15.
Input: ([1, 2, 3, 4, 5, 6])
Expected Output: ([[4, 5, 6], [1, 2, 3]], 1, [])
Explanation: The lexicographically first scoring triple is at indices (3,4,5). The remaining triple does not score.
Input: ([5, 5, 5, 5, 5, 5])
Expected Output: ([[5, 5, 5], [5, 5, 5]], 2, [])
Explanation: Each turn removes a scoring triple.
Hints
- Search the current table for a valid triple before each turn; after removing cards, start over on the new table.
- When deleting 3 chosen indices from a list, remove them in descending order so earlier positions do not shift.
Part 3: Simulate and Evaluate the Naive Strategy
You must build a simulation harness for the naive strategy from Part 2.
Assumptions for this standalone problem:
- deck is a list of integer card values; values may repeat.
- For game g, create a shuffled copy of deck using random.Random(seed + g), then deal the first min(table_size, len(deck)) cards onto the table.
- Play the game using the exact naive strategy from Part 2: on each turn choose the lexicographically smallest current triple of indices that sums to 15; if none exists, remove the first 3 cards.
- A perfect score means the strategy scores on every possible turn, i.e. score == floor(initial_table_size / 3). If fewer than 3 cards are dealt, the game has 0 turns and counts as perfect.
Simulate num_games games and return:
1. average total score
2. fraction of games that are perfect
Return both numbers rounded to 4 decimal places. If num_games is 0, return (0.0, 0.0).
Constraints
- 0 <= len(deck) <= 50
- 0 <= table_size <= 50
- 0 <= num_games <= 500
- Card values are integers and may repeat
Examples
Input: ([5, 5, 5, 5, 5, 5], 6, 3, 42)
Expected Output: (2.0, 1.0)
Explanation: Every shuffled game has two scoring turns, so average score is 2 and every game is perfect.
Input: ([1, 1, 1, 1, 1, 1], 6, 4, 7)
Expected Output: (0.0, 0.0)
Explanation: No triple can ever sum to 15, so score is always 0 and no 2-turn game is perfect.
Input: ([7, 8, 5, 5, 5, 5], 6, 2, 99)
Expected Output: (1.0, 0.0)
Explanation: Each game contains exactly one scoring triple [5,5,5], so average score is 1 and no 2-turn game is perfect.
Input: ([1, 2], 6, 3, 1)
Expected Output: (0.0, 1.0)
Explanation: Only 2 cards are dealt, so each game has 0 turns. Score is 0, and every game counts as perfect.
Input: ([5, 5, 5], 3, 0, 123)
Expected Output: (0.0, 0.0)
Explanation: Edge case: zero simulations.
Hints
- Write a helper that scores one table using the deterministic naive strategy, then call it repeatedly on shuffled deals.
- A game is perfect when its score equals the number of possible turns, which is len(initial_table) // 3.
Part 4: Maximize Total Score Over the Whole Game
You are given a table of face-up cards, each with an integer value. On each turn, you must remove exactly 3 cards from the current table. That turn scores 1 point if the chosen 3 values sum to 15; otherwise it scores 0. The game ends when fewer than 3 cards remain.
Your task is to compute the maximum total score achievable over the entire game.
This is an optimization problem: a locally good triple is not always part of the best overall plan. Values may repeat.
Constraints
- 0 <= len(table) <= 18
- Card values are integers and may repeat
- You may choose any 3 currently available cards on each turn
Examples
Input: ([])
Expected Output: 0
Explanation: Edge case: no cards, so no turns.
Input: ([8, 1, 6, 5, 5, 5])
Expected Output: 2
Explanation: An optimal play scores with [8,1,6] and [5,5,5].
Input: ([1, 2, 3, 4, 5, 6])
Expected Output: 1
Explanation: Only one scoring triple can be formed.
Input: ([4, 4, 7, 8, 1, 6, 5, 5, 5])
Expected Output: 3
Explanation: The cards can be partitioned into three scoring triples: [4,4,7], [8,1,6], and [5,5,5].
Input: ([7, 8, 5, 5, 5, 5])
Expected Output: 1
Explanation: At most one scoring triple [5,5,5] is possible.
Hints
- Think of the state as the multiset of remaining cards, not the history of how you got there.
- Memoization on a sorted tuple of remaining values can avoid recomputing the same subproblems.