Process time intervals and detect overlaps/gaps
Company: Sierra
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given `n` time intervals representing debug log segments. Each interval has a start time, an end time, and an associated text message.
- Each interval is represented as `(start, end, text)`.
- `start` and `end` are integers representing timestamps in seconds.
- Assume all intervals are half-open: they cover `[start, end)`, i.e., they include `start` and exclude `end`.
- The input intervals are not guaranteed to be in order and may overlap or leave gaps.
### Task 1: Output ordered, merged intervals
Write a function that:
1. Takes as input a list of intervals `[(start_i, end_i, text_i)]`.
2. Sorts them by time and merges overlapping intervals.
- When two or more intervals overlap in time, merge them into a single interval `[min_start, max_end)` where:
- `min_start` is the smallest start time among those intervals.
- `max_end` is the largest end time among those intervals.
- For the merged interval's text, concatenate the texts of the merged intervals in chronological order, separated by a single space.
3. Returns the merged, non-overlapping intervals in ascending order of start time as a list of `(start, end, merged_text)`.
Example (one possible style of input/output):
- Input:
- `[(0, 5, "A"), (3, 10, "B"), (12, 15, "C")]`
- Expected output:
- `[(0, 10, "A B"), (12, 15, "C")]`
(You can assume that the concatenation order for texts is determined by the start time of each interval; if start times are equal, you may break ties arbitrarily.)
### Task 2 (Follow-up): Detect overlaps and gaps
Using the same input model (original, unmerged intervals):
1. Determine whether **any** pair of intervals overlaps in time.
- Two intervals `[s1, e1)` and `[s2, e2)` overlap if their intersection is non-empty, i.e., `max(s1, s2) < min(e1, e2)`.
2. Determine whether there exists **any gap** between the earliest start time and the latest end time.
- A gap exists if, after ordering the intervals by start time, there is at least one pair of consecutive intervals where `next.start > current.end`.
Define and implement appropriate functions/methods to:
- Produce the ordered, merged list of intervals with concatenated texts (Task 1).
- Return booleans or equivalent indicators for:
- "there is at least one overlap" and
- "there is at least one gap" (Task 2).
State the expected time and space complexity of your approach in terms of `n` (the number of intervals).
Quick Answer: This question evaluates the ability to process and manipulate time intervals: sorting and merging overlapping ranges, concatenating associated textual metadata, detecting overlaps and gaps, and reasoning about time and space complexity.
Part 1: Merge Overlapping Log Segments
You are given an unsorted list of debug log intervals. Each interval is a tuple (start, end, text), representing the half-open time range [start, end) and its message. Sort the intervals by time and merge every set of overlapping intervals into one interval. Two intervals overlap only if their intersection is non-empty, so intervals that only touch at an endpoint, such as [1, 4) and [4, 6), must not be merged. For each merged block, concatenate the texts of all intervals inside it in chronological order, separated by a single space. For deterministic output, if two intervals have the same start time, order them by smaller end time first; if both start and end are equal, keep their original input order.