Uber·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Uber SWE interview that went deep into geometric sampling and probabilistic design. One question, but it had enough layers to fill a whole session.

Questions Asked (1)

Design a class for an axis-aligned square on a 2D plane that can sample a uniformly random point inside it. Then extend the design to support N non-overlapping squares, where sampling picks a point with probability proportional to each square's area. Cover the API design, data structures, sampling algorithm, time/space complexity, and how you'd handle floating-point precision issues.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

The single-square part was fine, just pick random x and y within bounds.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by designing a single Square class with a uniform sampling method, then extend to N squares using a weighted sampling scheme where weights are proportional to area. Discuss the API, data structures (e.g., prefix sums for efficient sampling), time/space complexity, and floating-point precision handling.

Pro tip: Mention that using prefix sums of areas allows O(log N) sampling via binary search, but if areas are similar, a simpler O(1) approach with rejection sampling might be acceptable—showing awareness of trade-offs.

1. Design the Square class

Define a Square with center, side length, and a method to sample a uniform random point inside. Ensure the sampling is correct by generating coordinates uniformly within the square's bounds.

2. Extend to N squares

Create a collection of non-overlapping squares. Compute each square's area and store cumulative sums to enable weighted sampling proportional to area.

3. Implement sampling algorithm

Generate a random number between 0 and total area, then use binary search on cumulative sums to select a square, and finally sample uniformly within that square.

4. Analyze complexity

Discuss time complexity: O(log N) for selection plus O(1) for point generation; space complexity O(N) for storing squares and prefix sums.

5. Address floating-point precision

Handle precision by using double precision, avoiding exact equality comparisons, and considering epsilon-based adjustments or alternative methods like rejection sampling if needed.

Key Points to Mention

Uniform sampling within a square: generate x and y independently from uniform distributions over the square's intervals.
Weighted sampling proportional to area: use cumulative area array and binary search for O(log N) selection.
API design: methods like samplePoint() for single square, and addSquare(), samplePoint() for the collection.
Time and space complexity: O(1) for single square sampling, O(log N) for N squares with prefix sums, O(N) space.
Floating-point precision: use double, avoid exact comparisons, consider epsilon for boundary cases, and ensure cumulative sums are accurate.
Non-overlapping constraint: ensures area sum is valid and sampling is independent; if overlapping, need to handle union area differently.

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