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 Onsite 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 time blocks per neighborhood

Quick Overview

This question evaluates a candidate's ability to perform interval merging and temporal aggregation across joined datasets, testing algorithmic efficiency, data-processing skills, and handling of sorting and grouping in the Coding & Algorithms domain.

Company: Scale AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two datasets: 1. **Parties**: - `party_id` (string or integer) - `start_timestamp` (e.g., UNIX timestamp or datetime) - `end_timestamp` (same type as `start_timestamp`, and `end_timestamp > start_timestamp`) 2. **PartyLocations**: - `party_id` - `neighborhood` (string) - `city` (string) - `state` (string) Assume each `party_id` appears exactly once in `Parties` and once in `PartyLocations`. Define a **party time block** for a given `(neighborhood, city, state)` as a **maximal continuous time interval** during which there is at least one ongoing party in that neighborhood. If two party intervals in the same neighborhood overlap or touch (i.e., the end of one equals the start of another), they belong to the same block. **Task** Given the `Parties` and `PartyLocations` data, compute all party time blocks for each neighborhood. **Output** Return a list of records with the following fields: - `neighborhood` - `city` - `state` - `block_start_timestamp` - `block_end_timestamp` Each record represents one maximal merged time block for that neighborhood. The list should be sorted by `state`, then `city`, then `neighborhood`, then `block_start_timestamp`. You may assume there are up to \(10^5\) parties in total and should design an algorithm that is efficient for this input size.

Quick Answer: This question evaluates a candidate's ability to perform interval merging and temporal aggregation across joined datasets, testing algorithmic efficiency, data-processing skills, and handling of sorting and grouping in the Coding & Algorithms domain.

You are given two lists: `parties` and `party_locations`. Each party appears exactly once in each list. A party belongs to one exact location identified by `(neighborhood, city, state)`, and has a time interval `[start_timestamp, end_timestamp]` with `end_timestamp > start_timestamp`. For each exact location, compute all maximal continuous time blocks during which at least one party is happening. Two party intervals belong to the same block if they overlap or if one ends exactly when the next begins. Return all merged blocks sorted by `state`, then `city`, then `neighborhood`, then `block_start_timestamp`.

Constraints

0 <= len(parties) == len(party_locations) <= 100000
Each `party_id` appears exactly once in `parties` and exactly once in `party_locations`
`start_timestamp < end_timestamp` for every party
Timestamps are integers and may be negative

Examples

Input: ([(1, 1, 5), (2, 3, 7), (3, 7, 10), (4, 12, 15), (5, 2, 4)], [(1, 'Downtown', 'Austin', 'TX'), (2, 'Downtown', 'Austin', 'TX'), (3, 'Downtown', 'Austin', 'TX'), (4, 'Downtown', 'Austin', 'TX'), (5, 'Midtown', 'Austin', 'TX')])

Expected Output: [{'neighborhood': 'Downtown', 'city': 'Austin', 'state': 'TX', 'block_start_timestamp': 1, 'block_end_timestamp': 10}, {'neighborhood': 'Downtown', 'city': 'Austin', 'state': 'TX', 'block_start_timestamp': 12, 'block_end_timestamp': 15}, {'neighborhood': 'Midtown', 'city': 'Austin', 'state': 'TX', 'block_start_timestamp': 2, 'block_end_timestamp': 4}]

Explanation: In Downtown, intervals [1,5], [3,7], and [7,10] overlap or touch, so they merge into [1,10]. The interval [12,15] is separate. Midtown has only one interval [2,4].

Input: ([(10, 0, 2), (11, 2, 3), (12, 5, 6), (13, 1, 4)], [(10, 'Soho', 'New York', 'NY'), (11, 'Soho', 'New York', 'NY'), (12, 'Soho', 'Albany', 'NY'), (13, 'Mission', 'San Francisco', 'CA')])

Expected Output: [{'neighborhood': 'Mission', 'city': 'San Francisco', 'state': 'CA', 'block_start_timestamp': 1, 'block_end_timestamp': 4}, {'neighborhood': 'Soho', 'city': 'Albany', 'state': 'NY', 'block_start_timestamp': 5, 'block_end_timestamp': 6}, {'neighborhood': 'Soho', 'city': 'New York', 'state': 'NY', 'block_start_timestamp': 0, 'block_end_timestamp': 3}]

Explanation: The two Soho parties in New York touch at time 2, so they merge into [0,3]. Soho in Albany is a different location, so it stays separate. Results are sorted by state, city, neighborhood, then block start.

Input: ([], [])

Expected Output: []

Explanation: With no parties, there are no blocks.

Input: ([('a', -5, -1), ('b', -1, 2), ('c', 10, 12), ('d', 11, 13)], [('a', 'Old Town', 'Denver', 'CO'), ('b', 'Old Town', 'Denver', 'CO'), ('c', 'Old Town', 'Denver', 'CO'), ('d', 'Old Town', 'Denver', 'CO')])

Expected Output: [{'neighborhood': 'Old Town', 'city': 'Denver', 'state': 'CO', 'block_start_timestamp': -5, 'block_end_timestamp': 2}, {'neighborhood': 'Old Town', 'city': 'Denver', 'state': 'CO', 'block_start_timestamp': 10, 'block_end_timestamp': 13}]

Explanation: The first two intervals touch at -1, so they merge into [-5,2]. The last two overlap and merge into [10,13].

Input: ([(42, 100, 101)], [(42, 'Center', 'Boston', 'MA')])

Expected Output: [{'neighborhood': 'Center', 'city': 'Boston', 'state': 'MA', 'block_start_timestamp': 100, 'block_end_timestamp': 101}]

Explanation: A single party forms a single block.

Solution

def solution(parties, party_locations):
    from collections import defaultdict

    location_by_party = {}
    for party_id, neighborhood, city, state in party_locations:
        location_by_party[party_id] = (state, city, neighborhood)

    intervals_by_group = defaultdict(list)
    for party_id, start_timestamp, end_timestamp in parties:
        state, city, neighborhood = location_by_party[party_id]
        intervals_by_group[(state, city, neighborhood)].append((start_timestamp, end_timestamp))

    result = []

    for state, city, neighborhood in sorted(intervals_by_group.keys()):
        intervals = sorted(intervals_by_group[(state, city, neighborhood)], key=lambda x: (x[0], x[1]))

        current_start = None
        current_end = None

        for start_timestamp, end_timestamp in intervals:
            if current_start is None:
                current_start = start_timestamp
                current_end = end_timestamp
            elif start_timestamp <= current_end:
                if end_timestamp > current_end:
                    current_end = end_timestamp
            else:
                result.append({
                    'neighborhood': neighborhood,
                    'city': city,
                    'state': state,
                    'block_start_timestamp': current_start,
                    'block_end_timestamp': current_end
                })
                current_start = start_timestamp
                current_end = end_timestamp

        if current_start is not None:
            result.append({
                'neighborhood': neighborhood,
                'city': city,
                'state': state,
                'block_start_timestamp': current_start,
                'block_end_timestamp': current_end
            })

    return result

Time complexity: O(n log n). Space complexity: O(n).

Hints

First join the two datasets by `party_id`, then group intervals by the exact location `(state, city, neighborhood)`.
For each location, sort intervals by start time and merge while the next interval starts at or before the current merged end.

Quick Overview