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

Q: What difficulty level is this coding question?

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

Q: What role is this question designed for?

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

Question

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.

PracHub · Accepted Answer

def solution(packages, required):
    normalized_required = []
    seen = set()
    for name in required:
        key = str(name).lower()
        if key not in seen:
            seen.add(key)
            normalized_required.append(key)

s = len(normalized_required)
    bit_index = {name: i for i, name in enumerate(normalized_required)}

n = len(packages)
    masks = [0] * n
    prices = [0] * n

for i, (services, price) in enumerate(packages):
        prices[i] = price
        mask = 0
        local_seen = set()
        for service in services:
            key = str(service).lower()
            if key in bit_index and key not in local_seen:
                mask |= 1 << bit_index[key]
                local_seen.add(key)
        masks[i] = mask

full_mask = (1 << s) - 1
    INF = 10 ** 18
    dp = [[INF] * (1 << s) for _ in range(n + 1)]
    dp[n][0] = 0

for i in range(n - 1, -1, -1):
        pkg_mask = masks[i]
        price = prices[i]
        next_row = dp[i + 1]
        row = dp[i]
        for rem in range(1 << s):
            best = next_row[rem]
            new_rem = rem & ~pkg_mask
            take_cost = price + next_row[new_rem]
            if take_cost < best:
                best = take_cost
            row[rem] = best

min_cost = dp[0][full_mask]
    if min_cost >= INF:
        return (-1, [])

combos = []
    path = []

def dfs(i, rem):
        if i == n:
            if rem == 0:
                combos.append(path.copy())
            return

best = dp[i][rem]

if dp[i + 1][rem] == best:
            dfs(i + 1, rem)

new_rem = rem & ~masks[i]
        if prices[i] + dp[i + 1][new_rem] == best:
            path.append(i)
            dfs(i + 1, new_rem)
            path.pop()

dfs(0, full_mask)
    combos.sort()
    return (min_cost, combos)

Quick Overview

Examples

Solution

Hints

Quick Overview