Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Amazon coding round, one question the whole time. Pretty focused session on intervals, which sounds manageable until you're actually in it and they start asking about every edge case you forgot to mention.

Questions Asked (1)

You're given a sorted list of non-overlapping closed intervals and a new interval. Insert the new interval into the list, merging any overlaps, so the result stays sorted and overlap-free. Walk through your approach, complexity analysis, and handle edge cases like insertion at the start or end, full containment, and an empty input list.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I got the basic merge logic down pretty quick but then they kept pulling on edge cases.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Walk through a linear scan approach that processes intervals in three phases: those entirely before the new interval, those overlapping (which get merged), and those entirely after. Clearly state the O(n) time and O(n) space complexity, and explicitly address edge cases like empty input, insertion at start/end, and full containment.

Pro tip: Mention that since the input is sorted and non-overlapping, a linear scan is optimal—no need for binary search unless you're only finding the insertion point. Also, clarify that you're returning a new list to avoid mutating the input, which is often expected in production code.

1. Clarify and Restate

Confirm the problem: intervals are sorted, non-overlapping, closed, and you need to insert and merge. Ask if the input can be modified or if a new list is preferred.

2. Outline the Three-Phase Scan

Explain that you'll iterate through intervals: first add all intervals that end before the new interval starts, then merge all overlapping intervals with the new one, then add the remaining intervals.

3. Detail the Merge Logic

While merging, update the new interval's start to min(current.start, new.start) and end to max(current.end, new.end). Continue until an interval starts after the new interval ends.

4. Analyze Complexity

State that time complexity is O(n) because each interval is visited once, and space complexity is O(n) for the output list (or O(1) extra if modifying in place).

5. Cover Edge Cases

Explicitly mention: empty input list, new interval before all, after all, completely contained within an existing interval, and completely containing existing intervals.

Key Points to Mention

Sorted and non-overlapping property allows a single linear pass without sorting.
Three-phase approach: before, merge, after.
Merge condition: intervals overlap if current.start <= new.end and current.end >= new.start.
Time complexity O(n), space complexity O(n) for output (or O(1) extra if in-place).
Edge cases: empty list, insertion at beginning/end, full containment (new interval inside existing or vice versa).
Return a new list to avoid side effects unless explicitly allowed to modify input.

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