How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Optimize a Fifteen-Sum Card Strategy

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given a simulator for a card game with 36 cards: ranks `1` through `9` in four suits. The table starts with 16 random cards. A move removes any 3 table cards whose numeric values sum to 15 and scores 15 points. After a move, the simulator draws up to 3 replacement cards from the remaining deck. The game ends when no valid triple remains or no further progress is possible. A perfect game scores 180 points. Starting from an existing codebase and tests, complete the following tasks: 1. Fix a bug in the draw logic so the game only removes cards that are actually on the current table. 2. Implement a simple baseline strategy that picks any valid triple summing to 15. 3. Add an experiment or unit test that simulates many games and reports how often the strategy achieves a perfect score. 4. Implement a stronger strategy using search, memoization, or dynamic programming to maximize total score. Assume the strategy can see the current table and knows the deck composition, but it does not know the future random draw order.

Quick Answer: This question evaluates algorithmic problem-solving, debugging, simulation-based testing, and strategy optimization using techniques such as search, memoization, and dynamic programming in a combinatorial card game context.

Part 1: Safe Triple Removal in a Fifteen-Sum Move

You are given the current `table`, a requested `triple`, and the remaining `deck` in draw order. Perform exactly one move of the fifteen-sum game. A move is valid only if the requested triple has exactly 3 cards, its values sum to 15, and the current table contains enough copies of each requested value. If valid, remove one occurrence of each triple value from the table while preserving the order of the remaining cards, then draw up to 3 replacement cards from the front of the deck and append them to the table. Return the new table, the new deck, and the points scored. If the move is invalid, return the original table and deck unchanged with 0 points.

Constraints

0 <= len(table), len(deck) <= 50
Card values are integers in the range 1 to 9
A valid move must remove exactly 3 cards from the current table

Examples

Input: ([1, 5, 9, 2, 4, 6], [1, 5, 9], [3, 7])

Expected Output: ([2, 4, 6, 3, 7], [], 15)

Explanation: A valid triple is removed, and only two cards are drawn because the deck has two cards left.

Input: ([5, 5, 1, 4, 9], [5, 5, 5], [2, 3, 4])

Expected Output: ([5, 5, 1, 4, 9], [2, 3, 4], 0)

Explanation: The table has only two 5s, so the move is invalid and nothing changes.

Input: ([8, 4, 3, 7], [8, 4, 3], [])

Expected Output: ([7], [], 15)

Explanation: The move is valid, but the deck is empty so no replacement cards are drawn.

Input: ([1, 2, 3], [1, 2, 3], [4])

Expected Output: ([1, 2, 3], [4], 0)

Explanation: The requested cards sum to 6, not 15, so the move is invalid.

Hints

Treat the table and the requested triple as multisets, especially when duplicate values appear.
Validate the move before removing anything, then remove only as many copies as the triple actually needs.

Part 2: Baseline Strategy for Choosing a Fifteen-Sum Triple

Given the current `table` of card values, implement a simple baseline strategy that picks any valid triple whose values sum to 15. To make the result deterministic for testing, return the first valid triple of indices `(i, j, k)` found by scanning in increasing index order with `i < j < k`. If no valid triple exists, return `None`.

Constraints

0 <= len(table) <= 50
Card values are integers in the range 1 to 9

Examples

Input: [1, 5, 9, 2, 4]

Expected Output: (0, 1, 2)

Explanation: The first scanned triple already sums to 15.

Input: [5, 5, 5]

Expected Output: (0, 1, 2)

Explanation: Duplicates are allowed as long as they come from different positions.

Input: [1, 2, 3, 4]

Expected Output: None

Explanation: No triple on the table sums to 15.

Input: []

Expected Output: None

Explanation: Edge case: an empty table has no valid move.

Hints

The table is small enough that checking all 3-card combinations is acceptable.
Use three nested loops with `i < j < k` so the first match is deterministic.

Part 3: Count Perfect Games in a Baseline Strategy Experiment

You are building a deterministic test harness for the fifteen-sum strategy. Each game is given as a pair `(table, deck)`, where `table` is the starting table and `deck` is the remaining draw pile in fixed front-to-back order. Repeatedly apply the baseline strategy from Part 2: find the first triple of table positions whose values sum to 15, remove those cards, then draw up to 3 cards from the front of the deck. The game ends when no valid triple remains. A game is considered perfect if all cards from both the table and the deck have been removed by the end. Given many game instances, return how many are perfect.

Constraints

0 <= len(games) <= 200
For each game, 0 <= len(table) + len(deck) <= 36
Card values are integers in the range 1 to 9

Examples

Input: [([1, 5, 9], []), ([1, 2, 3], [])]

Expected Output: 1

Explanation: Only the first game clears all cards.

Input: [([1, 5, 9], [2, 4, 9]), ([1, 5, 9, 2], [])]

Expected Output: 1

Explanation: The first game clears in two moves; the second leaves one card behind.

Input: []

Expected Output: 0

Explanation: No games means no perfect games.

Input: [([], []), ([], [1, 2, 3]), ([5, 5, 5], [])]

Expected Output: 2

Explanation: The empty-empty game and the all-5s game are perfect; the empty-table game with a leftover deck is not.

Hints

Write a helper that simulates one full game using the same first-valid-triple rule every turn.
A game is perfect only if both the table and the deck are empty at the end.

Part 4: Maximize Fifteen-Sum Score with Search and Memoization

In this deterministic optimization variant, the remaining `deck` order is known. Starting from the current `table` and `deck`, you may choose any valid triple of table cards whose values sum to 15. Each move scores 15 points, removes those 3 cards, and then draws up to 3 cards from the front of the deck. Continue until no valid move remains. Return the maximum total score that can be achieved. A strong solution should use search with memoization or dynamic programming.

Constraints

0 <= len(table) + len(deck) <= 20
Card values are integers in the range 1 to 9
Each move must remove exactly 3 table cards summing to 15

Examples

Input: ([1, 5, 9], [])

Expected Output: 15

Explanation: One move is possible.

Input: ([1, 2, 3], [])

Expected Output: 0

Explanation: No valid triple exists.

Input: ([1, 5, 9], [2, 4, 9])

Expected Output: 30

Explanation: The first move draws another valid triple, giving two moves total.

Input: ([1, 5, 9, 2, 4], [5, 8, 8])

Expected Output: 30

Explanation: Choosing 1+5+9 leads to another move, while choosing 2+4+9 does not.

Input: ([], [])

Expected Output: 0

Explanation: Edge case: no cards means no score.

Hints

Try every valid triple from the current table, and recurse on the resulting state.
Memoize by game state. Since only card values matter for future sums, sorting the table can merge equivalent states.

Quick Overview

This question evaluates algorithmic problem-solving, debugging, simulation-based testing, and strategy optimization using techniques such as search, memoization, and dynamic programming in a combinatorial card game context.