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 community ranges and town idle hours

Company: Scale AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two in-memory datasets for a party-planning app. 1) PartyWindow: {partyId: string, startTime: ISO-8601 UTC datetime, endTime: ISO-8601 UTC datetime} with startTime < endTime. 2) GeoData: {partyId: string, state: string, county: string, town: string, community: string}. Each partyId appears exactly once in each dataset. Implement: (a) A method that joins PartyWindow with GeoData on partyId and returns, for every community, the earliest party start and the latest party end across all parties in that community. Specify your return type (e.g., Map<community, [minStart, maxEnd]>) and how you handle sorting/output order. (b) A method that, using the same inputs, computes for every town the total number of hours during which no party is happening anywhere in that town. First, within each town, merge overlapping or adjacent intervals (adjacent means end == nextStart and should not count as a gap). Then sum the durations of gaps strictly between the merged intervals over the span from the earliest start to the latest end observed in that town. Return Map<town, hours>, using UTC and ignoring DST, and state any rounding policy. State and justify the time and space complexity of your solutions, and discuss data structures you would use (e.g., hash maps, sorting, interval merging).

Quick Answer: This question evaluates skills in dataset joins, temporal interval aggregation and merging, gap computation, UTC time handling, and algorithmic complexity analysis alongside appropriate data-structure selection.

Part 1: Join party data and compute earliest/latest time range for each community

You are given two in-memory datasets for a party-planning app. - `party_windows`: each row is `(party_id, start_time, end_time)` - `geo_data`: each row is `(party_id, state, county, town, community)` Each `party_id` appears exactly once in both datasets. Join the datasets on `party_id`, then compute, for every `community`, the earliest party start time and the latest party end time among all parties in that community. Return a dictionary of the form `{community: (min_start, max_end)}`. All timestamps are ISO-8601 UTC datetimes. Normalize returned timestamps to UTC strings ending in `Z`. Output order is not important.

Constraints

`0 <= n <= 200000`, where `n` is the number of parties
`len(party_windows) == len(geo_data)`
Each `party_id` appears exactly once in each input, and the ID sets are identical
All times are valid ISO-8601 UTC datetimes, and `start_time < end_time` for every party
Group only by the `community` string exactly as given

Examples

Input: ([('p1', '2024-01-01T10:00:00Z', '2024-01-01T12:00:00Z'), ('p2', '2024-01-01T09:00:00Z', '2024-01-01T11:30:00Z'), ('p3', '2024-01-02T15:00:00Z', '2024-01-02T18:00:00Z')], [('p1', 'CA', 'A', 'Town1', 'CommA'), ('p2', 'CA', 'A', 'Town2', 'CommA'), ('p3', 'CA', 'B', 'Town3', 'CommB')])

Expected Output: {'CommA': ('2024-01-01T09:00:00Z', '2024-01-01T12:00:00Z'), 'CommB': ('2024-01-02T15:00:00Z', '2024-01-02T18:00:00Z')}

Explanation: After joining on `party_id`, community `CommA` has two parties, so its range is from 09:00 to 12:00. `CommB` has one party.

Input: ([('p3', '2024-03-01T18:00:00Z', '2024-03-01T19:00:00Z'), ('p1', '2024-03-01T08:00:00Z', '2024-03-01T09:00:00Z'), ('p2', '2024-03-01T07:30:00+00:00', '2024-03-01T21:00:00+00:00')], [('p2', 'WA', 'King', 'Town2', 'North'), ('p1', 'WA', 'King', 'Town1', 'North'), ('p3', 'WA', 'Pierce', 'Town9', 'South')])

Expected Output: {'North': ('2024-03-01T07:30:00Z', '2024-03-01T21:00:00Z'), 'South': ('2024-03-01T18:00:00Z', '2024-03-01T19:00:00Z')}

Explanation: The input order is arbitrary. The `+00:00` timestamps are valid UTC and should be normalized to `Z` in the output.

Hints

Build a hash map from `party_id` to its `(start_time, end_time)` so the join is O(1) per row.
For each community, keep only two values while scanning: the minimum start seen so far and the maximum end seen so far.

Part 2: Compute total idle hours in each town by merging party intervals

You are given the same two datasets: - `party_windows`: each row is `(party_id, start_time, end_time)` - `geo_data`: each row is `(party_id, state, county, town, community)` Each `party_id` appears exactly once in both datasets. Join the datasets on `party_id`, then group party intervals by `town`. For each town: 1. Sort that town's intervals by start time. 2. Merge intervals that overlap or are adjacent. Adjacent means `current_end == next_start`, and such intervals should be treated as continuous with no gap. 3. Over the span from the earliest party start to the latest party end in that town, sum the durations of the gaps strictly between the merged intervals. Return a dictionary `{town: idle_hours}`. Use UTC only. Ignore DST. Return hours as `total_seconds / 3600.0` with no additional rounding. Output order is not important.

Constraints

`0 <= n <= 200000`, where `n` is the number of parties
`len(party_windows) == len(geo_data)`
Each `party_id` appears exactly once in each input, and the ID sets are identical
All times are valid ISO-8601 UTC datetimes, and `start_time < end_time` for every party
Group only by the `town` string exactly as given
Adjacent intervals (`end == next_start`) must be merged and must not contribute to idle time

Examples

Input: ([('p1', '2024-01-01T10:00:00Z', '2024-01-01T12:00:00Z'), ('p2', '2024-01-01T11:00:00Z', '2024-01-01T13:00:00Z'), ('p3', '2024-01-01T15:00:00Z', '2024-01-01T16:00:00Z'), ('p4', '2024-01-01T09:00:00Z', '2024-01-01T10:00:00Z'), ('p5', '2024-01-01T10:00:00Z', '2024-01-01T11:00:00Z')], [('p1', 'CA', 'A', 'TownX', 'C1'), ('p2', 'CA', 'A', 'TownX', 'C2'), ('p3', 'CA', 'A', 'TownX', 'C3'), ('p4', 'CA', 'B', 'TownY', 'C1'), ('p5', 'CA', 'B', 'TownY', 'C2')])

Expected Output: {'TownX': 2.0, 'TownY': 0.0}

Explanation: In `TownX`, `[10,12]` and `[11,13]` merge to `[10,13]`, leaving a 2-hour gap before `[15,16]`. In `TownY`, `[09,10]` and `[10,11]` are adjacent, so they merge and create no gap.

Input: ([('p1', '2024-02-01T08:00:00Z', '2024-02-01T09:00:00Z'), ('p2', '2024-02-01T09:00:00Z', '2024-02-01T10:00:00Z'), ('p3', '2024-02-01T10:30:00Z', '2024-02-01T12:00:00Z'), ('p4', '2024-02-01T11:00:00Z', '2024-02-01T13:00:00Z'), ('p5', '2024-02-01T14:00:00Z', '2024-02-01T14:30:00Z')], [('p1', 'OR', 'X', 'TownZ', 'A'), ('p2', 'OR', 'X', 'TownZ', 'B'), ('p3', 'OR', 'X', 'TownZ', 'C'), ('p4', 'OR', 'X', 'TownZ', 'D'), ('p5', 'OR', 'X', 'TownZ', 'E')])

Expected Output: {'TownZ': 1.5}

Explanation: Merged intervals are `[08:00,10:00]`, `[10:30,13:00]`, and `[14:00,14:30]`. The gaps are 0.5 hours and 1.0 hour, totaling 1.5 hours.

Hints

After joining by `party_id`, collect all `(start, end)` intervals for each town in a hash map.
Sort each town's intervals by start time, then scan once: merge when `next_start <= current_end`; otherwise add the gap `next_start - current_end`.

Quick Overview

This question evaluates skills in dataset joins, temporal interval aggregation and merging, gap computation, UTC time handling, and algorithmic complexity analysis alongside appropriate data-structure selection.