How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Airbnb.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Compute minimum-cost service cover | Airbnb Coding Question

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.

Input: ([(["a"], 5), (["b"], 5), (["a", "b"], 10)], ["A", "B"])

Expected Output: (10, [[0, 1], [2]])

Explanation: Either buy packages 0 and 1 for 10 total, or package 2 alone for 10. Both are optimal.

Input: ([(["wifi"], 50)], [])

Expected Output: (0, [[]])

Explanation: No services are required, so the minimum cost is 0 and the empty combination is optimal.

Input: ([(["WiFi", "wifi"], 10), (["PARKING"], 20), (["wifi", "parking"], 40)], ["wifi", "WiFi", "Parking"])

Expected Output: (30, [[0, 1]])

Explanation: Required services normalize to wifi and parking. Package 0 covers wifi for 10, package 1 covers parking for 20, so the best total is 30.

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.

Quick Overview

This question evaluates proficiency in combinatorial optimization and set-coverage with cost minimization, including handling case-insensitive service matching and enumerating minimal solution combinations.