Group booking across properties in one neighborhood

Clarify first. Each property is [id, neighborhood, capacity]. book(neighborhood, group_size) picks free properties in that one neighborhood. Confirm the rule order with the interviewer:

1. The total capacity must be at least group_size.
2. Use as few properties as possible.
3. Among those, use the smallest total capacity (fewest empty beds).
4. If there is still a tie, return the lexicographically smallest sorted list of ids. Ask for this rule if the interviewer has not given one; the output must be deterministic.

Also ask: does a booking remove the properties (yes here), can capacity be zero (no), and what to return when nothing fits (an empty list).

Brute force. Try every subset size k = 1, 2, .... For each k, check every combination of k properties in the neighborhood. Keep the one with the smallest (total, sorted ids) among those that fit, and stop at the first k that has any fit. This is correct and a good first answer, but it is O(2^n) in the worst case.

Why greedy is not enough. Sorting by capacity, largest first, gives the minimum count k (take the biggest until the group fits). It does not give the smallest total: with capacities [10, 5, 5] and a group of 4, greedy takes 10, but 5 wastes fewer beds. Rule 3 is a subset-sum question, so use DP.

Optimal: 0/1 knapsack over exact totals. Let best[s] be the best subset whose capacities add to exactly s, stored as (count, sorted ids). Comparing tuples applies rule 2 and then rule 4. Process each property once and update s from high to low so no property is used twice (the standard 0/1 knapsack trick). Then scan s from group_size up and pick the smallest key (count, s, ids), which applies rules 2, 3 and 4 in order.

How far to scan. In a set with the fewest properties, removing any member drops the total below group_size (otherwise a smaller set would fit). So the best total is less than group_size + max_capacity. Totals above that bound never win, which keeps the table small.

Invariants.

• After processing properties p1..pi, best[s] holds the best subset of those properties with total exactly s, or None.
• Free properties are kept per neighborhood, so each request only looks at its own neighborhood. A booked id is deleted, so it can never be returned twice.

from __future__ import annotations

from collections import defaultdict


class BookingSystem:
    """Pick the best set of free properties in one neighborhood for a group.

    Rules, in order:
      1. Total capacity >= group size.
      2. Fewest properties.
      3. Smallest total capacity (fewest empty beds).
      4. Lexicographically smallest sorted list of ids.
    Booked properties stop being available.
    """

    def __init__(self, properties: list[list[str]]) -> None:
        self._free: dict[str, dict[str, int]] = defaultdict(dict)
        for pid, hood, cap in properties:
            capacity = int(cap)
            if capacity <= 0:
                raise ValueError(f"capacity must be positive: {pid}")
            self._free[hood][pid] = capacity

    def book(self, neighborhood: str, group_size: int) -> list[str]:
        if group_size <= 0:
            return []
        free = self._free.get(neighborhood, {})
        if sum(free.values()) < group_size:
            return []

        # In a minimal-count set, dropping any member falls below group_size,
        # so the best total is below group_size + max capacity.
        limit = group_size + max(free.values()) - 1

        # best[s] = (count, sorted ids) of the best subset with exact total s.
        best: list[tuple[int, tuple[str, ...]] | None] = [None] * (limit + 1)
        best[0] = (0, ())
        for pid in sorted(free):
            cap = free[pid]
            for s in range(limit, cap - 1, -1):  # descending: each id once
                prev = best[s - cap]
                if prev is None:
                    continue
                cand = (prev[0] + 1, tuple(sorted(prev[1] + (pid,))))
                if best[s] is None or cand < best[s]:
                    best[s] = cand

        choice: tuple[int, int, tuple[str, ...]] | None = None
        for s in range(group_size, limit + 1):
            entry = best[s]
            if entry is None:
                continue
            key = (entry[0], s, entry[1])
            if choice is None or key < choice:
                choice = key

        if choice is None:
            return []
        ids = list(choice[2])
        for pid in ids:
            del free[pid]
        return ids

Example:

system = BookingSystem([
    ["a", "soma", "4"], ["b", "soma", "3"], ["c", "soma", "5"],
    ["d", "soma", "2"], ["e", "mission", "6"],
])
system.book("soma", 7)   # ["a", "b"]  (two properties, total 7; beats ["c", "d"] on ids)
system.book("soma", 7)   # ["c", "d"]  (a and b are booked now)
system.book("soma", 1)   # []          (no free property left in soma)

Let n be the free properties in the neighborhood, G the group size and M the largest capacity. Let S = G + M.

• __init__: O(P) time and space for P properties.
• book: O(n * S) DP updates. Each update builds a sorted id tuple of length up to n, so the honest bound is O(n^2 * S) time (O(n * S * n log n) with the sort) and O(S * n) space. If ties on ids are not required, store only count per cell plus a back-pointer, which brings it to O(n * S) time and space.
• Removing booked ids: O(k) for k ids returned.

If capacities are large but n is small, the brute force over subsets of size k (O(C(n, k))) can be cheaper. Mention the trade-off.

• Properties a:4, b:3, c:5, d:2 in soma, e:6 in mission. book("soma", 7) returns ["a", "b"]. Two sets of two properties total exactly 7; ["a", "b"] wins on ids.
• Then book("soma", 7) again returns ["c", "d"], because a and b are booked.
• Then book("soma", 1) returns []. Nothing is free in soma.
• book("mission", 6) returns ["e"]. Exact fit with one property.
• book("nowhere", 1) returns []. Unknown neighborhood.
• x:3, y:3, z:6, book("h", 6) returns ["z"]. One property beats two, even though both waste zero beds.
• Then book("h", 6) returns ["x", "y"].
• p:10, q:5, r:5, book("h", 4) returns ["q"]. Greedy by size would wrongly pick p.
• book("h", 0) returns []. A group of zero needs nothing.
• Total capacity in the neighborhood below the group size returns [] and books nothing.
• Random check: the DP matches the brute force (try every subset, sort by (count, total, ids)) on 1,000 random cases with repeated bookings.

• Release or cancel a booking. Give each booking an id and keep booking_id -> [property ids]. cancel(booking_id) puts the properties back into their neighborhood's free map. Nothing else changes.
• Date ranges. Each property now has a calendar. A property is free for [start, end) if no existing booking overlaps it. Keep a sorted list of intervals per property and check overlap with binary search (O(log b)). Run the same DP over the properties that are free for the requested dates.
• Neighborhood fallback. If the neighborhood cannot fit the group, try nearby neighborhoods, or allow mixing. Model neighborhoods as a graph and search outward with BFS, or add a "distance" rule after rule 1. Clarify the new rule order before coding.
• Prices instead of beds. Replace rule 3 with "lowest total price". The DP becomes a min-cost knapsack: index by total capacity (capped at G + M), and store (count, price, ids). If price comes before count, swap the tuple order.
• Scale. With thousands of properties and large capacities, the table gets big. Bucket properties by capacity (many share the same size), so the DP runs over distinct sizes with counts (bounded knapsack). For many concurrent requests, lock per neighborhood so two requests cannot book the same property.

Mid-level (L4)

• Asks how ties are broken and what happens when nothing fits.
• Writes a correct brute force over subsets, then sees why greedy by size fails rule 3.
• Removes booked properties and keeps neighborhoods separate.

Senior (L5)

• Moves to a 0/1 knapsack DP and explains the high-to-low loop.
• Justifies the G + max capacity bound for the scan.
• Uses one comparable key (count, total, ids) so all rules apply in one place, and tests against the brute force.

Staff (L6+)

• Compares DP and subset search by input shape (many small capacities versus few large ones).
• Designs for cancellations, date ranges and concurrent bookings without rewriting the core.
• Discusses how the product rules may change (price, distance) and keeps the selection logic easy to swap.