Find minimal property set in neighborhood

Quick Overview

This question evaluates combinatorial optimization and algorithm design skills, focusing on capacity-constrained selection (subset-sum/knapsack-style reasoning), deterministic tie-breaking, and complexity analysis within the Coding & Algorithms domain.

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of properties, each Property(id: int, neighborhood: string, capacity: int). Given a targetNeighborhood (string) and groupSize (int), return the IDs of a combination of properties drawn only from targetNeighborhood such that: - the total capacity is at least groupSize; - among all feasible combinations, the number of selected properties is minimized; - if multiple combinations have the same minimal count, choose one whose total capacity is minimal (i.e., as close to groupSize as possible above it); - if no feasible combination exists, return []. Specify and implement an optimal algorithm. Describe: 1) the approach and data structures, 2) time and space complexity, 3) how you handle ties deterministically (e.g., smallest total capacity, then lexicographically smallest ID list), 4) edge cases (e.g., duplicate capacities/IDs, very large inputs). Example input: Properties = [ Property(1, "downtown", 5), Property(2, "downtown", 3), Property(3, "downtown", 1), Property(4, "uptown", 4), Property(5, "uptown", 2) ] targetNeighborhood = "downtown" - groupSize = 6 -> one valid answer is [1, 3] - groupSize = 3 -> [2] - groupSize = 16 -> [] Note: With targetNeighborhood = "downtown" and groupSize = 10, no solution exists because the capacities of downtown properties sum to 9.

Overview: This question evaluates combinatorial optimization and algorithm design skills, focusing on capacity-constrained selection (subset-sum/knapsack-style reasoning), deterministic tie-breaking, and complexity analysis within the Coding & Algorithms domain.

Given a list of properties represented as tuples (id, neighborhood, capacity), choose a subset using only properties whose neighborhood equals targetNeighborhood. Return the selected property IDs in ascending order so that: 1. the total capacity is at least groupSize; 2. the number of selected properties is minimized; 3. if several subsets use the same minimum number of properties, choose the one with the smallest total capacity; 4. if there is still a tie, choose the lexicographically smallest ID list. If no feasible subset exists, return []. Duplicate capacities are allowed. IDs are unique in valid input because the answer is returned as IDs. If groupSize <= 0, return []. An exact algorithm is expected under the provided constraints.

Constraints

0 <= len(properties) <= 200
Each property is a tuple (id, neighborhood, capacity)
IDs are unique integers; duplicate capacities are allowed
1 <= capacity <= 1000
0 <= groupSize <= 20000
The sum of capacities of properties in targetNeighborhood is at most 20000

Examples

Input: ([(1, "downtown", 5), (2, "downtown", 3), (3, "downtown", 1), (4, "uptown", 4), (5, "uptown", 2)], "downtown", 6)

Expected Output: [1, 3]

Explanation: No single downtown property reaches 6. Both [1, 2] and [1, 3] use 2 properties, but [1, 3] has smaller total capacity: 6 instead of 8.

Input: ([(1, "downtown", 5), (2, "downtown", 3), (3, "downtown", 1), (4, "uptown", 4), (5, "uptown", 2)], "downtown", 3)

Expected Output: [2]

Explanation: Property 2 alone reaches the target, so 1 property is optimal.

Hints

This is a 0/1 knapsack or subset-sum variant: exact sums matter because two solutions with the same number of properties can overshoot by different amounts.
After you know the optimal count and exact total capacity, sort the matching properties by ID and reconstruct greedily to get the lexicographically smallest valid ID list.

Approach

This is an exact DP that solves a layered optimization over a subset-sum problem.

Setup. If groupSize <= 0, return []. Otherwise keep only properties whose neighborhood equals targetNeighborhood, reducing each to (id, capacity). If none remain, or the total capacity is below groupSize, the target is unreachable → []. The items are sorted by ID, which is the key trick: it makes both the final ascending order and the lexicographic tie-break fall out of a left-to-right greedy reconstruction.

Bounding the DP. A clever bound caps the sums we track at limit = min(total, groupSize + maxCapacity − 1). Reason: in any minimum-cardinality solution, dropping any chosen property must break feasibility, so the optimal total T satisfies T < groupSize + maxCapacity. We never need sums beyond that.

Suffix DP. suf[i][s] = the minimum number of properties drawn from items[i:] that hit an exact sum s (or inf). It's built backward: suf[i] copies suf[i+1] (skip item i), then for each s tries taking item i: suf[i+1][s − cap] + 1. Using array('H') keeps each row compact.

Choosing the answer. Scan s from groupSize to limit and pick the (count, sum) with the fewest properties first, then the smallest qualifying sum (the first improving count found per increasing s naturally yields the smallest sum for that minimal count).

Reconstruction. Walk items in ID order; take item i whenever suf[i+1][remaining − cap] + 1 == remaining_count, i.e. it still lies on an optimal path. Greedily taking the smallest available ID gives the lexicographically smallest ID list. Correct by construction.

Time complexity:

O(n * L), where n is the number of properties in the target neighborhood and L = min(totalCapacity, groupSize + maxCapacity - 1). The suffix DP fills n+1 rows, each via a single pass over [0, L].

Space complexity:

O(n * L). All n+1 DP rows of width L+1 are retained (as compact array('H') rows) because the final greedy reconstruction needs every suf[i+1] layer.