Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE coding round, got an interval intersection problem. Pretty standard LC-style question but the details trip you up if you're not careful with the pointer logic.

Questions Asked (1)

Given two lists of sorted, non-overlapping closed intervals, find and return all intersecting intervals between the two lists.

Algorithms & Data Structures

Author's notes

I knew the two-pointer approach pretty quickly but fumbled the overlap condition on the first try.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pointer technique to traverse both interval lists simultaneously, comparing the current intervals to find their intersection. At each step, advance the pointer of the interval that ends first, as it cannot intersect with any subsequent interval in the other list.

Pro tip: Clarify upfront that intervals are closed and non-overlapping, and confirm the expected output format (e.g., list of intervals). This shows attention to detail and avoids misinterpretation.

1. Clarify and confirm

Restate the problem to ensure understanding: both lists are sorted, non-overlapping, closed intervals. Ask about output format and edge cases (e.g., empty lists, touching intervals).

2. Initialize pointers

Set two pointers, i and j, to 0, pointing to the first interval in each list. Prepare an empty result list.

3. Iterate and compare

While both pointers are within bounds, compute the intersection of the current intervals: start = max(start1, start2), end = min(end1, end2). If start <= end, add [start, end] to the result.

4. Advance pointers

Move the pointer of the interval with the smaller end time forward. If ends are equal, advance both pointers.

5. Return result

After the loop, return the list of intersecting intervals.

Key Points to Mention

Time complexity: O(m + n) where m and n are the lengths of the two lists, as each interval is visited at most once.
Space complexity: O(1) extra space excluding the output list, which is O(k) for k intersections.
Handling of edge cases: empty lists, intervals that just touch (e.g., [1,2] and [2,3] intersect at point 2), and non-overlapping intervals.
The importance of advancing the pointer with the smaller end time to ensure no intersections are missed.
Closed intervals mean endpoints are inclusive, so intersection condition is start <= end.
The algorithm works because the lists are sorted and non-overlapping, allowing linear traversal.

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