Raindrops Wetting: Compute the Fraction of a Surface Wetted After N Raindrops Land

Question

## Problem Raindrops land randomly on a 1D surface of length L. Each raindrop wets a segment of radius R centered at its landing position. After N drops have landed, compute the total wetted length (accounting for overlapping drops). ```python def wetted_length(L: float, R: float, positions: list[float]) -> float: # positions: x-coordinates where drops landed (0 <= x <= L) # each drop wets [x-R, x+R] clamped to [0, L] # returns: total unique wetted length pass ``` **Example:** ``` L=10, R=1 positions = [2.0, 2.5, 7.0] # Segments: [1,3], [1.5,3.5], [6,8] # Union: [1,3.5] + [6,8] -> length 4.5 wetted_length(10, 1, [2.0, 2.5, 7.0]) -> 4.5 ``` ## Follow-ups 1. What is the most efficient way to compute the union length of overlapping intervals? 2. How does sorting the positions before merging reduce complexity from O(n^2) to O(n log n)? 3. How would you extend this to 2D (circular raindrops on a rectangular surface)? 4. If drops evaporate after T time units, how does your algorithm change?

Raindrops Wetting: Compute the Fraction of a Surface Wetted After N Raindrops Land

Question Details

Full Details

Topics

More from Waymo