Exam Room

Exam Room

What is this problem about?

The Exam Room interview question asks you to design a class that manages seating in a long row of N seats (numbered 0 to N-1). When a student enters, they must sit in the seat that maximizes their distance from the closest person already sitting. If there are multiple such seats, they sit in the one with the lowest number. When a student leaves, their seat becomes empty. You need to implement the seat() and leave(p) functions efficiently.

Why is this asked in interviews?

Companies like Apple and Google use this Design interview pattern to test your ability to manage dynamic intervals. It’s a classic optimization problem that requires balancing multiple constraints (maximizing distance, breaking ties with the smallest index). It evaluates whether you can use sophisticated data structures like a Heap or an Ordered Set to maintain sorted intervals and find the optimal insertion point in logarithmic time.

Algorithmic pattern used

This problem is best solved using an Ordered Set or a Max-Heap of Intervals.

1. Interval Representation: Represent the row as a set of intervals between occupied seats. For example, if seats 0 and 9 are taken in a row of 10, the interval is [0, 9].
2. seat(): Find the interval [a, b] that has the largest "middle point" distance. Also consider the boundaries (distance from 0 or N-1).
3. leave(p): Remove the occupied seat p and merge the two adjacent intervals into one. Using a self-balancing BST or an ordered set helps keep the occupied seats in order, allowing you to find neighbors in O(log S) time.

Example explanation

Row size N=10.

1. seat(): First student sits at 0. (Always pick smallest index if empty).
2. seat(): Second student sits at 9. (Max distance from 0).
3. seat(): Third student sits in the middle of [0, 9], which is index 4. Distance is 4 from 0 and 5 from 9. (Rounded down).
4. leave(4): Seat 4 is now empty. Intervals [0, 4] and [4, 9] merge back to [0, 9].

Common mistakes candidates make

• Linear Search: Using an array and searching for the best seat in O(N) time for every seat() call, which is too slow for large N.
• Ignoring Boundaries: Only checking the gaps between people and forgetting that the seats at the very beginning (0) and very end (N-1) are also valid candidates.
• Rounding errors: Incorrectly calculating the midpoint distance (b - a) / 2.

Interview preparation tip

Practice problems involving "dynamic gaps" or "interval management." This problem is conceptually similar to managing memory blocks or scheduling tasks in a free-time window.