Katkat
Back

Compute minimum-cost service cover

AirbnbSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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: (

  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.