Find Optimal Property Combination
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are building a reservation-matching system for short-term rentals.
Each property has:
- `id`: a unique identifier
- `neighborhood`: the neighborhood where the property is located
- `capacity`: the maximum number of guests it can host
Given a list of properties, a target `neighborhood`, and a `groupSize`, choose a subset of properties in that neighborhood that can accommodate the group.
A valid subset must have total capacity `>= groupSize`.
Among all valid subsets, return the best subset using these priorities, in order:
1. Minimize the total selected capacity.
2. If multiple subsets have the same total capacity, choose the subset with the fewest properties.
3. If there is still a tie, any one of the tied subsets may be returned.
If no valid subset exists, return an empty result.
Example:
```text
properties = [
{id: "A", neighborhood: "SoMa", capacity: 2},
{id: "B", neighborhood: "SoMa", capacity: 4},
{id: "C", neighborhood: "SoMa", capacity: 5},
{id: "D", neighborhood: "Mission", capacity: 10}
]
neighborhood = "SoMa"
groupSize = 6
```
Valid subsets include:
- `[A, B]` with total capacity `6`
- `[A, C]` with total capacity `7`
- `[B, C]` with total capacity `9`
- `[A, B, C]` with total capacity `11`
The best answer is `[A, B]` because it satisfies the group exactly with the minimum total capacity.
Implement a function that returns the selected property IDs or property objects.
Quick Answer: This question evaluates combinatorial optimization and algorithmic problem-solving skills, focusing on subset selection under capacity constraints and prioritization via multiple tie-breaking criteria.
You are building a reservation-matching system for short-term rentals. Each property is represented as a tuple `(id, neighborhood, capacity)`. Given a list of properties, a target `neighborhood`, and a `groupSize`, choose a subset of properties from that neighborhood whose total capacity is at least `groupSize`. Among all valid subsets, return the one that: (1) has the minimum total capacity, (2) uses the fewest properties if total capacity is tied. If no valid subset exists, return an empty list. Return the selected property IDs in the same order they appear in the input.
Constraints
- 0 <= len(properties) <= 80
- Each property capacity is an integer in the range 1 to 1000
- 1 <= groupSize <= 20000
- The sum of capacities of properties in the target neighborhood is at most 20000
Examples
Input: ([('A', 'SoMa', 2), ('B', 'SoMa', 4), ('C', 'SoMa', 5), ('D', 'Mission', 10)], 'SoMa', 6)
Expected Output: ['A', 'B']
Explanation: The subset ['A', 'B'] has total capacity 6, which exactly matches the group size and is therefore the minimum possible valid total.
Input: ([('P1', 'Downtown', 2), ('P2', 'Downtown', 2), ('P3', 'Downtown', 4), ('P4', 'Downtown', 7)], 'Downtown', 4)
Expected Output: ['P3']
Explanation: Both ['P1', 'P2'] and ['P3'] reach total capacity 4, but ['P3'] uses fewer properties, so it is preferred.
Input: ([('X', 'OldTown', 3), ('Y', 'OldTown', 5), ('Z', 'OldTown', 6), ('W', 'Midtown', 2)], 'OldTown', 7)
Expected Output: ['X', 'Y']
Explanation: No subset reaches exactly 7. The smallest valid total is 8 using ['X', 'Y'].
Input: ([('H1', 'Harbor', 2), ('H2', 'Harbor', 3), ('U1', 'Uptown', 10)], 'Harbor', 6)
Expected Output: []
Explanation: The total capacity available in Harbor is only 5, so no valid subset exists.
Input: ([], 'Any', 1)
Expected Output: []
Explanation: With no properties available, no valid subset can be formed.
Hints
- Ignore properties outside the target neighborhood first; the real problem is then choosing a subset of capacities.
- This is a subset-sum style dynamic programming problem: for each reachable exact total capacity, store the minimum number of properties needed to achieve it.