Compute minimum-cost service cover
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given:
(
1) a list of rental service packages, where each package contains a set of services (strings) and a non-negative price, e.g., [(["wifi"],
50), (["parking"],
30), (["parking", "tv"],
70)]; and
(
2) a list of required services, e.g., ["WiFi", "parking"]. Design and implement an algorithm that returns
(a) the minimum total cost to cover all required services (treat service names case-insensitively), and
(b) the combination
(s) of package indices that achieve this minimum. Define the output as: min_cost: int and combos: List[List[int]] where each inner list is a strictly increasing list of package indices; if coverage is impossible, return (-1, []). Explain and analyze your approach, including time and space complexity in terms of N (packages) and S (distinct required services). Describe how you will reconstruct the optimal combination
(s) from your DP/bitmask state; handle ties and avoid duplicate combinations. Provide tests for the example above and at least one case with no feasible cover.
Quick Answer: This question evaluates proficiency in combinatorial optimization and set-coverage with cost minimization, including handling case-insensitive service matching and enumerating minimal solution combinations.
You are given a list of rental service packages and a list of required services. Each package is a pair (services, price), where services is a list of service names and price is a non-negative integer. Service names must be treated case-insensitively.
Write a function that returns all minimum-cost ways to cover every distinct required service.
Return a tuple (min_cost, combos):
- min_cost: the minimum total price needed to cover all required services
- combos: a list of package-index combinations that achieve min_cost
Rules:
- Package indices are 0-based.
- Each combo must be a strictly increasing list of indices.
- If multiple optimal combos exist, return all of them.
- Do not return duplicate combos.
- Ignore services in packages that are not required.
- If coverage is impossible, return (-1, []).
- For deterministic output, return combos sorted lexicographically.
A strong solution should use DP with bitmasking over the distinct required services, then reconstruct all optimal combinations by following only transitions that preserve the optimal cost.
Constraints
- 0 <= N <= 30, where N is the number of packages
- 0 <= price <= 10^6 for each package
- 0 <= S <= 15, where S is the number of distinct required services after case-insensitive normalization
- The number of optimal combinations can be exponential in N, so reconstruction is inherently output-sensitive
Examples
Input: ([(["wifi"], 50), (["parking"], 30), (["parking", "tv"], 70)], ["WiFi", "parking"])
Expected Output: (80, [[0, 1]])
Explanation: Package 0 covers wifi and package 1 covers parking for a total of 80. Package 2 does not include wifi, so using it with package 0 costs 120 and is not optimal.
Input: ([(["wifi"], 50), (["tv"], 20)], ["wifi", "parking"])
Expected Output: (-1, [])
Explanation: No package provides parking, so it is impossible to cover all required services.
Hints
- Map each distinct required service to a bit position. Then each package becomes a bitmask showing which required services it covers.
- Use DP on (package_index, remaining_services_mask) to compute the minimum cost, then run a DFS that follows only transitions whose cost matches the DP optimum to reconstruct all optimal combos.