Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jun 2026

Summary

Google SWE coding round with a geometry/interval problem that looks deceptively simple until you're actually in the room trying to explain edge cases about infinity. Pretty standard algorithmic interview but the problem had enough wrinkles to keep me on my toes.

Questions Asked (1)

You're given a list of planets on a 1D number line, each defined by a center coordinate and a radius of gravitational influence. Every planet makes an interval unsafe. Find all maximal continuous safe intervals on the real line, including potentially unbounded ones on either end, and return them sorted.

Algorithms & Data Structures

Author's notes

My first instinct was to just merge the unsafe intervals and return the gaps, which is basically right, but I fumbled the unbounded ends.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model each planet as an interval [center - radius, center + radius] and merge overlapping or touching intervals to find the union of unsafe regions. Then, the safe intervals are the gaps between these merged intervals, including (-infinity, first_start) and (last_end, +infinity) if they exist. Return the safe intervals sorted by their start points.

Pro tip: Clarify edge cases upfront: whether intervals that just touch (e.g., [1,2] and [2,3]) are considered overlapping, and whether the safe intervals should be open or closed. This shows attention to detail and prevents incorrect assumptions.

1. Clarify and Define

Confirm with the interviewer whether intervals are inclusive, whether touching intervals merge, and the expected output format (e.g., open/closed intervals).

2. Transform to Intervals

Convert each planet into an unsafe interval [center - radius, center + radius].

3. Sort and Merge

Sort intervals by start point, then merge overlapping or touching intervals to form a list of disjoint unsafe intervals.

4. Identify Safe Gaps

Iterate through the merged intervals to find gaps between them, including unbounded gaps before the first and after the last interval.

5. Return Sorted Result

Collect the safe intervals in order and return them, ensuring they are sorted by start point.

Key Points to Mention

Time complexity: O(n log n) due to sorting, which is optimal for comparison-based sorting.
Space complexity: O(n) for storing intervals and the result.
Handling of unbounded intervals: use -infinity and +infinity or null to represent them.
Edge cases: no planets (entire line safe), all planets overlapping (no safe intervals), planets with zero radius.
Definition of 'maximal' safe intervals: they cannot be extended without hitting an unsafe region.
Potential pitfalls: integer overflow when computing center ± radius, and floating-point precision if coordinates are not integers.

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