Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Meta SWE coding round, one question on merging two sorted interval lists. Pretty clean problem but the edge cases around touching endpoints tripped me up more than I expected.

Questions Asked (1)

Given two sorted, internally non-overlapping lists of closed integer intervals, merge them into a single sorted list of non-overlapping intervals covering the union of all input intervals. Intervals that overlap or share an endpoint must be combined.

Algorithms & Data Structures

Author's notes

My first instinct was to just concatenate both lists and run a standard merge pass, which is basically right, but I fumbled the touching-endpoint condition.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pointer technique to traverse both lists simultaneously, merging intervals on the fly. At each step, select the interval with the smaller start, then merge it with the last interval in the result if they overlap or touch; otherwise, append it. Continue until all intervals from both lists are processed.

Pro tip: Clarify upfront that intervals are closed and that touching endpoints count as overlapping, then handle edge cases like empty lists or one list being exhausted early. This shows attention to detail and prevents off-by-one errors.

1. Clarify and Validate

Confirm that intervals are closed, sorted, and internally non-overlapping. Ask about edge cases such as empty lists or single intervals.

2. Initialize Pointers and Result

Set pointers i and j to the start of each list, and initialize an empty result list to store merged intervals.

3. Merge While Both Lists Have Intervals

While i < len(list1) and j < len(list2), pick the interval with the smaller start. If the result is empty or the picked interval does not overlap/touch the last interval in result, append it; otherwise, merge by updating the end of the last interval to the maximum of both ends.

4. Process Remaining Intervals

After one list is exhausted, iterate through the remaining intervals of the other list, merging them with the last interval in result if they overlap/touch, or appending them otherwise.

5. Return Result

Return the merged list of non-overlapping intervals.

Key Points to Mention

Two-pointer technique for linear time complexity O(m+n).
Handling of overlapping and touching intervals (e.g., [1,3] and [3,5] merge to [1,5]).
Edge cases: empty lists, one list empty, intervals that are completely contained within another.
In-place merging vs. creating a new list (trade-offs).
Time and space complexity analysis: O(m+n) time, O(m+n) space for output.
Correctness proof: invariant that result remains sorted and non-overlapping.

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