Design menu DP and optimize for three items
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given a restaurant menu with n single items and m combo offers. Each single item i has a price p[i] (in cents). Each combo j specifies nonnegative quantities q[j][i] for each item and a total combo price c[j]. A customer order is a vector need[i] (nonnegative integers). You may purchase any number of single items and any number of combos, but you cannot exceed need[i] for any item. Return the minimum total cost to exactly satisfy the order. Sub-questions:
1) Describe an algorithm (e.g., DP or search with memoization), justify correctness, and analyze its time and space complexity in terms of n, the needs, and the number of offers.
2) Follow-up: If the order involves only three distinct item types (all other need[i] =
0), how would you optimize the solution beyond naive pruning? Be specific about state representation (e.g., a 3D DP/state graph), transition design, and the improved complexity.
3) What preprocessing/pruning would you apply to discard dominated or irrelevant combos/items, and how would you prove that such pruning preserves optimality?
Quick Answer: This question evaluates understanding of dynamic programming, search with memoization, multidimensional state representation, and pruning/dominance reasoning for combinatorial cost minimization under constraints.
You are given n item prices and a list of combo offers. Each offer is an array of length n+1: the first n nonnegative integers are item quantities, and the last element is the total combo price. You may purchase any number of combos and any number of single items at their unit prices but cannot exceed the required quantity of any item. Given prices and needs (an array of length n of nonnegative integers), return the minimum total cost to exactly satisfy the needs.
Constraints
- 1 <= n <= 6
- 0 <= m <= 100 (number of offers)
- 0 <= needs[i] <= 10
- 1 <= prices[i] <= 10^4
- 0 <= offer quantities and offer price <= 10^6
- Each offer is length n+1: first n entries are quantities, last is price
- No over-purchasing allowed: total bought for each item must equal needs[i]
Solution
from functools import lru_cache
def min_menu_cost(prices: list[int], offers: list[list[int]], needs: list[int]) -> int:
n = len(prices)
assert len(needs) == n, "needs must match number of prices"
# Preprocess offers: keep valid and useful ones
filtered = []
for off in offers:
if not isinstance(off, list) or len(off) != n + 1:
continue
q = tuple(max(0, int(x)) for x in off[:-1])
cost = int(off[-1])
# Skip zero-quantity offers
if all(qi == 0 for qi in q):
continue
# Offers that require more than total need in any dimension can never be used (no overbuying)
if any(q[i] > needs[i] for i in range(n)):
continue
# Prune dominated offers (no cheaper than buying items separately)
base = sum(q[i] * prices[i] for i in range(n))
if cost >= base:
continue
filtered.append((q, cost))
needs_t = tuple(needs)
@lru_cache(maxsize=None)
def dfs(state: tuple) -> int:
# Cost of buying remaining items individually
base_cost = sum(state[i] * prices[i] for i in range(n))
best = base_cost
for q, c in filtered:
# Can we apply this offer?
for i in range(n):
if q[i] > state[i]:
break
else:
next_state = tuple(state[i] - q[i] for i in range(n))
cand = c + dfs(next_state)
if cand < best:
best = cand
return best
return dfs(needs_t)
Explanation
Treat the remaining need vector as a state. The minimal cost for a state is at most the cost of buying remaining items individually. For each offer that fits the state (no coordinate becomes negative), transition to the reduced state and add the offer cost. Memoize by the state tuple to avoid recomputation. Preprocess offers to remove those that are strictly dominated by buying their items individually or that cannot be used due to exceeding any initial need; this reduces branching without affecting optimality. The number of distinct states is the product over i of (needs[i] + 1). For the three-item case, a 3D DP array over (a, b, c) can replace DFS+memo with the same transitions, offering predictable memory locality and iteration order.
Time complexity: O(m * Π_i (needs[i] + 1)), where m is the number of remaining offers after pruning. Space complexity: O(Π_i (needs[i] + 1)) for memoization, plus O(m + n) for offers and parameters.
Hints
- Think of the remaining needs as a state. Use DFS with memoization where the key is a tuple of remaining quantities.
- The base case for any state is buying all remaining items as singles.
- Prune offers that cost at least as much as buying their quantities individually, or that exceed initial needs in any dimension.
- If the order involves at most three items, a 3D DP table over the three quantities yields O((a+1)(b+1)(c+1) * m) time.