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.

What difficulty level is this coding question?

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

What role is this question designed for?

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

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.

Quick Answer: 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.

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

Expected Output: []

Explanation: The total downtown capacity is only 9, so reaching 10 is impossible.

Input: ([(10, "midtown", 6), (11, "midtown", 3), (12, "midtown", 2)], "midtown", 5)

Expected Output: [10]

Explanation: Using one property is better than using two, even though [11, 12] hits the target exactly.

Input: ([(5, "alpha", 4), (1, "alpha", 4), (3, "alpha", 4), (9, "beta", 10)], "alpha", 8)

Expected Output: [1, 3]

Explanation: Any 2 alpha properties reach 8. They all have the same count and total capacity, so choose the lexicographically smallest ID list.

Input: ([(1, "north", 4), (2, "north", 7)], "north", 0)

Expected Output: []

Explanation: A non-positive group size is already satisfied by the empty subset.

Input: ([(1, "north", 4), (2, "north", 7)], "south", 3)

Expected Output: []

Explanation: No property belongs to the target neighborhood.

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.

Quick Overview