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.
Overview: This question evaluates understanding of interval coverage, streaming or online algorithms, and data structures for maintaining dynamic unions of intervals as points arrive.
Read the full Waymo Site Reliability Engineer interview experience this question came from
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.
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.