Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Uber SWE interview with a geometry/sweep-line problem that looked deceptively clean on the surface. The algorithm constraints made it interesting but I definitely fumbled some of the edge case discussion.

Questions Asked (1)

You're given an array of lamps, each defined by a center position and radius, illuminating a closed interval on the number line. The brightness at any point is how many intervals cover it. Return the smallest coordinate with maximum brightness, using an O(n log n) algorithm without iterating over every point. Explain your approach, how you handle ties, and how you'd deal with large coordinates, negatives, and floating-point radii.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was a difference array which obviously breaks down with coordinates up to 1e9.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model each lamp as two events: +1 at start (center - radius) and -1 at end (center + radius). Sort events by coordinate, sweep to compute brightness, and track the smallest coordinate where the maximum brightness is achieved. Use a tie-breaking rule that processes +1 events before -1 events at the same coordinate to correctly handle closed intervals.

Pro tip: Mention that you can avoid floating-point issues by scaling coordinates to integers if radii are given as decimals, or by using exact rational arithmetic. Also, clarify that the maximum brightness is the peak of the sweep, and the smallest coordinate is found by checking after each event group.

1. Event representation

For each lamp, create two events: (start, +1) and (end, -1). Use the interval [center - radius, center + radius].

2. Sort events

Sort all events by coordinate. For ties, process +1 events before -1 events to handle closed intervals correctly.

3. Sweep and track maximum

Initialize current brightness = 0, max brightness = 0, and best coordinate = -infinity. Iterate through sorted events, updating current brightness and checking if it exceeds max brightness. When it does, update max brightness and record the current event's coordinate as best coordinate.

4. Handle ties and edge cases

If multiple coordinates have the same max brightness, the first one encountered during the sweep (smallest coordinate) is kept. For large coordinates, use appropriate data types (e.g., 64-bit integers or doubles). For negatives, ensure sorting handles them naturally.

5. Complexity and optimizations

The algorithm runs in O(n log n) due to sorting. Space is O(n). Discuss potential optimizations like coordinate compression if needed, but not required.

Key Points to Mention

Event-based sweep line algorithm
Tie-breaking: process +1 before -1 at same coordinate
Closed intervals: endpoints are included
Handling large coordinates: use 64-bit integers or doubles
Floating-point radii: consider scaling to integers or using exact arithmetic
Time complexity O(n log n), space O(n)

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.