Closest Dessert Cost

Closest Dessert Cost

What is this problem about?

The Closest Dessert Cost interview question involves a chef making a dessert with one base and multiple optional toppings. You are given the costs of various bases and toppings, and a target price. You must choose exactly one base and any number of toppings (at most two of each kind) to reach a total cost as close to the target as possible. If there's a tie, you should pick the lower cost.

Why is this asked in interviews?

This Backtracking interview pattern is popular at Google. It tests your ability to explore a search space with constraints. It’s a variation of the knapsack or subset-sum problem but with a specific "at most two of each" rule. Interviewers look for how you prune the search (e.g., if you're already way over the target, stop adding toppings) and how you handle the "lower cost on tie" requirement.

Algorithmic pattern used

The problem is best solved using Backtracking or Recursion. You can think of it as a decision tree: for each topping, do you add zero, one, or two of it? Since the number of toppings is usually small, the search space is manageable. Alternatively, it can be modeled as Dynamic Programming, specifically a variation of the "Change Making" or "Bounded Knapsack" problem.

Example explanation

Target: 10 Bases: [5, 7] Toppings: [2, 3]

1. Start with base 5.
2. Branch 1: Add zero toppings. Cost = 5.
3. Branch 2: Add one topping of cost 2. Cost = 7.
4. Branch 3: Add two toppings of cost 2. Cost = 9.
5. Branch 4: Add one topping of cost 3. Cost = 8.
6. Branch 5: Add one 2 and one 3. Cost = 10 (Perfect match!). ...and so on. The algorithm keeps track of the cost that minimizes abs(cost - target).

Common mistakes candidates make

• Choosing multiple bases: The rule is exactly one base.
• Topping limits: Forgetting that you can use each topping up to two times.
• Tie-breaking: Returning a higher cost that is equally close to the target instead of the lower one.
• Infinite recursion: Not having a proper stopping condition for the backtracking.

Interview preparation tip

When dealing with "closest value" problems with backtracking, always pass the current best cost as a reference or global variable to prune branches that have no hope of improving the current result.