Find leftmost point of maximum brightness
UberSoftware Engineer · Online AssessmentLast updated
This question evaluates understanding of interval overlap counting, efficient use of ordered data structures for range events, tie-breaking logic, and robustness to numeric edge cases such as large coordinates and floating-point radii.
You are given an array of lights, where each light is [p, r] representing a lamp centered at coordinate p on the real number line with radius r, illuminating the closed interval [p − r, p + r]. The brightness at point x is the count of intervals that contain x. Return the smallest coordinate x with maximum brightness. If the maximum brightness occurs over an interval, return its left endpoint. Design an algorithm that runs in O(n log n) time without enumerating individual points on the number line, and explain your approach (e.g., event sweep or ordered map), tie-breaking, and correctness. Discuss how you would handle large coordinates (up to 1e 9), negative positions, and floating-point radii.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.