Uber·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Onsite coding round at Uber for a SWE role. One question, seat assignment, which sounds straightforward until you're actually implementing it under pressure.

Questions Asked (1)

Implement a class that assigns seats one at a time in a row of n seats, always picking the seat that maximizes the minimum distance to any already-occupied seat. The first person goes to seat 0, and seats are never vacated.

Algorithms & Data Structures

Author's notes

I recognized this as basically LeetCode 855 but without the leave() part, which actually made it simpler.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then propose an efficient solution using a priority queue to track available intervals, prioritizing by maximum minimum distance. Walk through the algorithm step-by-step, analyze time and space complexity, and discuss potential optimizations or alternative approaches.

Pro tip: Mention that this is essentially the 'Exam Room' problem (LeetCode 855) and that using a priority queue with a custom comparator yields O(log n) per seat assignment, which is optimal for this problem.

1. Understand the problem and constraints

Ask clarifying questions about n (range, type), whether seats are assigned one at a time, and if there are any constraints on time complexity. Confirm that the first seat is always 0 and seats are never vacated.

2. Design the data structures

Use a priority queue (max-heap) to store available intervals, prioritized by the minimum distance to occupied seats. Also maintain a set or boolean array to track occupied seats for quick lookup.

3. Define the interval and priority

For an interval [left, right] of unoccupied seats, the best seat is the one that maximizes the minimum distance to occupied seats. Compute the distance as min(seat - left, right - seat) and prioritize intervals by this distance, breaking ties by smaller seat index.

4. Implement seat assignment

When assigning a seat, pop the interval with the highest priority, choose the seat that maximizes the minimum distance (usually the middle), mark it occupied, and push the resulting left and right sub-intervals back into the priority queue.

5. Analyze complexity and test edge cases

Each seat assignment takes O(log n) time due to heap operations, and space is O(n). Test with small n, n=1, and sequences of assignments to ensure correctness.

Key Points to Mention

Priority queue (max-heap) to efficiently select the interval with the largest minimum distance.
Handling edge intervals: when the interval touches the start or end, the distance is simply the distance to the occupied seat.
Tie-breaking rule: when multiple seats have the same minimum distance, choose the smallest seat index (as per typical problem statement).
Time complexity: O(log n) per seat assignment, O(n log n) for n assignments; space complexity O(n).
Alternative approaches: using a balanced BST or a sorted list, but priority queue is optimal.
Connection to the 'Exam Room' problem (LeetCode 855) and potential follow-up questions about dynamic seat vacating.

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