← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Uber SWE interview, got a classic interval merging problem. Nothing too wild but the O(n) constraint meant you couldn't just brute force it and call it a day.

Questions Asked (1)

Q1

Given a sorted list of non-overlapping intervals and a new interval, insert the new interval into the list, merging any overlapping intervals as needed. Return the resulting sorted, non-overlapping list. Target O(n) time and O(n) space.

Algorithms & Data Structures
Author's notes

I knew the general shape of this problem but the sorted input is actually a gift you have to use properly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Walk through the intervals in three phases: first, add all intervals that end before the new interval starts; second, merge all intervals that overlap with the new interval; third, add the remaining intervals. This yields a single pass O(n) time and O(n) space solution.

Pro tip: Clarify edge cases upfront (empty list, new interval before all, after all, fully contained) and mention that the output list can be built in-place if mutation is allowed, but since the problem asks for O(n) space, creating a new list is fine.

1. Clarify and confirm

Restate the problem, confirm input format (list of intervals, each as [start, end]), and ask about edge cases like empty list or intervals that just touch.

2. Plan the three-phase approach

Explain that you will iterate through intervals, first adding those that end before the new interval starts, then merging overlapping ones, then adding the rest.

3. Implement the merge logic

During the merge phase, update the new interval's start to min(current start, new start) and end to max(current end, new end) until no overlap, then add the merged interval.

4. Analyze complexity

State that the algorithm runs in O(n) time because each interval is visited once, and O(n) space for the output list.

5. Test with examples

Walk through a few examples, including edge cases, to verify correctness and demonstrate thoroughness.

Key Points to Mention

  • The input list is already sorted and non-overlapping, which simplifies the merge process.
  • Overlap condition: two intervals overlap if the start of one is <= the end of the other.
  • During merging, the new interval's start becomes the minimum of the overlapping starts and its end becomes the maximum of the overlapping ends.
  • Time complexity is O(n) because we make a single pass through the intervals.
  • Space complexity is O(n) for the output list; if in-place modification were allowed, it could be O(1) extra space.
  • Edge cases: empty input list, new interval before all, after all, or completely contained within an existing interval.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.