Nuro Data Scientist Interview Experience — Merging Overlapping Vehicle-Run Intervals in SQL and Python

Dataset description

The dataset had several fields: set id, run id, start time, end time, and set number.

The set ids ran from 1 to 6 and represented different recorded segments from autonomous-vehicle sessions. For example, set 1 was about 30 seconds long, set 2 was 23 seconds, set 3 was 19 seconds, and so on.

The run id identified the trip. It used a time-string format such as 20250101_122334, meaning that the trip happened on January 1, 2025 at 12:34. The start time and end time were both two-digit values showing the beginning and end of a clip. The set number indicated which dataset the row came from.

Sets 1 through 5 belonged to the same run id, meaning the same trip. Their time windows had overlaps and gaps; sets 1 through 4 overlapped.

Interval details

• Set 1: start time 58, end time 70
• Set 2: start time 57, end time 69
• Set 3: start time 55, end time 72
• Set 4: start time 56, end time 71
• Set 5: start time 80, end time 100
• Set 6: start time 43, end time 62

Task

Using both SQL and Python, calculate the cumulative deduplicated time for each run id. In other words, merge all of a trip's time intervals and return the total duration without counting overlaps more than once.

SQL example

WITH intervals AS (
    SELECT run_id, start_time, end_time
    FROM your_table
),
merged AS (
    SELECT
        run_id,
        MIN(start_time) AS start_time,
        MAX(end_time) AS end_time
    FROM intervals i1
    WHERE NOT EXISTS (
        SELECT 1
        FROM intervals i2
        WHERE i2.run_id = i1.run_id
          AND i2.start_time < i1.end_time
          AND i2.end_time > i1.start_time
          AND (i2.start_time > i1.start_time
               OR i2.end_time < i1.end_time)
    )
    GROUP BY run_id
)
SELECT
    run_id,
    SUM(end_time - start_time) AS cumulative_unique_time
FROM merged
GROUP BY run_id;

Different databases support interval merging differently. The SQL above was only an illustration; more complicated cases may need window functions or a recursive query.

Python example

from collections import defaultdict

data = [
    {'run_id': '20250101_122334', 'start_time': 58, 'end_time': 70},
    {'run_id': '20250101_122334', 'start_time': 57, 'end_time': 69},
    {'run_id': '20250101_122334', 'start_time': 55, 'end_time': 72},
    {'run_id': '20250101_122334', 'start_time': 56, 'end_time': 71},
    {'run_id': '20250101_122334', 'start_time': 80, 'end_time': 100},
    {'run_id': '20250102_101010', 'start_time': 43, 'end_time': 62},
]

def merge_intervals(intervals):
    # Sort by start time first.
    intervals.sort(key=lambda x: x[0])
    merged = []
    for start, end in intervals:
        if not merged or merged[-1][1] < start:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

intervals_by_run = defaultdict(list)
for row in data:
    intervals_by_run[row['run_id']].append(
        (row['start_time'], row['end_time'])
    )

for run_id, intervals in intervals_by_run.items():
    merged = merge_intervals(intervals)
    total_time = sum(end - start for start, end in merged)
    print(f"Run ID: {run_id}, Cumulative Dedup Time: {total_time}")

The output was:

Run ID: 20250101_122334, Cumulative Dedup Time: 39
Run ID: 20250102_101010, Cumulative Dedup Time: 19

This shows how SQL and Python can calculate cumulative deduplicated time for each trip when analyzing time intervals from autonomous-vehicle data.