Find minimal property set in neighborhood

Q: Find minimal property set in neighborhood

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.

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

PracHub · Accepted Answer

def solution(properties, targetNeighborhood, groupSize): from array import array # Edge case: an empty selection already satisfies a non-positive target. if groupSize <= 0: return [] # Keep only properties from the requested neighborhood. # Each property is a tuple: (id, neighborhood, capacity). # Duplicate capacities are fine; IDs are assumed unique by the constraints. items = [] for pid, neighborhood, capacity in properties: if neighborhood == targetNeighborhood: items.append((pid, capacity)) if not items: return [] # Sort by ID so reconstruction naturally returns IDs in ascending order # and can break ties lexicographically. items.sort(key=lambda x: x[0]) total_capacity = sum(capacity for _, capacity in items) if total_capacity < groupSize: return [] max_capacity = max(capacity for _, capacity in items) # Exact DP only needs sums up to this limit. # If an optimal subset uses the minimum possible number of properties, # then removing any selected property must make it infeasible; otherwise # a smaller-cardinality solution would exist. So if T is the optimal total, # T - chosen_capacity < groupSize for every chosen property, which implies # T < groupSize + chosen_capacity <= groupSize + max_capacity. limit = min(total_capacity, groupSize + max_capacity - 1) n = len(items) inf = n + 1 # suf[i][s] = minimum number of properties needed to make exact sum s # using only items[i:]. If impossible, it stores inf. suf = [None] * (n + 1) base = array('H', [inf]) * (limit + 1) base[0] = 0 suf[n] = base for i in range(n - 1, -1, -1): _, capacity = items[i] next_row = suf[i + 1] row = array('H', next_row) # option: skip current property for s in range(capacity, limit + 1): candidate = next_row[s - capacity] + 1 if candidate < row[s]: row[s] = candidate suf[i] = row # Choose the best exact total capacity: # 1) minimum number of properties # 2) among those, minimum total capacity >= groupSize best_count = inf best_sum = None for s in range(groupSize, limit + 1): count = suf[0][s] if count < best_count: best_count = count best_sum = s if best_sum is None or best_count == inf: return [] # Reconstruct the lexicographically smallest ID list for (best_count, best_sum). # Since items are sorted by ID, greedily taking the current item whenever it can # still lead to an optimal solution yields the lexicographically smallest answer. result = [] remaining_sum = best_sum remaining_count = best_count for i, (pid, capacity) in enumerate(items): if remaining_count == 0: break if remaining_sum >= capacity and suf[i + 1][remaining_sum - capacity] + 1 == remaining_count: result.append(pid) remaining_sum -= capacity remaining_count -= 1 return result

Quick Overview

Examples

Solution

Hints

Quick Overview