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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Waymo.

What role is this question designed for?

This question is commonly asked for Site Reliability Engineer candidates at Waymo during technical interviews.

Determine Complete Interval Coverage

Company: Waymo

Role: Site Reliability Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You need to process a stream of real-valued points on a one-dimensional target segment from 0 to 50. Each time a point `x` arrives, it contaminates the interval `[x - 0.5, x + 0.5]`. Contamination is permanent, and intervals from different points may overlap. Design a function that receives one point at a time as a `double` and returns a `bool` indicating whether the entire target segment `[0, 50]` is fully contaminated after processing that point. Notes: - Points may arrive in any order. - A point may be any real value; only its overlap with `[0, 50]` matters. - You should support repeated updates efficiently.

Quick Answer: This question evaluates understanding of interval coverage, streaming or online algorithms, and data structures for maintaining dynamic unions of intervals as points arrive.

You process a stream of real-valued points on the one-dimensional target segment `[0, 50]`. Each arriving point `x` permanently contaminates the closed interval `[x - 0.5, x + 0.5]` (a length-1 region). Contamination never goes away, and the regions from different points may overlap. Implement `solution(points)` which receives the full sequence of points (as a list of doubles, in arrival order) and returns a list of booleans of the same length: the i-th boolean is `true` if and only if the entire target segment `[0, 50]` is fully contaminated after the first `i+1` points have been processed. **Notes** - Points may arrive in any order. - A point may be any real value; only the overlap of its interval with `[0, 50]` matters (points whose interval lies entirely outside `[0, 50]` change nothing). - Updates should be supported efficiently (amortized near-constant time per point), so merging intervals as they arrive is preferred over rescanning everything each time. In an interview this would be modeled as a stateful object whose update method takes one `double` and returns one `bool`; here the equivalent contract is a single function over the whole stream so the behavior after every point can be checked deterministically.

Constraints

The target segment is fixed at [0, 50].
Each point contaminates exactly the closed interval [x - 0.5, x + 0.5].
Contamination is permanent and cumulative across all processed points.
Points are real numbers (doubles) and may be negative or exceed 50.
0 <= number of points <= 10^6; the solution must support efficient incremental updates.

Examples

Input: ([0.5, 1.5, 2.5],)

Expected Output: [False, False, False]

Explanation: Three points cover [0,1], [1,2], and [2,3], so only [0,3] of the target [0,50] is contaminated after each arrival. The segment is never fully covered, so every answer is False.

Input: ([],)

Expected Output: []

Explanation: No points arrive, so no coverage status is produced.

Input: ([25.0],)

Expected Output: [False]

Explanation: A single point at 25.0 contaminates only [24.5, 25.5]; the rest of [0,50] is still clean, so the answer is False.

Input: ([100.0],)

Expected Output: [False]

Explanation: Point 100.0 contaminates [99.5, 100.5], which does not overlap [0,50] at all. Coverage of the target segment is unchanged, so the answer is False.

Input: ([-50.0],)

Expected Output: [False]

Explanation: Point -50.0 contaminates [-50.5, -49.5], entirely outside [0,50]. The target stays uncovered, so the answer is False.

Input: ([0.5, 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5, 10.5, 11.5, 12.5, 13.5, 14.5, 15.5, 16.5, 17.5, 18.5, 19.5, 20.5, 21.5, 22.5, 23.5, 24.5, 25.5, 26.5, 27.5, 28.5, 29.5, 30.5, 31.5, 32.5, 33.5, 34.5, 35.5, 36.5, 37.5, 38.5, 39.5, 40.5, 41.5, 42.5, 43.5, 44.5, 45.5, 46.5, 47.5, 48.5, 49.5],)

Expected Output: [False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True]

Explanation: Points 0.5, 1.5, ..., 49.5 each contaminate a length-1 interval; consecutive intervals abut exactly. Only after the 50th point does the union reach all of [0,50], so the final answer is True and every prior answer is False.

Input: ([49.5, 48.5, 47.5, 46.5, 45.5, 44.5, 43.5, 42.5, 41.5, 40.5, 39.5, 38.5, 37.5, 36.5, 35.5, 34.5, 33.5, 32.5, 31.5, 30.5, 29.5, 28.5, 27.5, 26.5, 25.5, 24.5, 23.5, 22.5, 21.5, 20.5, 19.5, 18.5, 17.5, 16.5, 15.5, 14.5, 13.5, 12.5, 11.5, 10.5, 9.5, 8.5, 7.5, 6.5, 5.5, 4.5, 3.5, 2.5, 1.5, 0.5],)

Explanation: The same 50 points arrive in reverse order. Because contamination is order-independent, full coverage of [0,50] is reached only after the last (50th) point, so only the final answer is True.

Hints

Maintain the union of contaminated regions as a set of disjoint, merged intervals kept sorted by start point rather than tracking every individual point.
When a new interval [x-0.5, x+0.5] arrives, merge it with any existing intervals it overlaps or touches, then check whether the single interval that starts at (or before) 0 also reaches 50.
The whole segment [0,50] is covered exactly when one merged interval has start <= 0 and end >= 50. Use a small epsilon for floating-point comparisons, and clip incoming intervals to [0,50] so points outside the target are naturally ignored.

Quick Overview

This question evaluates understanding of interval coverage, streaming or online algorithms, and data structures for maintaining dynamic unions of intervals as points arrive.