When Hours Collide

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Uber

Problem

A shared room-booking calendar stores each reservation as a [name, start, end] record, and you need to flag every scheduling clash. Ranges are half-open [start, end), so a booking that ends exactly when another begins does not clash. Return each clashing pair once as [name_a, name_b] with the earlier-starting booking first, ordered by the first booking's start and then the second's, or an empty list when nothing clashes.

Two reservations, one slot. Find every clash.

Example 1

Input:

events = [["A",1,5],["B",3,7],["C",6,9],["D",8,10]]

Output:

[["A","B"],["B","C"],["C","D"]]

Example 2

Input:

events = [["X",1,2],["Y",3,4]]

Output:

[]

Worked solution and explanation

What this really is

Strip the calendar costume and this is pairwise interval intersection with two traps that sink otherwise-correct code. First the boundary: the ranges are half-open, so [9, 10) and [10, 12) share the instant 10 but do NOT overlap. Write the test with <= and you flag every back-to-back booking as a clash, which is the one thing a scheduler must never do. Second the order: the input is not sorted, so if you emit pairs in the order the loop happens to find them, two clashes come back in the wrong sequence and exact-match grading fails even though you found every collision. The fix for both is small: a strict two-sided overlap test, each pair written earlier-booking-first, and a final sort of the collected pairs by start time.

Break down the requirements

Step 1: Check every pair once

Walk every pair with a nested loop where the inner index starts one past the outer (j from i + 1). That visits each unordered pair exactly once, so a clash is never reported twice.

Step 2: Test for a real overlap

Two ranges overlap only when start_a < end_b and start_b < end_a, both strict. Because the events are NOT pre-sorted, either one could start first, so you genuinely need both halves of the test: drop one and a reversed, non-touching pair sneaks through as a false clash. A shared boundary fails the strict test, which is exactly what half-open ranges demand.

Step 3: Order the pairs

Write each surviving pair with the earlier-starting booking first, and stash its two start times alongside the names. The loop groups one event's pairs together, which is NOT the promised output order, so sort the collected pairs by (first start, second start) at the end. That final sort is what turns a correct set of clashes into the exact sequence the grader wants.

The solution

All-pairs half-open overlap detection
def find_overlaps(events: list[list]) -> list[list[str]]:
    collisions = []
    for i in range(len(events)):
        name_a, start_a, end_a = events[i]
        for j in range(i + 1, len(events)):
            name_b, start_b, end_b = events[j]
            if start_a >= end_b or start_b >= end_a:
                continue
            if start_a <= start_b:
                collisions.append((start_a, start_b, name_a, name_b))
            else:
                collisions.append((start_b, start_a, name_b, name_a))
    collisions.sort(key=lambda c: (c[0], c[1]))
    return [[name_a, name_b] for _, _, name_a, name_b in collisions]

Common follow-up questions