How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find safe travel intervals between planet influences

Quick Overview

This question evaluates interval arithmetic and line-sweep reasoning for computing complements on the real line, testing competencies in sorting, interval merging, and handling unbounded ranges within the Coding & Algorithms domain and focusing on practical application rather than purely conceptual theory.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are planning a space route along a one-dimensional line (the x-axis). You are given a list of planets. Each planet is represented by an integer pair \((c, r)\): - `c` is the coordinate of the planet's center on the x-axis. - `r` is a non-negative integer radius of its gravitational influence. A point `x` on the x-axis is **unsafe** for a space traveler if it lies within the gravitational influence of at least one planet: \[ |x - c_i| \le r_i \quad \text{for some planet } i \] Equivalently, each planet makes the interval \([c_i - r_i,\; c_i + r_i]\) unsafe. Task: - Consider the entire real line as the possible travel path. - Compute all **maximal continuous intervals** on this line where the traveler is **safe**, i.e., points not covered by any planet's unsafe interval. - Return these safe intervals as a sorted list of disjoint intervals. Representation details: - Represent each safe interval as a pair `(start, end)` with `start < end`. - Intervals may be unbounded on the left or right: - Use `-∞` for an interval unbounded to the left (e.g., `(-∞, a)`). - Use `+∞` for an interval unbounded to the right (e.g., `(b, +∞)`). You may assume the input list of planets can be in any order and may contain overlapping or nested gravitational ranges. Return the safe intervals in increasing order of `start`.

Quick Answer: This question evaluates interval arithmetic and line-sweep reasoning for computing complements on the real line, testing competencies in sorting, interval merging, and handling unbounded ranges within the Coding & Algorithms domain and focusing on practical application rather than purely conceptual theory.

You are planning a route along the real x-axis. Each planet is given as a pair (c, r), where c is its center and r is a non-negative radius of gravitational influence. A point x is unsafe if it lies inside at least one planet's influence, meaning |x - c| <= r. So each planet creates an unsafe closed interval [c - r, c + r]. Your task is to return all maximal continuous safe intervals on the real line: regions not covered by any unsafe interval. Represent each safe interval as a tuple (start, end), where the interval means start < x < end. Because JSON/Python literals do not have a direct infinity literal, use None to represent an unbounded side: - (None, a) means (-infinity, a) - (b, None) means (b, +infinity) - (None, None) means the entire real line Return the safe intervals in increasing order. Overlapping, nested, and touching unsafe intervals should be treated as one merged unsafe region.

Constraints

0 <= len(planets) <= 200000
-10^9 <= c <= 10^9
0 <= r <= 10^9

Examples

Input: []

Expected Output: [(None, None)]

Explanation: With no planets, no point is unsafe, so the entire real line is safe.

Input: [(3, 1), (10, 2)]

Expected Output: [(None, 2), (4, 8), (12, None)]

Explanation: The unsafe intervals are [2, 4] and [8, 12]. Their complement is (-infinity, 2), (4, 8), and (12, +infinity).

Input: [(-4, 3), (1, 2), (0, 5)]

Expected Output: [(None, -7), (5, None)]

Explanation: The unsafe intervals are [-7, -1], [-1, 3], and [-5, 5], which merge into one interval [-7, 5].

Input: [(0, 1), (3, 2), (7, 0)]

Expected Output: [(None, -1), (5, 7), (7, None)]

Explanation: The first two unsafe intervals are [-1, 1] and [1, 5], which touch and must be merged into [-1, 5]. The point interval [7, 7] removes only x = 7, leaving a gap (5, 7) and then (7, +infinity).

Input: [(-2, 0), (2, 0)]

Expected Output: [(None, -2), (-2, 2), (2, None)]

Explanation: Each planet blocks only a single point: x = -2 and x = 2. The safe regions are everything else.

Solution

def solution(planets):
    if not planets:
        return [(None, None)]

    intervals = [(c - r, c + r) for c, r in planets]
    intervals.sort()

    merged = []
    for left, right in intervals:
        if not merged or left > merged[-1][1]:
            merged.append([left, right])
        else:
            if right > merged[-1][1]:
                merged[-1][1] = right

    safe = []
    safe.append((None, merged[0][0]))

    for i in range(1, len(merged)):
        prev_right = merged[i - 1][1]
        curr_left = merged[i][0]
        if prev_right < curr_left:
            safe.append((prev_right, curr_left))

    safe.append((merged[-1][1], None))
    return safe

Time complexity: O(n log n). Space complexity: O(n).

Hints

First convert every planet (c, r) into the unsafe interval [c - r, c + r].
Sort the unsafe intervals and merge all overlapping or touching ones. The safe intervals are the gaps before, between, and after the merged intervals.

Quick Overview