Solve two interval array problems
Company: BlackRock
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two interval-based tasks from a technical screen for a data engineering role.
1. **Merge overlapping intervals**
- Input: an array of integer intervals `intervals`, where each interval is `[start, end]`.
- The intervals may be unsorted.
- Return a new array where all overlapping intervals are merged.
- Example: `[[1,3],[2,6],[8,10],[15,18]]` becomes `[[1,6],[8,10],[15,18]]`.
- In the interview, you only need to explain the algorithm clearly; full runnable code is not required.
2. **Insert and merge one interval**
- Input: a list of non-overlapping intervals sorted by start time, plus one additional interval `new_interval`.
- Insert `new_interval` into the list so that the final result is still sorted and contains no overlapping intervals.
- Example: `intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]`, `new_interval = [4,8]` should return `[[1,2],[3,10],[12,16]]`.
- For this task, write code or precise pseudocode that handles edge cases and passes test cases.
Discuss the key edge cases, such as empty input, intervals that fully contain one another, and insertion at the beginning or end.
Overview: This question evaluates proficiency with array and interval-manipulation concepts—specifically sorting, merging overlapping ranges, and robust edge-case handling in interval operations.
Read the full BlackRock Data Engineer interview experience this question came from
Community answers
Answer by binduum12345
Merge Overlapping Intervals
Approach
First, sort the intervals by their starting point. Then traverse them from left to right while maintaining the current merged interval.
For each interval:
If its start is less than or equal to the current end, the intervals overlap. Update the current end to the maximum of both ends.
Otherwise, there is no overlap. Add the current interval to the result and start a new interval.
Example
Input:
[[1,3], [2,6], [8,10], [15,18]]
After sorting:
[[1,3], [2,6], [8,10], [15,18]]
[1,3] and [2,6] overlap → [1,6]
[8,10] does not overlap with [1,6]
[15,18] does not overlap with [8,10]
Output:
[[1,6], [8,10], [15,18]]
Complexity
Sorting: O(n log n)
Traversal: O(n)
Overall: O(n log n)
Output space: O(n)
Edge Cases
Empty input: return an empty result.
One interval: return it unchanged.
Fully contained interval: for example [1,10] and [3,5] remain [1,10].
Touching intervals: [1,3] and [3,5] can be merged into [1,5] because 3 <= 3.
No overlapping intervals: simply return the sorted intervals.
Insert and Merge One Interval
Here the intervals are already sorted and non-overlapping, so there is no need to sort again.
Approach
Process the intervals in three phases:
Phase 1: Intervals completely before new_interval
If:
current_end < new_start
there is no possibility of overlap, so directly add the interval to the result.
Phase 2: Intervals overlapping new_interval
If:
current_start <= new_end
the intervals overlap. Merge them by:
new_start = min(new_start, curr