Party hours and quiet gaps by neighborhood and city

Question: Party hours and quiet gaps by neighborhood and city

Companies: Scale AI

Difficulty: Medium

Problem statement

A community events app records every party in two separate lists that share a partyId:

• partyWindows: rows of [partyId, start, end]. start and end are hours as strings, and a party runs over the half-open interval [start, end).
• geoDataList: rows of [partyId, neighborhood, city].

Each neighborhood belongs to one city. Ignore a party that appears in only one of the two lists.

Implement a class PartyAggregator(partyWindows, geoDataList) with:

1. neighborhood_hours() -> dict[str, int]: for each neighborhood, the number of hours during which at least one of its parties is running. Overlapping parties must not be counted twice.
2. city_hours() -> dict[str, int]: the same measure for each city, over all parties in all of its neighborhoods.
3. city_gaps() -> dict[str, list[tuple[int, int]]]: for each city, the quiet stretches (from, to) between its first party start and its last party end when no party is running anywhere in the city, in time order. A party ending at 15 and another starting at 15 leave no gap.
4. report(): a list of (city, hours, gaps) sorted by hours descending, then city name ascending.

Raise ValueError for a window whose start is after its end. A zero-length window covers no time.

Constraints: up to 10^5 parties; hours fit in a 32-bit integer.

Example

partyWindows = [["a","10","14"], ["b","12","16"], ["c","20","21"], ["d","8","9"]]
geoDataList  = [["a","Harbor","Bayview"], ["b","Hilltop","Bayview"], ["c","Harbor","Bayview"], ["e","Old Town","Riverton"]]

• neighborhood_hours() → {"Harbor": 5, "Hilltop": 4}
• city_hours() → {"Bayview": 7} (10 to 16 is 6 hours, plus 20 to 21)
• city_gaps() → {"Bayview": [(16, 20)]}
• Party d has no location and e has no window, so both are ignored.

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

Approach

The two lists are two halves of one record, joined on partyId. Once every party has both its window and its place, each question becomes an interval-union question over a group of parties: one group per neighborhood, one group per city.

Join first. Build a dictionary partyId -> (start, end) from partyWindows, then walk geoDataList and append each window to its neighborhood's list and its city's list. A party with a location but no window (or the reverse) is skipped. Say so out loud: the interviewer wants to hear that you thought about records that don't match.

Brute force. For each group, mark every hour from the earliest start to the latest end in a boolean array and count the marked cells. This is correct for small integer hours, but the cost is O(span) per group rather than O(parties), and it breaks if times are minutes or Unix timestamps. Adding up raw durations without merging is the common wrong answer: two parties from 18 to 22 and 20 to 23 cover 5 hours, not 7.

Sort and merge (the expected answer). Sort a group's intervals by start. Keep a list of merged intervals. For each interval, if it starts at or before the end of the last merged interval, extend that end to max(end, last_end). Otherwise start a new merged interval. Party hours for the group are the sum of end - start over the merged list. The gaps for a city are the spaces between consecutive merged intervals: (merged[i].end, merged[i+1].start).

Invariants.

• After processing the first k sorted intervals, the merged list is sorted, pairwise disjoint with a strictly positive space between neighbors, and its union equals the union of those k intervals.
• Intervals are half-open [start, end). A party ending at 15 and one starting at 15 leave no gap, so they merge. State this convention before coding; it decides whether < or <= goes in the merge test.
• A city's union is computed from all its parties directly, not by adding neighborhood totals. Two neighborhoods that party at the same time in one city must not count that time twice.

Code

from __future__ import annotations

from collections import defaultdict

Interval = tuple[int, int]


def merge(intervals: list[Interval]) -> list[Interval]:
    """Union of half-open intervals [start, end). Touching intervals merge."""
    merged: list[Interval] = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            last_start, last_end = merged[-1]
            merged[-1] = (last_start, max(last_end, end))
        else:
            merged.append((start, end))
    return merged


class PartyAggregator:
    def __init__(
        self,
        party_windows: list[list[str]],
        geo_data: list[list[str]],
    ) -> None:
        windows: dict[str, Interval] = {}
        for party_id, start, end in party_windows:
            s, e = int(start), int(end)
            if s > e:
                raise ValueError(f"party {party_id}: start after end")
            windows[party_id] = (s, e)

        self._by_neighborhood: dict[str, list[Interval]] = defaultdict(list)
        self._by_city: dict[str, list[Interval]] = defaultdict(list)
        for party_id, neighborhood, city in geo_data:
            window = windows.get(party_id)
            if window is None or window[0] == window[1]:
                continue  # no time window, or zero length: covers no time
            self._by_neighborhood[neighborhood].append(window)
            self._by_city[city].append(window)

    def neighborhood_hours(self) -> dict[str, int]:
        """Hours during which at least one party runs in each neighborhood."""
        return {
            hood: sum(e - s for s, e in merge(intervals))
            for hood, intervals in self._by_neighborhood.items()
        }

    def city_hours(self) -> dict[str, int]:
        """Party hours per city: union over all its neighborhoods' parties."""
        return {
            city: sum(e - s for s, e in merge(intervals))
            for city, intervals in self._by_city.items()
        }

    def city_gaps(self) -> dict[str, list[Interval]]:
        """Quiet stretches between a city's first party start and last party end."""
        gaps: dict[str, list[Interval]] = {}
        for city, intervals in self._by_city.items():
            merged = merge(intervals)
            gaps[city] = [
                (merged[i][1], merged[i + 1][0]) for i in range(len(merged) - 1)
            ]
        return gaps

    def report(self) -> list[tuple[str, int, list[Interval]]]:
        """(city, city hours, gaps) sorted by hours desc, then city name."""
        hours, gaps = self.city_hours(), self.city_gaps()
        return sorted(
            ((c, hours[c], gaps[c]) for c in hours),
            key=lambda row: (-row[1], row[0]),
        )

Complexity

Let n be the number of parties and k the number of parties in one group.

• Constructor (join and group): O(n) time, O(n) space. Each party is stored once per neighborhood list and once per city list.
• merge: O(k log k) time for the sort, O(k) space for the output.
• neighborhood_hours, city_hours, city_gaps: O(n log n) time in total across all groups, because the groups partition the parties. O(n) space.
• report: O(n log n + c log c) time, where c is the number of cities.

If the same aggregator is queried many times, cache the merged list per group after the first call; later queries then cost O(number of groups).

Test cases

• Basic overlap: p1 [18,22) and p2 [20,23), both in Mission, SF → Mission has 5 hours, not 7.
• City with a gap: add p3 [9,11) in SoMa, SF → SF has 7 hours and one gap (11, 18).
• Touching windows across neighborhoods: p4 [13,15) in Fremont and p5 [15,16) in Ballard, both Seattle → Seattle has 3 hours and no gaps.
• Report order: the data above → [("SF", 7, [(11, 18)]), ("Seattle", 3, [])].
• Nested and duplicate windows: [(1,10), (2,3), (1,10)] merges to [(1,10)].
• Unmatched records: a window with no location row (p6) and a location row with no window (p7) are both ignored; no "Nowhere" city appears.
• Zero-length party: [5,5) covers no time and is dropped, so it can't create a city with 0 hours or split a gap.
• Bad input: start > end raises ValueError.
• Empty input: empty lists → empty dicts and an empty report.

Follow-ups

1. Busiest moment per city. Report the maximum number of parties running at the same time, and when. Turn each window into events (start, +1) and (end, -1), sort with ends before starts at equal times (half-open), and sweep a running count. O(k log k) per city.
2. A deeper region hierarchy (neighborhood → town → city → country). Store a parent map and attach each party to every ancestor while joining, or merge bottom-up: a parent's merged list is the k-way merge of its children's sorted merged lists followed by one merge pass. Never sum child totals.
3. Streaming parties. Parties arrive one at a time and queries come between arrivals. Keep a sorted, disjoint interval set per region (a balanced tree or sortedcontainers.SortedList). An insert finds the neighbors by binary search, absorbs every interval it overlaps, and adjusts a running total. Inserts cost O(log m + merged), queries O(1).
4. Query window. "Party hours in SF between 12 and 20." Clip each merged interval to the window, or keep prefix sums of merged lengths and binary-search the two edges for O(log m) per query.
5. Real timestamps and time zones. Parse ISO strings to UTC epoch seconds before merging, and convert gaps back to the city's local time only for display. Windows that cross midnight then need no special case.

Interviewer expectations

Mid-level (L4)

• Joins the two lists on partyId correctly and notices that durations must be merged, not summed.
• Writes a correct sort-and-merge with the right comparison for touching intervals.
• Tests with at least one overlapping and one non-overlapping case.

Senior (L5)

• Asks about unmatched ids, zero-length and reversed windows, and the open or closed endpoint convention before coding.
• Computes city totals from the union of all city parties, and explains why adding neighborhood totals is wrong.
• Gives tight complexity per method and structures the code so a new aggregation (gaps, peaks) reuses merge.

Staff (L6+)

• Moves quickly through the base parts, then designs for the follow-ups: streaming inserts, a deeper hierarchy, and window queries.
• Discusses trade-offs between recomputing on demand and maintaining merged sets incrementally, and where to cache.
• Raises data concerns: time zones, duplicate or conflicting records for one partyId, and validating inputs at the boundary.