Airbnb·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Airbnb SWE interview with a combinatorics/optimization problem that felt deceptively simple at first glance. The small constraint on distinct food types was the key unlock, and I almost missed it.

Questions Asked (1)

You're given a list of menu items where each item is a (set of foods, price) pair. Given a list of wanted foods, find the minimum total cost to acquire at least all the wanted foods by purchasing some combination of items. Return both the cost and the actual items chosen.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I spent the first few minutes trying to think of this as a greedy problem, which was a mistake.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a set cover problem where each menu item covers a subset of wanted foods at a given cost, and we need to cover all wanted foods with minimum total cost. Since set cover is NP-hard, discuss both exact solutions (e.g., DP over subsets if the number of wanted foods is small) and approximation or heuristic approaches (e.g., greedy) for larger inputs, clarifying assumptions with the interviewer.

Pro tip: Always clarify constraints first (e.g., number of wanted foods, menu size) because they determine whether an exact exponential solution is acceptable or if you need to discuss approximation trade-offs. Mention that the problem is NP-hard and that you'd use DP with bitmask when the number of wanted foods is small (≤20), otherwise a greedy set cover approximation.

1. Clarify requirements and constraints

Ask about the size of the wanted foods list, the number of menu items, whether prices are positive, and if items can be purchased multiple times. Confirm that the goal is to minimize total cost while covering all wanted foods.

2. Model as a set cover problem

Represent each menu item as a bitmask of the wanted foods it contains. The problem reduces to selecting a set of masks whose union equals the full mask, minimizing total price.

3. Choose an algorithm based on constraints

If the number of wanted foods is small (e.g., ≤20), use dynamic programming over subsets: dp[mask] = min cost to cover mask, iterating over items. Otherwise, discuss greedy set cover (repeatedly pick the item with best cost per newly covered food) and its approximation ratio.

4. Implement and track chosen items

During DP, store the last item added to each mask to reconstruct the solution. For greedy, maintain a list of selected items. Return both the minimum cost and the list of items.

5. Analyze complexity and trade-offs

DP takes O(2^F * N) time and O(2^F) space, where F is number of wanted foods and N is number of menu items. Greedy runs in O(F * N) but may not be optimal. Discuss when each is appropriate.

Key Points to Mention

The problem is equivalent to the weighted set cover problem, which is NP-hard.
Dynamic programming with bitmask is optimal when the number of wanted foods is small (e.g., ≤20).
Greedy set cover provides an H(n) approximation (harmonic number) and is practical for large inputs.
Bitmask representation efficiently handles set operations (union, intersection, complement).
Reconstruction of chosen items is possible by storing parent pointers or the last item added in DP.
Clarify whether items can be purchased multiple times; if not, it's a 0/1 set cover, which DP handles naturally.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.