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.

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.

Hints

  1. Maintain the union of contaminated regions as a set of disjoint, merged intervals kept sorted by start point rather than tracking every individual point.
  2. 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.
  3. 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.

Loading coding console...