Maximize Cards Bought Within a Budget

Reported in interviews at Citadel

Problem statement

You are buying birthday cards for a friend. Each card has a printed number that equals its cost. You only want to give cards the recipient does not already own, and you have a fixed budget. You want to give as many cards as possible -- you are maximizing the count of new cards, not their total value.

Given the list all_costs of every card's cost, the list owned of cards the recipient already has, and an integer budget, return the maximum number of not-yet-owned cards you can buy without exceeding the budget. Cards are identified by their printed number: if a number appears in owned, every card with that number in all_costs is excluded, while repeated numbers not in owned are separate cards that can each be bought.

Complete:

def maxCards(all_costs: list[int], owned: list[int], budget: int) -> int:

Constraints:

  • $1 \le \text{len(all\_costs)} \le 10^5$, costs are positive integers.
  • $0 \le \text{budget} \le 10^9$.

Examples:

  • all_costs = [2, 5, 1, 8], owned = [5], budget = 4 -> available costs are [1, 2, 8]; buy 1 then 2 (total 3), cannot afford 8, so the answer is 2.
  • all_costs = [3, 3, 7], owned = [], budget = 6 -> buy both 3s, the answer is 2.
  • all_costs = [10, 20], owned = [10, 20], budget = 100 -> nothing is available, the answer is 0.
Show hint

When the goal is the number of items rather than their total worth, which items does a budget stretch furthest on?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems