Solve and optimize menu combo DP
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given up to N different menu items, each with a unit price, and a list of combo offers where each offer specifies quantities for some items and a total combo price, write an algorithm that, given the required quantities for each item, returns the minimum cost to satisfy the order without buying extra items. Describe and implement a dynamic programming or memoized search solution, stating the state definition, transitions, and base cases. Analyze time and space complexity in terms of N (item types), Q (maximum needed quantity per item), and S (number of offers). Follow-up: When N = 3, propose and implement an optimization that leverages a fixed 3D state (i, j, k) to reduce overhead; explain any preprocessing such as pruning dominated or irrelevant offers and capping offer counts to needs; provide the resulting complexity. Discuss additional practical optimizations such as skipping offers that exceed current needs or reordering states to enable bottom-up computation.
Quick Answer: This question evaluates dynamic programming and combinatorial optimization skills, focusing on state definition, transitions, memoization, pruning dominated offers, and minimizing state space for menu-combo minimum-cost problems in the domain of Coding & Algorithms.
You are given N item types with unit prices, a list of S combo offers, and the required quantities (needs) for each item. Each offer is a list of length N+1 where the first N entries are quantities for each item and the last entry is the total offer price. Compute the minimum total cost to satisfy the needs exactly (no extra items allowed). You may use an offer multiple times as long as it never causes any item's purchased quantity to exceed its remaining need.
Constraints
- 1 <= N <= 6
- 0 <= S <= 100
- 0 <= needs[i] <= 10
- 1 <= prices[i] <= 10^4
- Each offer is length N+1: first N non-negative integers are quantities, last is offer price (0 <= offer price <= 10^5)
- No extra items allowed: an offer can be applied only if all its quantities are <= the remaining needs
- All inputs are integers
Solution
from functools import lru_cache
from typing import List, Tuple
def min_order_cost(prices: List[int], offers: List[List[int]], needs: List[int]) -> int:
n = len(prices)
if n != len(needs):
raise ValueError("prices and needs length mismatch")
# Prune offers: wrong length, zero-quantity, exceeds needs, or not cheaper than individual
pruned: List[Tuple[Tuple[int, ...], int]] = []
for off in offers:
if len(off) != n + 1:
continue
qty = off[:-1]
cost = off[-1]
if all(q == 0 for q in qty):
continue
if any(q > needs[i] for i, q in enumerate(qty)):
continue
indiv = sum(prices[i] * qty[i] for i in range(n))
if cost >= indiv:
continue
pruned.append((tuple(qty), cost))
# Specialized bottom-up DP when N == 3
if n == 3:
a, b, c = needs
INF = 10**18
dp = [[[INF for _ in range(c + 1)] for _ in range(b + 1)] for __ in range(a + 1)]
for i in range(a + 1):
for j in range(b + 1):
for k in range(c + 1):
# baseline: buy individually
best = i * prices[0] + j * prices[1] + k * prices[2]
# try offers
for qty, ocost in pruned:
if i >= qty[0] and j >= qty[1] and k >= qty[2]:
cand = dp[i - qty[0]][j - qty[1]][k - qty[2]] + ocost
if cand < best:
best = cand
dp[i][j][k] = best
return dp[a][b][c]
# General N: top-down memoized DFS
@lru_cache(maxsize=None)
def dfs(state: Tuple[int, ...]) -> int:
# baseline: buy what's left individually
total = sum(state[i] * prices[i] for i in range(n))
# try each offer
for qty, ocost in pruned:
ok = True
nxt = [0] * n
for i in range(n):
if qty[i] > state[i]:
ok = False
break
nxt[i] = state[i] - qty[i]
if ok:
cand = ocost + dfs(tuple(nxt))
if cand < total:
total = cand
return total
return dfs(tuple(needs))
Explanation
State: remaining needs vector. Base cost for any state is buying remaining items individually. Transition: for each offer whose quantities do not exceed the current state, apply it once and recurse on the reduced state, taking the minimum over all choices. Pruning removes offers that are never helpful: ones exceeding overall needs, zero-quantity offers, and offers not cheaper than buying those quantities individually. For N=3, a bottom-up 3D DP with dimensions (a+1)*(b+1)*(c+1) initializes each cell with individual-buy cost and relaxes with applicable offers, enabling faster iteration and lower overhead compared to recursive memoization.
Time complexity: O(S * Π_i (needs[i] + 1)) in the general case; for N = 3, O(S * (needs[0]+1)*(needs[1]+1)*(needs[2]+1)).. Space complexity: O(Π_i (needs[i] + 1)) for memoization/DP table; plus O(S) for pruned offers..
Hints
- Model the state as the remaining needs vector; use memoization with the state as a tuple.
- Baseline for any state: buy remaining items individually; try applying each valid offer to reduce the state.
- Prune offers whose price is >= the cost of buying their quantities individually, and offers that have any quantity exceeding needs.
- For N=3, build a bottom-up 3D DP of size (needs[0]+1)*(needs[1]+1)*(needs[2]+1), initializing with individual-buy costs and relaxing with offers.
- Skip offers that exceed current remaining needs to enforce the no-extras rule.