Compute unique duration by merging intervals
Problem
You are provided with an autonomous-driving clip dataset, where each row represents a time interval from a driving run.
Table: clips
| column | type | description |
|---|---|---|
set_id | INT | Session/clip set identifier |
run_id | STRING | Driving run identifier (e.g., YYYYMMDD_HHMMSS) |
start_time | INT | Clip start time offset (seconds) |
end_time | INT | Clip end time offset (seconds) |
set_number | INT | Dataset/source identifier |
Assume each interval is half-open: [start_time, end_time), meaning its duration is calculated as end_time - start_time.
For a given run_id, intervals may exhibit the following characteristics:
- They can overlap (partially or fully).
- They can be duplicated or redundant.
- They may have gaps, meaning they are non-contiguous.
Task
For each unique run_id, compute the cumulative deduplicated time. This metric represents the total duration covered by the union of all intervals associated with that run_id, after merging any overlaps.
Example Input
For run_id 20250101_122334:
- set 1:
[58, 70) - set 2:
[57, 69) - set 3:
[55, 72) - set 4:
[56, 71) - set 5:
[80, 100)
For run_id 20250102_101010:
- set 6:
[43, 62)
Expected Output
The result should contain two columns:
run_idcumulative_unique_time(in the same unit as the time offsets)
Using the example above, the expected output values would be:
20250101_122334→3920250102_101010→19
Requirements
- Provide a SQL solution to compute
cumulative_unique_timeperrun_id. - Provide a Python solution to compute the same metric, given a list or dataframe of intervals.
AI interview prep
Core dilemma
Efficiently merging potentially overlapping and redundant time intervals to calculate a unique cumulative duration, grouped by an identifier, using both SQL and a general-purpose programming language.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Compute unique duration by merging intervals
Problem
You are provided with an autonomous-driving clip dataset, where each row represents a time interval from a driving run.
Table: clips
| column | type | description |
|---|---|---|
set_id | INT | Session/clip set identifier |
run_id | STRING | Driving run identifier (e.g., YYYYMMDD_HHMMSS) |
start_time | INT | Clip start time offset (seconds) |
end_time | INT | Clip end time offset (seconds) |
set_number | INT | Dataset/source identifier |
Assume each interval is half-open: [start_time, end_time), meaning its duration is calculated as end_time - start_time.
For a given run_id, intervals may exhibit the following characteristics:
- They can overlap (partially or fully).
- They can be duplicated or redundant.
- They may have gaps, meaning they are non-contiguous.
Task
For each unique run_id, compute the cumulative deduplicated time. This metric represents the total duration covered by the union of all intervals associated with that run_id, after merging any overlaps.
Example Input
For run_id 20250101_122334:
- set 1:
[58, 70) - set 2:
[57, 69) - set 3:
[55, 72) - set 4:
[56, 71) - set 5:
[80, 100)
For run_id 20250102_101010:
- set 6:
[43, 62)
Expected Output
The result should contain two columns:
run_idcumulative_unique_time(in the same unit as the time offsets)
Using the example above, the expected output values would be:
20250101_122334→3920250102_101010→19
Requirements
- Provide a SQL solution to compute
cumulative_unique_timeperrun_id. - Provide a Python solution to compute the same metric, given a list or dataframe of intervals.