Katkat

Determine Complete Interval Coverage

WaymoSite Reliability Engineer · Technical Screen

Last updated

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

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.