Shopping Offers

Shopping Offers

What is this problem about?

The Shopping Offers interview question gives you prices for individual items, a list of bundle deals (each deal trades a set of items for a fixed price), and the desired quantities of each item. Find the minimum cost to buy exactly the required quantities, using any combination of bundle deals and individual item purchases. Items cannot be bought in excess of the requirement. This is a bitmask dynamic programming / memoized backtracking problem.

Why is this asked in interviews?

Amazon, Airbnb, and Google ask this problem because it models real-world e-commerce promotional pricing — a customer should find the optimal combination of discounts and individual purchases. It tests memoized backtracking with state represented as a tuple of remaining quantities. The pruning condition (no deal can buy more than needed) makes it a practical exercise in constraint-satisfying search.

Algorithmic pattern used

The pattern is memoized DFS (backtracking + memoization). The state is the current needs tuple (remaining quantities for each item). For each state, either apply a valid bundle offer (if it doesn't exceed any item's need) or fall back to buying all remaining items individually. Cache dp[needs] = minimum cost for that need state. Transition: for each offer, if valid, recurse with needs - offer_quantities and add offer_price. Base case: needs = [0, 0, ..., 0] → cost = 0. The individual-purchase cost for any state is sum(needs[i] * price[i]).

Example explanation

prices = [2, 5], offers = [[3, 0, 5], [1, 2, 10]], needs = [3, 2].

• Apply offer [3,0,5]: needs becomes [0,2]. Apply offer [1,2,10]: needs [0,2] → can't (needs 1 of item 0). Buy individually: 0×2 + 2×5 = 10. Total: 5+10=15.
• Apply offer [1,2,10]: needs becomes [2,0]. Buy individually: 2×2 + 0×5 = 4. Total: 10+4=14.
• Buy individually: 3×2 + 2×5 = 16.

Minimum: 14.

Common mistakes candidates make

• Applying an offer that would cause any item quantity to go negative — always validate the offer doesn't exceed needs.
• Not memoizing the needs state — without caching, repeated sub-problems cause exponential time.
• Forgetting the base case fallback (individual item purchases) as a valid option at every state.
• Using a list instead of a tuple as the memoization key — lists are not hashable in Python.

Interview preparation tip

For the Shopping Offers coding problem, the dynamic programming bitmask memoization interview pattern is the clean approach. The key insight: represent remaining needs as an immutable tuple for memoization. Amazon and Airbnb interviewers appreciate that you validate offer applicability before recursing. Practice the "offer-or-individual" branching structure — it also appears in coin change variants where different denomination combinations lead to the same subproblem.