Compute minimum-cost service cover

Q: Compute minimum-cost service cover

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

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given: (

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

Compute minimum-cost service cover

Overview

Comments (0)