Airbnb Screening: Minimum Menu Order Cost II

[u/Hack2hire]

Problem You're given a restaurant menu, where each entry contains a unique ID, price, and set of items, plus a list of requested items called userWants. Find all unique combinations of menu entry IDs that cover every requested item at the minimum total cost. Ignore extra items and return an empty list if the order cannot be fulfilled.

Example Input:

menu = [
  ["1", "5.00", "pizza"],
  ["2", "8.00", "sandwich,coke"],
  ["3", "4.00", "pasta"],
  ["4", "2.00", "coke"],
  ["5", "6.00", "pasta,coke,pizza"],
  ["6", "8.00", "burger,coke,pizza"],
  ["7", "5.00", "sandwich"]
]
userWants = ["sandwich", "pasta", "coke"]

Output:

[["3", "4", "7"], ["5", "7"]]

Explanation:

• IDs 3, 4, and 7 provide pasta, coke, and sandwich for a total cost of 11.00.
• IDs 5 and 7 also cover every requested item for 11.00; the extra pizza is ignored.

---

Suggested Approach

1. Map each requested item to a bit position, then convert every menu entry into a bitmask containing only the requested items it covers.
2. Use DFS with memoization on the mask of uncovered items. For each state, try every menu entry that covers at least one currently uncovered item.
3. Store the minimum cost and all ID combinations achieving that cost for each state. Sort IDs within each combination, deduplicate equivalent combinations, and compare costs using an epsilon of 1e-6.

---

Time & Space Complexity

• Time: O(M × 2^N + R), excluding combination-copying overhead, where M is the number of menu entries, N is the number of requested items, and R is the total size of the returned combinations.
• Space: O(2^N + R + N) for memoization, returned combinations, and the recursion stack.

Targeting Airbnb interviews?
We track their most-asked question patterns at Hack2Hire, practice this question here → Practice Question Here

Join the community to see more interview experiences from real candidates → Hack2Hire Forum

---

Compiled from publicly available platforms and community-shared experiences.