Smallest free hub for a task: Frontier Interview's solution

Question: Smallest free hub for a task

Companies: Amazon

Difficulty: Medium

Problem statement

You run a fleet of n compute hubs, numbered 0 to n - 1, and need to place one new task on a single hub.

You are given:

capacities: an integer list of length n. capacities[i] is the processing capacity of hub i.
intervals: a list of n lists of strings. intervals[i] holds the time ranges already booked on hub i, each written "start:end" with integer times. Both ends are inclusive.
requiredCapacity: the capacity the task needs.
taskInterval: the task's time range, also "start:end" and inclusive.

A hub can take the task when its capacity is at least requiredCapacity and none of its bookings overlaps the task interval. Because ends are inclusive, two ranges that share even one time unit overlap: a booking "4:6" blocks a task "6:9".

Return the index of the hub that can take the task and has the smallest capacity. If several qualify with the same capacity, return the smallest index. Return -1 if no hub can take it.

find_smallest_hub(capacities, intervals, requiredCapacity, taskInterval) -> int

Constraints: 0 <= n <= 10^5; total bookings up to 2 * 10^5; times fit in a 32-bit integer and start <= end. Bookings on one hub may be unsorted.

Example 1

capacities       = [9, 3, 5]
intervals        = [[], ["0:2"], ["7:8"]]
requiredCapacity = 3
taskInterval     = "1:4"

Hub 1 is busy (0:2 overlaps 1:4). Hubs 0 and 2 are free, and hub 2 has the smaller capacity. Answer: 2.

Example 2

Same hubs, taskInterval = "3:6". Hub 1 is now free and is the smallest that fits. Answer: 1.

Part 2. Requests arrive one after another. Each accepted task is booked on its chosen hub, so it blocks later requests. Design a class with schedule(requiredCapacity, taskInterval) -> int that is fast across many calls.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Two checks decide whether a hub can take the task:

Capacity. capacities[i] >= requiredCapacity.
Availability. No booked interval on hub i overlaps the task interval.

Among the hubs that pass both checks, pick the one with the smallest capacity. The task fits, and the bigger hubs stay free for bigger jobs (best fit). Break ties by the smallest index. If no hub qualifies, return -1.

Overlap test. Both ends are inclusive. Two closed intervals [a, b] and [c, d] overlap exactly when a <= d and c <= b. Sharing one endpoint counts as a conflict: a booking "3:5" blocks a task "5:8". Say this out loud and confirm it with the interviewer. It is the most common place to lose points.

Parsing. Split each "start:end" on ":" and convert both halves to int. Validate start <= end. Do not compare the strings directly: "10" < "9" as strings.

One-shot algorithm. Parse the task interval once. Walk the hubs in index order. Skip a hub cheaply when its capacity is too small, before parsing any of its bookings. Otherwise scan its bookings and stop at the first overlap. Keep the best (capacity, index) seen so far. Walking in index order and replacing only on a strictly smaller capacity gives the smallest-index tie-break for free.

This is already optimal for a single query. Every booking might have to be read once, so O(total bookings) is a lower bound.

Many queries (the usual Part 2). If the same hubs answer many requests, and each accepted task becomes a new booking, re-scanning everything per request is wasteful. Keep each hub's bookings sorted by start and non-overlapping. Then one binary search decides availability: find the last booking that starts at or before the task's end, and check whether it ends at or after the task's start. Bookings never overlap each other, so only that one neighbour can conflict. The HubScheduler class below does this and books the chosen hub.

Invariants.

best is the smallest-capacity, then smallest-index, feasible hub among the hubs scanned so far.
In HubScheduler, every hub's starts list is sorted, and its intervals are pairwise disjoint (each book only inserts a free interval).

Code

import bisect
from typing import List, Tuple

Interval = Tuple[int, int]


def parse_interval(s: str) -> Interval:
    start_str, end_str = s.split(":")
    start, end = int(start_str), int(end_str)
    if start > end:
        raise ValueError(f"bad interval {s!r}")
    return start, end


def overlaps(a: Interval, b: Interval) -> bool:
    """Closed intervals: touching endpoints count as overlap."""
    return a[0] <= b[1] and b[0] <= a[1]


def find_smallest_hub(capacities: List[int], intervals: List[List[str]],
                      required_capacity: int, task_interval: str) -> int:
    task = parse_interval(task_interval)
    best = -1
    for i, cap in enumerate(capacities):
        if cap < required_capacity:
            continue
        if best != -1 and cap >= capacities[best]:
            continue  # cannot beat the current best; skip parsing
        if any(overlaps(parse_interval(b), task) for b in intervals[i]):
            continue
        best = i
    return best


class HubScheduler:
    """Answers many requests and books each accepted task on its hub."""

    def __init__(self, capacities: List[int], intervals: List[List[str]]):
        self.capacities = capacities
        self.starts: List[List[int]] = []
        self.ends: List[List[int]] = []
        for bookings in intervals:
            parsed = sorted(parse_interval(b) for b in bookings)
            self.starts.append([s for s, _ in parsed])
            self.ends.append([e for _, e in parsed])
        # Hub indices by (capacity, index): the first free one is the answer.
        self.order = sorted(range(len(capacities)),
                            key=lambda i: (capacities[i], i))
        self.order_caps = [capacities[i] for i in self.order]

    def is_free(self, hub: int, task: Interval) -> bool:
        # Last booking that starts at or before the task's end.
        k = bisect.bisect_right(self.starts[hub], task[1]) - 1
        return k < 0 or self.ends[hub][k] < task[0]

    def schedule(self, required_capacity: int, task_interval: str) -> int:
        task = parse_interval(task_interval)
        first = bisect.bisect_left(self.order_caps, required_capacity)
        for hub in self.order[first:]:
            if self.is_free(hub, task):
                pos = bisect.bisect_left(self.starts[hub], task[0])
                self.starts[hub].insert(pos, task[0])
                self.ends[hub].insert(pos, task[1])
                return hub
        return -1

Complexity

Let n be the number of hubs and B the total number of booked intervals.

find_smallest_hub: O(n + B) time, since each booking is parsed at most once. O(1) extra space.
HubScheduler.__init__: O(B log B + n log n) time to sort bookings and hubs, O(n + B) space.
HubScheduler.schedule: O(h log b) to find the hub, where h is the number of hubs tried and b is the bookings per hub. The list insert costs O(b). A balanced tree (or sortedcontainers.SortedList) makes the insert O(log b).

Test cases

capacities = [8, 4, 6], intervals = [[], ["1:3"], ["10:12"]], required 4, task "2:5": hub 1 is busy (1:3 overlaps 2:5), hub 2 is free with capacity 6. Answer 2.
Same hubs, task "4:9": hub 1 is free and smallest. Answer 1.
Touching endpoint: capacities = [5], intervals = [["3:5"]], required 5, task "5:8". They share time 5. Answer -1.
Adjacent but not touching: same hub, task "6:8". Answer 0.
Tie on capacity: capacities = [7, 7], both free. Answer 0 (smallest index).
Exact fit: capacity equals required. That hub qualifies.
No hub big enough: capacities = [1, 2], required 3. Answer -1.
Empty hub list: capacities = []. Answer -1.
Multi-digit times: booking "9:10", task "10:20". Overlap at 10, so the hub is busy (string comparison would get this wrong).
HubScheduler([5, 5], [[], []]): schedule(5, "1:4") returns 0; schedule(5, "3:6") returns 1 (hub 0 is now busy at 3–4); schedule(5, "3:6") again returns -1.

Follow-ups

Book the task and handle a stream of requests. Use HubScheduler: sorted, disjoint bookings per hub and a binary search per hub. Hubs pre-sorted by (capacity, index) let you start at the first hub that is large enough and stop at the first free one.
Bookings consume capacity instead of blocking the hub. Each booking now carries a load, and a hub can run several tasks at once. A hub fits when its peak load over the task interval plus requiredCapacity stays within capacity. For one query, sweep the bookings that overlap the task interval (+load at start, -load at end + 1) and track the peak. For many queries, use a segment tree per hub with range add and range max.
Many hubs, many queries, few distinct capacities. Group hubs by capacity, or keep a segment tree over hubs sorted by capacity where each node can answer "is any hub in this range free". The usual interview answer is the sorted scan plus early exit, together with a note on when it degrades.
Choose a different policy. Earliest-free, least-loaded, or "pack the busiest hub that still fits" all reuse the same feasibility check with a different key. Ask which one the business wants. Best fit reduces fragmentation, and least-loaded spreads risk.
Cancel a booking. Delete it from the sorted lists with a binary search on the start. Disjointness still holds.

Interviewer expectations

Mid-level (L4)

Parses "start:end" into integers and gets the inclusive overlap test right, including touching endpoints.
Applies the capacity filter and the smallest-capacity, then smallest-index rule, and returns -1 when nothing fits.
Walks through a couple of the test cases above by hand.

Senior (L5)

Asks about inclusive ends, ties, and bad input before coding.
States O(n + B) and explains why a single query cannot do better. Skips parsing for hubs that cannot win.
Moves to the multi-query version without prompting: sorted disjoint bookings, binary search, booking the chosen hub.

Staff (L6+)

Talks about the placement policy as a product choice (best fit versus spread) and what each costs.
Generalises to capacity-consuming bookings with a sweep or a segment tree, and to concurrency: two schedulers must not book the same slot (per-hub locks or compare-and-set on the booking list).
Discusses scale: sharding hubs, keeping availability indexes fresh, and what to do when a hub fails with bookings on it.