Katkat
Back

Maximize score in 15-sum card game

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to use memoized recursion or dynamic programming to explore state spaces in a combinatorial game where you must decide which cards to remove to maximize your total score.

Problem Statement

You are given a list of n cards, where each card has an integer value. In each turn, you must pick exactly three cards from the current set whose values sum up to exactly 15. When you pick these three cards, you remove them from the set and gain 1 point. The game continues until you can no longer find any triplet that sums to 15.

Write a function max_score(cards) that returns the maximum number of points (triplets) you can obtain from the given list of cards.

Function Signature

def max_score(cards: List[int]) -> int:

Constraints

  • n (number of cards) is between 0 and 50.
  • Card values are between 1 and 14.
  • Time limit: 1 second.

Examples

Example 1: Input: cards = [5, 5, 5, 10, 10, 10] Output: 2 Explanation: You can form one triplet (5, 5, 5) and one triplet (10, 10, 10).

Example 2: Input: cards = [1, 2, 3, 4, 14, 13] Output: 0 Explanation: No triplet sums to 15.

Edge Cases

  • Empty list or fewer than 3 cards: Should return 0.
  • Multiple combinations possible: Ensure you choose the path that yields the maximum total triplets.

Hints

Hint 1

Since the number of cards is small (up to 50), consider representing the current state of available cards using a frequency map or a sorted tuple.

Hint 2

Use recursion with memoization to store the results of states you have already processed to avoid redundant calculations.

Hint 3

In each recursive step, iterate through all possible triplets in the current collection that sum to 15 and recurse on the remaining cards.

Follow-up questions

  • How would your approach change if you were allowed to pick *any* number of cards that sum to exactly 15?
  • What is the time complexity of your solution, and how does the state space size limit the input constraints?
  • If the card values could be much larger (e.g., up to 1000) and the target sum was also larger, would dynamic programming still be the most efficient approach?