When the Hours Touch

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
mid
Asked in
Lyft

Problem

Online stretches in this status export arrive unsorted, and a flaky app reconnecting mid-session leaves many of them overlapping or meeting exactly end-to-end, each a [start, end] pair of timestamps in seconds with sub-second fractions. Collapse a driver's sessions into the distinct windows of time the driver was actually online, earliest window first.

Two sessions that overlap are really one. Find the windows a driver was actually online.

Example 1

Input:

sessions = [[10,30.5],[4.5,12],[40,50.25],[33,42]]

Output:

[[4.5,30.5],[33,50.25]]

Example 2

Input:

sessions = [[0,15],[15,20],[30,35]]

Output:

[[0,20],[30,35]]

Worked solution and explanation

Why this problem exists in real interviews

This is interval coalescing wearing a session-cleanup costume. The skill being probed is whether you know the merge only works AFTER you sort by start time. The data hands you sessions in arrival order, and two overlapping stretches are almost never next to each other, so the candidate who walks the raw list comparing each session to the previous one quietly reports overlapping windows as separate. And because the timestamps are continuous, you cannot dodge the merge by dumping every covered instant into a set and regrouping contiguous points; there is no finite grid to enumerate. Sort by start first and every mergeable pair becomes adjacent; that single invariant is the whole problem.

Break down the requirements

Step 1: Sort by start time to make overlaps adjacent

Sort the sessions so they run in start order. Two-element lists already compare on their first element, which is the start, so a plain sorted(sessions) does it and no custom key is needed. When two sessions share a start, the one with the smaller end comes first, and the merge takes the larger end either way. Once sorted, any session that overlaps an earlier one must overlap the window you are building, because nothing with an earlier start is still ahead of you. A single pass over the unsorted input never establishes this.

Step 2: Sweep, extending a running window

Seed the result with the first session. For each later session, if its start is less than or equal to the current window's end, it overlaps or touches, so extend the window's end to the max of the two ends. Otherwise it starts a fresh window. The 'less than or equal' is what makes back-to-back sessions like [0.0, 15.0] and [15.0, 20.0] collapse into [0.0, 20.0].

Step 3: Take the max of the ends, not the latest end

When a session sits fully inside the current window, its end is smaller, so assigning the new end would shrink the window and lose coverage. Always extend with max(last[1], end). This is the line that handles [1.0, 100.0] swallowing [20.0, 30.0].

The solution

Sort by start, sweep a running window
def merge_sessions(sessions):
    if not sessions:
        return []
    ordered = sorted(sessions)
    merged = [list(ordered[0])]
    for start, end in ordered[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged
Single pass, no sort
Walk the list in arrival order and compare each session to the previous one. On [[10.0, 30.5], [4.5, 12.0], ...] the [4.5, 12.0] arrives after [10.0, 30.5], so a forward-only scan either emits it as a separate window or extends in the wrong direction and loses the 4.5 start. Wrong answer, and it looks right on already-sorted inputs, which is how it slips through.
Sort then sweep
Sorting guarantees that if a session overlaps anything earlier, it overlaps the window currently being built. One comparison against the last window suffices, and every overlap is caught.

Common follow-up questions