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

What role is this question designed for?

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

Compute party hours per town and city gaps

Quick Overview

This question evaluates the ability to manipulate time-interval data, compute interval unions and gaps, and perform hierarchical aggregation across towns and cities, testing skills in interval arithmetic, data modeling, and efficient algorithmic implementation.

Compute party hours per town and city gaps

Company: Scale AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given (1) a region table describing a hierarchy of locations and (2) a list of party attendance time intervals (all timestamps occur within a single calendar day). ### Input 1) **Region data** (each row describes one town and the city/state it belongs to): - `town_id` (string/int) - `town_name` (string) - `city_id` (string/int) - `city_name` (string) - `state_id` (string/int) - `state_name` (string) Assume each `town_id` belongs to exactly one `city_id`. 2) **Party intervals** (each row indicates that a given town is “at a party” during a time range on that day): - `town_id` - `start_time` (time within the day, e.g., minutes since 00:00) - `end_time` (time within the day, `end_time > start_time`) Notes: - A town can have multiple party intervals in the same day. - Party intervals for the same town may be unsorted and may overlap or touch. Define the day as the window `[day_start, day_end)` (e.g., `[00:00, 24:00)`). --- ### Task A (per-town party hours) For each `town_id`, compute the **total number of hours** spent at a party during the day, counting the **union** of that town’s intervals (i.e., overlapping intervals should not be double-counted). Return results as: - `town_id`, `party_hours` (can be fractional) --- ### Task B (city-level idle/gap time segments) Using the same party intervals, compute **idle (not-at-party) time segments** for each town (within `[day_start, day_end)`), then **group the idle segments by `city_id`**. Output for each city a set/list of time segments representing the idle periods contributed by its towns. (You should specify clearly whether you are returning: - all town idle segments annotated with town, or - merged/unioned idle segments at the city level. If not specified otherwise, assume you should return **all idle segments per town, grouped by city**: - `city_id`, `town_id`, `idle_start`, `idle_end` --- ### Constraints / Expectations - Times can be represented as integer minutes. - Aim for an efficient approach (e.g., sort + merge per town). - Clarify edge cases: no party intervals for a town, intervals touching at endpoints, intervals outside the day window (if present, clamp to the day window).

Quick Answer: This question evaluates the ability to manipulate time-interval data, compute interval unions and gaps, and perform hierarchical aggregation across towns and cities, testing skills in interval arithmetic, data modeling, and efficient algorithmic implementation.

Part 1: Unioned Party Hours Per Town

You are given a region table and a list of party attendance intervals for towns within a single day. For each town in the region table, compute how many hours that town spent at a party during the day, counting the union of its intervals only once. Intervals for the same town may be unsorted, overlapping, touching at endpoints, or partially outside the day window. Any interval outside the day must be clamped to [day_start, day_end). If a town has no valid party interval, its total is 0.0 hours. Return results in the same order as towns appear in region_data. Round hours to 2 decimal places.

Loading coding console...

Examples

Input: ([('t1', 'Oak', 'c1', 'Metro', 's1', 'North'), ('t2', 'Pine', 'c1', 'Metro', 's1', 'North')], [('t1', 60, 120), ('t1', 90, 180), ('t1', 180, 210), ('t2', 300, 330)], 0, 1440)

Expected Output: [('t1', 2.5), ('t2', 0.5)]

Explanation: Town t1 has merged coverage [60, 210] = 150 minutes = 2.5 hours. Town t2 has 30 minutes = 0.5 hours.

Input: ([('t1', 'Oak', 'c1', 'Metro', 's1', 'North'), ('t2', 'Pine', 'c1', 'Metro', 's1', 'North'), ('t3', 'Elm', 'c2', 'Lake', 's1', 'North')], [('t1', -30, 30), ('t1', 1400, 1500), ('t3', 100, 160), ('t3', 120, 180)], 0, 1440)

Expected Output: [('t1', 1.17), ('t2', 0.0), ('t3', 1.33)]

Explanation: t1 is clamped to [0,30] and [1400,1440] for 70 minutes total. t2 has no intervals. t3 merges to [100,180] for 80 minutes.

Input: ([('t1', 'Solo', 'c1', 'Metro', 's1', 'North')], [('t1', -50, 100), ('t1', 100, 400), ('t1', 300, 1440), ('t1', 1440, 1500)], 0, 1440)

Expected Output: [('t1', 24.0)]

Explanation: After clamping and merging, the town is covered for the full day [0,1440).

Input: ([('t1', 'Oak', 'c1', 'Metro', 's1', 'North'), ('t2', 'Pine', 'c2', 'Lake', 's1', 'North')], [('t1', 450, 500), ('t1', 590, 650), ('t2', 480, 600)], 480, 600)

Expected Output: [('t1', 0.5), ('t2', 2.0)]

Explanation: The day window is [480,600). t1 contributes [480,500] and [590,600] = 30 minutes. t2 covers the whole window.

Solution

def solution(region_data, party_intervals, day_start, day_end):
    town_order = []
    seen = set()
    for row in region_data:
        town_id = row[0]
        if town_id not in seen:
            seen.add(town_id)
            town_order.append(town_id)

    grouped = {town_id: [] for town_id in town_order}

    for town_id, start, end in party_intervals:
        if town_id not in grouped:
            continue
        start = max(start, day_start)
        end = min(end, day_end)
        if start < end:
            grouped[town_id].append((start, end))

    result = []
    for town_id in town_order:
        intervals = sorted(grouped[town_id])
        merged = []

        for start, end in intervals:
            if not merged or start > merged[-1][1]:
                merged.append([start, end])
            else:
                if end > merged[-1][1]:
                    merged[-1][1] = end

        total_minutes = 0
        for start, end in merged:
            total_minutes += end - start

        hours = round(total_minutes / 60.0 + 1e-12, 2)
        result.append((town_id, hours))

    return result

Time complexity: O(R + P log P), where R is the number of region rows and P is the number of party intervals.. Space complexity: O(R + P).

Part 2: City-Grouped Idle Segments Per Town

You are given a region table and a list of party attendance intervals for towns within a single day. For each town, first compute the union of its party intervals inside the day window [day_start, day_end). Then compute that town's idle segments: the time ranges in the day when the town is not at a party. Finally, group those idle segments by city. Return all idle segments per town, grouped under each city_id. Intervals may be unsorted, overlapping, touching, or partially outside the day; clamp them to the day window before processing. If a town has no valid party intervals, its idle segment is the full day. If a town is at a party for the entire day, it contributes no idle segment. Include every city from region_data in the result, even if its list is empty.

Constraints

0 <= len(region_data) <= 10^5
0 <= len(party_intervals) <= 2 * 10^5
Times are integer minutes.
Intervals may be unsorted, overlapping, touching, or partially outside the day window.
Touching party intervals must be merged before computing gaps.
Assume each town_id in region_data belongs to exactly one city_id.

Examples

Input: ([('t1', 'Oak', 'c1', 'Metro', 's1', 'North'), ('t2', 'Pine', 'c1', 'Metro', 's1', 'North'), ('t3', 'Elm', 'c2', 'Lake', 's1', 'North')], [('t1', 60, 120), ('t1', 90, 180), ('t2', 300, 360), ('t3', 0, 600)], 0, 600)

Expected Output: {'c1': [('t1', 0, 60), ('t1', 180, 600), ('t2', 0, 300), ('t2', 360, 600)], 'c2': []}

Explanation: t1 has idle [0,60] and [180,600]. t2 has idle [0,300] and [360,600]. t3 is busy for the full day window, so c2 gets an empty list.

Input: ([('t1', 'Oak', 'c1', 'Metro', 's1', 'North'), ('t2', 'Pine', 'c1', 'Metro', 's1', 'North'), ('t3', 'Elm', 'c2', 'Lake', 's1', 'North')], [('t1', -30, 30), ('t1', 90, 150), ('t3', 50, 70), ('t3', 70, 80)], 0, 120)

Expected Output: {'c1': [('t1', 30, 90), ('t2', 0, 120)], 'c2': [('t3', 0, 50), ('t3', 80, 120)]}

Explanation: t1 becomes busy on [0,30] and [90,120], leaving [30,90]. t2 has no intervals, so it is idle the whole day. t3's touching intervals merge to [50,80].

Input: ([('t1', 'Solo', 'c1', 'Metro', 's1', 'North')], [], 10, 20)

Expected Output: {'c1': [('t1', 10, 20)]}

Explanation: With no party intervals, the town is idle for the entire day window.

Input: ([('t1', 'Oak', 'c1', 'Metro', 's1', 'North'), ('t2', 'Pine', 'c1', 'Metro', 's1', 'North')], [('t1', 10, 20), ('t1', 20, 30), ('t1', 25, 40), ('t2', 0, 100)], 0, 100)

Expected Output: {'c1': [('t1', 0, 10), ('t1', 40, 100)]}

Explanation: t1's touching and overlapping intervals merge to [10,40], so there is no gap at 20. t2 covers the whole day and contributes no idle segment.

Solution

def solution(region_data, party_intervals, day_start, day_end):
    town_to_city = {}
    town_order = []
    result = {}

    for row in region_data:
        town_id, _, city_id, _, _, _ = row
        if city_id not in result:
            result[city_id] = []
        if town_id not in town_to_city:
            town_to_city[town_id] = city_id
            town_order.append(town_id)

    grouped = {town_id: [] for town_id in town_order}

    for town_id, start, end in party_intervals:
        if town_id not in grouped:
            continue
        start = max(start, day_start)
        end = min(end, day_end)
        if start < end:
            grouped[town_id].append((start, end))

    for town_id in town_order:
        intervals = sorted(grouped[town_id])
        merged = []

        for start, end in intervals:
            if not merged or start > merged[-1][1]:
                merged.append([start, end])
            else:
                if end > merged[-1][1]:
                    merged[-1][1] = end

        city_id = town_to_city[town_id]
        prev = day_start

        for start, end in merged:
            if prev < start:
                result[city_id].append((town_id, prev, start))
            prev = end

        if prev < day_end:
            result[city_id].append((town_id, prev, day_end))

    return result

Time complexity: O(R + P log P), where R is the number of region rows and P is the number of party intervals.. Space complexity: O(R + P).

Hints

First solve the per-town merge problem: city grouping is easier once each town has a clean merged interval list.
Idle segments are just the complement of merged party coverage inside [day_start, day_end).