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?
Overview: 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]
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.
Community answers
Answer by psiinyou
package dsa;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ShoppingOffers {
public int shoppingOffers(int[] price, int[][] offers, int[] needs){
Map memo = new HashMap<>();
return dfs(price, offers, needs, memo);
}
int dfs(int[] price, int[][] offers, int[] needs, Map memo){
if(memo.containsKey(needs))
return memo.get(needs);
int minCost = 0;
for(int i = 0; i < needs.length; i++){
minCost += needs[i] * price[i];
}
for(int[] offer : offers){
if(isValid(offer, needs)){
int[] nextNeeds = new int[needs.length];
for(int i = 0; i < needs.length; i++){
nextNeeds[i] = needs[i] - offer[i];
}
int costWithOffer = offer[needs.length] + dfs(price, offers, nextNeeds, memo);
minCost = Math.min(minCost, costWithOffer);
}
}
memo.put(needs, minCost);
return minCost;
}
boolean isValid(int[] offer , int[] needs){
for(int i = 0; i < needs.length; i++){
if(offer[i] > needs[i])
return false;
}
return true;
}
public static void main(String[] args) {
System.out.println("Running Shopping Offers Test Cases...\n");
// Test Case 1: Standard case (LeetCode example 1)
int[] price1 = {2, 5};
int[][] special1 = {
{3, 0, 5},
{1, 2, 10}
};
int[] needs1 = {3, 2};
System.out.println("Test Case 1 Expected: 14");
// Test Case 2: Over-purchasing is strictly forbidden
int[] price2 = {2, 3, 4};
int[][] special2 = {
{1, 1, 0, 4},
{2, 2, 1, 9}
};
int[] needs2 = {1, 2, 1};
System.out.println("Test Case 2 Expected: 11");
// Test Case 3: Offers are worse than
Answer by AS12
function shoppingOffers(price, special, needs) {
const dp = new Map();
function dfs(currNeeds){
const key = currNeeds.join(",");
if(dp.has(key)) return dp.get(key);
let minCost = 0;
let newNeeds = [];
for(let i =0; i< price.length; i++){
minCost+= price[i]*currNeeds[i];
}
for(let offer of special){
let valid = true;
for(let i=0; i currNeeds[i]){
valid = false;
break;
}
newNeeds[i] = currNeeds[i]-offer[i]
}
if(!valid) continue;
console.log('newNeeds', newNeeds)
let offerPrice = offer[price.length];
let costWithOffer = offerPrice + dfs(newNeeds);
minCost = Math.min(minCost, costWithOffer);
}
dp.set(key, minCost);
return minCost;
}
return dfs(needs);
}
var price = [2,5], offers = [[3,0,5],[1,2,10]], needs = [3,2]
shoppingOffers(price, offers, needs)
Answer by leni
import math
def min_menu_cost(prices: list[int], offers: list[list[int]], needs: list[int]) -> int:
enhanced_offers = offers[:]
for pos, price in enumerate(prices):
offer = [0] * (len(needs) + 1)
offer[pos] = 1
offer[-1] = price
enhanced_offers.append(offer)
def dfs(needs) -> int:
if sum(needs) == 0:
return 0
min_offers = math.inf
for offer in enhanced_offers:
valid_offer = True
for pos, item_left in enumerate(needs):
if offer[pos] - item_left > 0:
valid_offer = False
break
if valid_offer:
next_needs = [y - x for (x,y) in zip(offer[:-1], needs)]
offers = offer[-1] + dfs(next_needs)
min_offers = min(offers, min_offers)
return min_offers
return dfs(needs)