How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Find leftmost point of maximum brightness

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

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.

Quick Answer: 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 a point `x` is the number of intervals that contain `x`. Return the smallest coordinate `x` with maximum brightness. If the maximum brightness occurs over a whole interval of coordinates, return that interval's left endpoint. Solve it in O(n log n) time using an event sweep — without enumerating individual points on the number line (coordinates can be up to 1e9, positions can be negative). Because the lit intervals are closed, a `+1` (interval start) at a coordinate must take effect before any `-1` (interval end) at the same coordinate, so that two intervals merely touching at a shared endpoint are correctly counted as overlapping there. Return `None` (null / empty) when the input is empty.

Constraints

0 <= n (number of lights)
-1e9 <= p <= 1e9
0 <= r <= 1e9
Intervals are closed: light [p, r] covers every x with p - r <= x <= p + r
Two intervals that share only an endpoint coordinate DO overlap there
Return the smallest coordinate achieving the maximum brightness; on an interval of maxima, return its left endpoint
Return None / null for empty input

Examples

Input: ([[-2, 3], [1, 2]],)

Expected Output: -1

Explanation: Lamp [-2,3] lights [-5,1]; lamp [1,2] lights [-1,3]. They overlap on [-1,1] with brightness 2. The smallest such x is -1.

Input: ([[0, 1]],)

Expected Output: -1

Explanation: Single lamp lights [-1,1], brightness 1 everywhere on it. The leftmost point of the maximum is -1.

Input: ([],)

Expected Output: None

Explanation: No lamps, so there is no illuminated coordinate; return None.

Input: ([[5, 0]],)

Expected Output: 5

Explanation: Radius 0 lights only the single point [5,5]; brightness 1 there. The answer is 5.

Input: ([[0, 2], [10, 2], [20, 2]],)

Expected Output: -2

Explanation: Intervals [-2,2], [8,12], [18,22] are disjoint, so maximum brightness is 1. It first occurs at the leftmost start, -2.

Input: ([[0, 5], [1, 5], [2, 5]],)

Expected Output: -3

Explanation: Intervals [-5,5], [-4,6], [-3,7]. All three overlap on [-3,5] with brightness 3. The triple overlap begins at -3.

Input: ([[-10, 1], [-10, 1], [5, 1]],)

Expected Output: -11

Explanation: Two identical lamps light [-11,-9] (brightness 2); lamp [5,1] lights [4,6] (brightness 1). Max brightness 2 starts at -11.

Input: ([[1000000000, 1000000000], [-1000000000, 1000000000]],)

Expected Output: 0

Explanation: Intervals [0, 2e9] and [-2e9, 0] are closed and meet only at x=0, where brightness is 2 (the maximum). The answer is 0, demonstrating start-before-end tie-breaking at a shared endpoint.

Hints

Don't materialize the number line. Convert each lamp [p, r] into two events at coordinates p - r (start, +1) and p + r (end, -1).
Sort events by coordinate. At ties, apply all starts (+1) before any ends (-1) so that intervals touching at a shared endpoint are counted as overlapping at that point.
Sweep left to right tracking a running count. Each time the running count strictly exceeds the previous best, record the current coordinate as the answer — that coordinate is the left endpoint of the segment where the new maximum begins, which is exactly the smallest x with that brightness.
Because you only update on a strict increase, the first (leftmost) coordinate that reaches the global maximum is returned automatically; later coordinates with equal brightness never overwrite it.

Quick Overview

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.