855. Exam Room - Solution & Explanation

Q: Is Exam Room easy or hard?

Exam Room is rated Medium but leans toward design-heavy reasoning. The greedy insight about choosing the largest gap is straightforward, but implementing the interval heap structure with correct merges requires careful handling of edge cases.

Q: Exam Room Python or Java solution?

Python implementations often use a sorted list with binary insertion for the simpler approach or heapq with custom interval logic for the optimized solution. Java implementations typically rely on PriorityQueue and TreeSet structures to maintain ordered seats and interval boundaries.

Q: How to solve Exam Room in O(log n)?

Model the exam room as intervals of empty seats and store them in a max heap ordered by seating distance. When a student arrives, pop the largest interval, place the student at the optimal midpoint, then split the interval into two smaller ones and push them back. Heap operations keep each update at O(log n).

Q: What is the best approach for Exam Room?

The interval-based design using a max heap (priority queue) is considered the best approach. It stores empty seat ranges and always selects the interval that maximizes distance to the nearest student. Both seat() and leave() operations run in O(log n) time, which is more efficient than scanning all occupied seats.

Q: Is Exam Room asked at Google/Amazon/Meta?

Exam Room is a classic design-style interview problem that appears in large tech company preparation lists. Variations of seat allocation or interval scheduling have been reported in interviews at companies like Google, Amazon, and Meta. The problem tests data structure design, priority queues, and edge-case reasoning.

Q: What data structure is used in Exam Room?

Common implementations use either a sorted set of occupied seats or a max heap storing empty intervals. The optimized design also uses hash maps to quickly merge adjacent intervals when a student leaves. Together these structures allow efficient seat selection and interval updates.

Q: What is the time complexity of Exam Room?

Using a sorted list of occupied seats leads to O(n) time for seat() because you scan all gaps to find the maximum distance. The optimized heap-based interval solution reduces operations to O(log n) time. Space complexity in both designs is O(n) since you track occupied seats or intervals.

The problem

There is an exam room with n seats in a single row labeled from 0 to n - 1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number 0.

Design a class that simulates the mentioned exam room.

Implement the ExamRoom class:

ExamRoom(int n) Initializes the object of the exam room with the number of the seats n.
int seat() Returns the label of the seat at which the next student will set.
void leave(int p) Indicates that the student sitting at seat p will leave the room. It is guaranteed that there will be a student sitting at seat p.

Example 1:

Input
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
Output
[null, 0, 9, 4, 2, null, 5]

Explanation
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
examRoom.seat(); // return 9, the student sits at the last seat number 9.
examRoom.seat(); // return 4, the student sits at the last seat number 4.
examRoom.seat(); // return 2, the student sits at the last seat number 2.
examRoom.leave(4);
examRoom.seat(); // return 5, the student sits at the last seat number 5.

Constraints:

1 <= n <= 10⁹
It is guaranteed that there is a student sitting at seat p.
At most 10⁴ calls will be made to seat and leave.

Approach overview

Problem Overview: You manage an exam room with n seats numbered 0 to n-1. Each arriving student chooses a seat that maximizes the distance to the closest occupied seat. If multiple seats give the same distance, the student picks the smallest index. You must implement seat() and leave(p) efficiently.

Approach 1: Sorted List of Occupied Seats (O(n) seat, O(n) leave)

This approach maintains a sorted list (or ordered set) of occupied seat indices. When a student calls seat(), iterate through the sorted seats and compute the largest possible distance between adjacent occupied seats. Also check the edges: the distance from seat 0 to the first student and from the last student to n-1. The best candidate seat is either the midpoint between two occupied seats or an edge seat. Insert the chosen seat into the sorted structure and maintain order.

The key idea is that the optimal seat always lies either at the midpoint of the largest gap or at a boundary. Computing the midpoint of each gap requires scanning the occupied list, which takes O(n) time. Insertion or deletion in a list also costs O(n). Space complexity is O(n) because you store all occupied seats. This approach is straightforward and easy to implement, especially in Python with a list or in C++ with an ordered container from Ordered Set.

Approach 2: Maximum Heap of Intervals (O(log n) seat, O(log n) leave)

A more scalable design models the room as intervals of empty seats. Each interval represents the gap between two occupied seats, such as (left, right). The best seat inside an interval is the midpoint that maximizes the distance to neighbors. Store intervals in a max heap ordered by their effective seating distance (largest first), with ties broken by smaller seat index.

When seat() runs, extract the largest interval from the heap. Compute the optimal seat inside it, then split the interval into two new intervals and push them back into the heap. When leave(p) runs, merge the two intervals adjacent to seat p into a larger interval and update the heap. Efficient merging usually requires hash maps that track interval boundaries.

This design relies on a Heap (Priority Queue) to always retrieve the largest gap in O(log n) time. Both seating and leaving operations maintain interval structure with heap updates. Space complexity remains O(n). The approach demonstrates strong Design skills because you model the room as dynamic segments rather than raw seat indices.

Recommended for interviews: Start by explaining the sorted list approach to show the greedy insight that students always sit in the largest gap. Then present the interval heap design as the optimized solution. Interviewers typically expect the heap-based design because it reduces repeated scans and keeps operations near O(log n), which scales well when many seat and leave operations occur.

Approach 1: Approach 1: Sorted List of Occupied Seats

This approach uses a sorted list to keep track of occupied seats. When a student enters the room, we calculate potential distances at each interval and choose the seat that maximizes the minimum distance to any occupied seat. If multiple seats provide the same distance, the earliest seat in terms of index is chosen. When a student leaves, we simply remove the seat from the list.

Python

class ExamRoom:
    def __init__(self, n: int):
        self.n = n
        self.students = []

    def seat(self) -> int:
        if not self.students:
            student = 0
        else:
            dist, student = self.students[0], 0
            for i in range(1, len(self.students)):
                prev, curr = self.students[i - 1], self.students[i]
                if (curr - prev) // 2 > dist:
                    dist = (curr - prev) // 2
                    student = prev + dist
            if self.n - 1 - self.students[-1] > dist:
                student = self.n - 1
        bisect.insort(self.students, student)
        return student

    def leave(self, p: int) -> None:
        self.students.remove(p)

C++

#include <vector>
#include <algorithm>

class ExamRoom {
private:
    int n;
    std::vector<int> students;

public:
    ExamRoom(int n) : n(n) {}

    int seat() {
        if (students.empty()) {
            students.push_back(0);
            return 0;
        }
        int dist = students[0], student = 0;
        for (int i = 1; i < students.size(); ++i) {
            int prev = students[i - 1], curr = students[i];
            int d = (curr - prev) / 2;
            if (d > dist) {
                dist = d;
                student = prev + d;
            }
        }
        if (n - 1 - students.back() > dist) {
            student = n - 1;
        }
        students.insert(std::upper_bound(students.begin(), students.end(), student), student);
        return student;
    }

    void leave(int p) {
        students.erase(std::remove(students.begin(), students.end(), p), students.end());
    }
};

We maintain a sorted list of occupied seats, allowing us to compute potential seating distances dynamically. The bisect module helps insert the new student in a sorted manner. Distances are checked between each successive occupied seat, including the boundaries.

Complexity

The time complexity is O(N) for the seat method, where N is the number of currently occupied seats. The leave method has a time complexity of O(N) due to list manipulation. The space complexity is O(N) for storing the list of occupied seats.

Try this approach in the editor

Approach 2: Approach 2: Maximum Heap of Intervals

In this approach, we utilize a max-heap (priority queue) to manage seat intervals. Each interval is prioritized by its distance, allowing us to efficiently determine where to seat the next student. The order of seating follows the priority determined by the maximum possible distance in the available intervals. When a student leaves, the adjacent intervals are merged and updated in the heap.

Java

import java.util.PriorityQueue;

class ExamRoom {
    private int n;
    private PriorityQueue<int[]> pq;

    public ExamRoom(int n) {
        this.n = n;
        this.pq = new PriorityQueue<>((a, b) -> (b[1] - b[0]) / 2 == (a[1] - a[0]) / 2 ? a[0] - b[0] : (b[1] - b[0]) / 2 - (a[1] - a[0]) / 2);
        pq.add(new int[]{-1, n});
    }

    public int seat() {
        int[] longest = pq.poll();
        int x = longest[0], y = longest[1];
        int seat;
        if (x == -1) {
            seat = 0;
        } else if (y == n) {
            seat = n - 1;
        } else {
            seat = (y - x) / 2 + x;
        }
        pq.add(new int[]{x, seat});
        pq.add(new int[]{seat, y});
        return seat;
    }

    public void leave(int p) {
        int x = -1, y = n;
        for (int[] interval : pq) {
            if (interval[0] == -1 && interval[1] == p) x = interval[0];
            if (interval[0] == p && interval[1] == n) y = interval[1];
            if (x == -1 && interval[1] == p) {
                x = interval[0];
                pq.remove(interval);
            } else if (y == n && interval[0] == p) {
                y = interval[1];
                pq.remove(interval);
            }
        }
        pq.add(new int[]{x, y});
    }
}

JavaScript

class ExamRoom {
    constructor(n) {
        this.n = n;
        this.students = new Set();
    }
    seat() {
        if (this.students.size === 0) {
            this.students.add(0);
            return 0;
        }
        let seat = 0, dist = [...this.students][0];
        let prev = -1;
        for (let s of this.students) {
            let currDist = prev === -1 ? s : Math.floor((s - prev) / 2);
            if (currDist > dist) {
                dist = currDist;
                seat = prev === -1 ? 0 : prev + currDist;
            }
            prev = s;
        }
        if (this.n - 1 - [...this.students][this.students.size - 1] > dist) {
            seat = this.n - 1;
        }
        this.students.add(seat);
        return seat;
    }
    leave(p) {
        this.students.delete(p);
    }
}

In this Java implementation, a priority queue manages intervals defined by two endpoints. The queue is structured such that intervals with the largest possible seating distances are dequeued first. When a new student is seated, two new intervals are created based on the seated position. The priority queue allows efficient management of these operations.

Complexity

Both seat and leave methods have a time complexity of O(logN), where N is the number of intervals in the room. This complexity arises from the operations in the priority queue. Space complexity is O(N), accounting for storing intervals in the queue.

Try this approach in the editor

Approach 3: Ordered Set + Hash Table

Considering that each time we call seat(), we need to find the seat with the maximum distance, we can use an ordered set to store seat intervals. Each element of the ordered set is a tuple (l, r), indicating that the seats between l and r (excluding l and r) can be occupied by a student. Initially, the ordered set contains only one element (-1, n), indicating that the seats between (-1, n) can be occupied by a student.

Additionally, we use two hash tables left and right to maintain the left and right neighbors of each occupied seat, making it easier to merge two seat intervals when calling leave(p).

The time complexity is O(log n), and the space complexity is O(n). Here, n is the number of seats in the exam room.

TypeScript

class ExamRoom {
    private ts: TreeSet<number[]> = new TreeSet<number[]>((a, b) => {
        const d1 = this.dist(a),
            d2 = this.dist(b);
        return d1 === d2 ? a[0] - b[0] : d2 - d1;
    });
    private left: Map<number, number> = new Map();
    private right: Map<number, number> = new Map();
    private n: number;

    constructor(n: number) {
        this.n = n;
        this.add([-1, n]);
    }

    seat(): number {
        const s = this.ts.first();
        let p = Math.floor((s[0] + s[1]) / 2);
        if (s[0] === -1) {
            p = 0;
        } else if (s[1] === this.n) {
            p = this.n - 1;
        }
        this.del(s);
        this.add([s[0], p]);
        this.add([p, s[1]]);
        return p;
    }

    leave(p: number): void {
        const l = this.left.get(p)!;
        const r = this.right.get(p)!;
        this.del([l, p]);
        this.del([p, r]);
        this.add([l, r]);
    }

    private dist(s: number[]): number {
        const [l, r] = s;
        return l === -1 || r === this.n ? r - l - 1 : Math.floor((r - l) / 2);
    }

    private add(s: number[]): void {
        this.ts.add(s);
        this.left.set(s[1], s[0]);
        this.right.set(s[0], s[1]);
    }

    private del(s: number[]): void {
        this.ts.delete(s);
        this.left.delete(s[1]);
        this.right.delete(s[0]);
    }
}

type Compare<T> = (lhs: T, rhs: T) => number;

class RBTreeNode<T = number> {
    data: T;
    count: number;
    left: RBTreeNode<T> | null;
    right: RBTreeNode<T> | null;
    parent: RBTreeNode<T> | null;
    color: number;
    constructor(data: T) {
        this.data = data;
        this.left = this.right = this.parent = null;
        this.color = 0;
        this.count = 1;
    }

    sibling(): RBTreeNode<T> | null {
        if (!this.parent) return null; // sibling null if no parent
        return this.isOnLeft() ? this.parent.right : this.parent.left;
    }

    isOnLeft(): boolean {
        return this === this.parent!.left;
    }

    hasRedChild(): boolean {
        return (
            Boolean(this.left && this.left.color === 0) ||
            Boolean(this.right && this.right.color === 0)
        );
    }
}

class RBTree<T> {
    root: RBTreeNode<T> | null;
    lt: (l: T, r: T) => boolean;
    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
        this.root = null;
        this.lt = (l: T, r: T) => compare(l, r) < 0;
    }

    rotateLeft(pt: RBTreeNode<T>): void {
        const right = pt.right!;
        pt.right = right.left;

        if (pt.right) pt.right.parent = pt;
        right.parent = pt.parent;

        if (!pt.parent) this.root = right;
        else if (pt === pt.parent.left) pt.parent.left = right;
        else pt.parent.right = right;

        right.left = pt;
        pt.parent = right;
    }

    rotateRight(pt: RBTreeNode<T>): void {
        const left = pt.left!;
        pt.left = left.right;

        if (pt.left) pt.left.parent = pt;
        left.parent = pt.parent;

        if (!pt.parent) this.root = left;
        else if (pt === pt.parent.left) pt.parent.left = left;
        else pt.parent.right = left;

        left.right = pt;
        pt.parent = left;
    }

    swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.color;
        p1.color = p2.color;
        p2.color = tmp;
    }

    swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.data;
        p1.data = p2.data;
        p2.data = tmp;
    }

    fixAfterInsert(pt: RBTreeNode<T>): void {
        let parent = null;
        let grandParent = null;

        while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
            parent = pt.parent;
            grandParent = pt.parent.parent;

            /*  Case : A
                Parent of pt is left child of Grand-parent of pt */
            if (parent === grandParent?.left) {
                const uncle = grandParent.right;

                /* Case : 1
                   The uncle of pt is also red
                   Only Recoloring required */
                if (uncle && uncle.color === 0) {
                    grandParent.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent;
                } else {
                    /* Case : 2
                       pt is right child of its parent
                       Left-rotation required */
                    if (pt === parent.right) {
                        this.rotateLeft(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is left child of its parent
                       Right-rotation required */
                    this.rotateRight(grandParent);
                    this.swapColor(parent!, grandParent);
                    pt = parent!;
                }
            } else {
                /* Case : B
               Parent of pt is right child of Grand-parent of pt */
                const uncle = grandParent!.left;

                /*  Case : 1
                    The uncle of pt is also red
                    Only Recoloring required */
                if (uncle != null && uncle.color === 0) {
                    grandParent!.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent!;
                } else {
                    /* Case : 2
                       pt is left child of its parent
                       Right-rotation required */
                    if (pt === parent.left) {
                        this.rotateRight(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is right child of its parent
                       Left-rotation required */
                    this.rotateLeft(grandParent!);
                    this.swapColor(parent!, grandParent!);
                    pt = parent!;
                }
            }
        }
        this.root!.color = 1;
    }

    delete(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        node.count--;
        if (!node.count) this.deleteNode(node);
        return true;
    }

    deleteAll(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        this.deleteNode(node);
        return true;
    }

    deleteNode(v: RBTreeNode<T>): void {
        const u = BSTreplace(v);

        // True when u and v are both black
        const uvBlack = (u === null || u.color === 1) && v.color === 1;
        const parent = v.parent!;

        if (!u) {
            // u is null therefore v is leaf
            if (v === this.root) this.root = null;
            // v is root, making root null
            else {
                if (uvBlack) {
                    // u and v both black
                    // v is leaf, fix double black at v
                    this.fixDoubleBlack(v);
                } else {
                    // u or v is red
                    if (v.sibling()) {
                        // sibling is not null, make it red"
                        v.sibling()!.color = 0;
                    }
                }
                // delete v from the tree
                if (v.isOnLeft()) parent.left = null;
                else parent.right = null;
            }
            return;
        }

        if (!v.left || !v.right) {
            // v has 1 child
            if (v === this.root) {
                // v is root, assign the value of u to v, and delete u
                v.data = u.data;
                v.left = v.right = null;
            } else {
                // Detach v from tree and move u up
                if (v.isOnLeft()) parent.left = u;
                else parent.right = u;
                u.parent = parent;
                if (uvBlack) this.fixDoubleBlack(u);
                // u and v both black, fix double black at u
                else u.color = 1; // u or v red, color u black
            }
            return;
        }

        // v has 2 children, swap data with successor and recurse
        this.swapData(u, v);
        this.deleteNode(u);

        // find node that replaces a deleted node in BST
        function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
            // when node have 2 children
            if (x.left && x.right) return successor(x.right);
            // when leaf
            if (!x.left && !x.right) return null;
            // when single child
            return x.left ?? x.right;
        }
        // find node that do not have a left child
        // in the subtree of the given node
        function successor(x: RBTreeNode<T>): RBTreeNode<T> {
            let temp = x;
            while (temp.left) temp = temp.left;
            return temp;
        }
    }

    fixDoubleBlack(x: RBTreeNode<T>): void {
        if (x === this.root) return; // Reached root

        const sibling = x.sibling();
        const parent = x.parent!;
        if (!sibling) {
            // No sibiling, double black pushed up
            this.fixDoubleBlack(parent);
        } else {
            if (sibling.color === 0) {
                // Sibling red
                parent.color = 0;
                sibling.color = 1;
                if (sibling.isOnLeft()) this.rotateRight(parent);
                // left case
                else this.rotateLeft(parent); // right case
                this.fixDoubleBlack(x);
            } else {
                // Sibling black
                if (sibling.hasRedChild()) {
                    // at least 1 red children
                    if (sibling.left && sibling.left.color === 0) {
                        if (sibling.isOnLeft()) {
                            // left left
                            sibling.left.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateRight(parent);
                        } else {
                            // right left
                            sibling.left.color = parent.color;
                            this.rotateRight(sibling);
                            this.rotateLeft(parent);
                        }
                    } else {
                        if (sibling.isOnLeft()) {
                            // left right
                            sibling.right!.color = parent.color;
                            this.rotateLeft(sibling);
                            this.rotateRight(parent);
                        } else {
                            // right right
                            sibling.right!.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateLeft(parent);
                        }
                    }
                    parent.color = 1;
                } else {
                    // 2 black children
                    sibling.color = 0;
                    if (parent.color === 1) this.fixDoubleBlack(parent);
                    else parent.color = 1;
                }
            }
        }
    }

    insert(data: T): boolean {
        // search for a position to insert
        let parent = this.root;
        while (parent) {
            if (this.lt(data, parent.data)) {
                if (!parent.left) break;
                else parent = parent.left;
            } else if (this.lt(parent.data, data)) {
                if (!parent.right) break;
                else parent = parent.right;
            } else break;
        }

        // insert node into parent
        const node = new RBTreeNode(data);
        if (!parent) this.root = node;
        else if (this.lt(node.data, parent.data)) parent.left = node;
        else if (this.lt(parent.data, node.data)) parent.right = node;
        else {
            parent.count++;
            return false;
        }
        node.parent = parent;
        this.fixAfterInsert(node);
        return true;
    }

    find(data: T): RBTreeNode<T> | null {
        let p = this.root;
        while (p) {
            if (this.lt(data, p.data)) {
                p = p.left;
            } else if (this.lt(p.data, data)) {
                p = p.right;
            } else break;
        }
        return p ?? null;
    }

    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.inOrder(root.left!)) yield v;
        yield root.data;
        for (const v of this.inOrder(root.right!)) yield v;
    }

    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.reverseInOrder(root.right!)) yield v;
        yield root.data;
        for (const v of this.reverseInOrder(root.left!)) yield v;
    }
}

class TreeSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size += successful ? 1 : 0;
        return successful;
    }

    delete(val: T): boolean {
        const deleted = this.tree.deleteAll(val);
        this._size -= deleted ? 1 : 0;
        return deleted;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) yield val;
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) yield val;
        return undefined;
    }
}

/**
 * Your ExamRoom object will be instantiated and called as such:
 * var obj = new ExamRoom(n)
 * var param_1 = obj.seat()
 * obj.leave(p)
 */

type ExamRoom struct {
	rbt   *redblacktree.Tree
	left  map[int]int
	right map[int]int
	n     int
}

func Constructor(n int) ExamRoom {
	dist := func(s []int) int {
		if s[0] == -1 || s[1] == n {
			return s[1] - s[0] - 1
		}
		return (s[1] - s[0]) >> 1
	}
	cmp := func(a, b any) int {
		x, y := a.([]int), b.([]int)
		d1, d2 := dist(x), dist(y)
		if d1 == d2 {
			return x[0] - y[0]
		}
		return d2 - d1
	}
	this := ExamRoom{redblacktree.NewWith(cmp), map[int]int{}, map[int]int{}, n}
	this.add([]int{-1, n})
	return this
}

func (this *ExamRoom) Seat() int {
	s := this.rbt.Left().Key.([]int)
	p := (s[0] + s[1]) >> 1
	if s[0] == -1 {
		p = 0
	} else if s[1] == this.n {
		p = this.n - 1
	}
	this.del(s)
	this.add([]int{s[0], p})
	this.add([]int{p, s[1]})
	return p
}

func (this *ExamRoom) Leave(p int) {
	l, _ := this.left[p]
	r, _ := this.right[p]
	this.del([]int{l, p})
	this.del([]int{p, r})
	this.add([]int{l, r})
}

func (this *ExamRoom) add(s []int) {
	this.rbt.Put(s, struct{}{})
	this.left[s[1]] = s[0]
	this.right[s[0]] = s[1]
}

func (this *ExamRoom) del(s []int) {
	this.rbt.Remove(s)
	delete(this.left, s[1])
	delete(this.right, s[0])
}

/**
 * Your ExamRoom object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Seat();
 * obj.Leave(p);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Sorted List of Occupied Seats	The time complexity is O(N) for the seat method, where N is the number of currently occupied seats. The leave method has a time complexity of O(N) due to list manipulation. The space complexity is O(N) for storing the list of occupied seats.
Approach 2: Maximum Heap of Intervals	Both `seat` and `leave` methods have a time complexity of O(logN), where N is the number of intervals in the room. This complexity arises from the operations in the priority queue. Space complexity is O(N), accounting for storing intervals in the queue.
Ordered Set + Hash Table	–

Complexity analysis

Approach	Time	Space	When to Use
Sorted List of Occupied Seats	seat(): O(n), leave(): O(n)	O(n)	Good for simple implementations or when the number of operations is small
Maximum Heap of Intervals	seat(): O(log n), leave(): O(log n)	O(n)	Best for large numbers of operations; maintains the largest seating gap efficiently

Frequently asked questions

Is Exam Room easy or hard?

Exam Room is rated Medium but leans toward design-heavy reasoning. The greedy insight about choosing the largest gap is straightforward, but implementing the interval heap structure with correct merges requires careful handling of edge cases.

Exam Room Python or Java solution?

Python implementations often use a sorted list with binary insertion for the simpler approach or heapq with custom interval logic for the optimized solution. Java implementations typically rely on PriorityQueue and TreeSet structures to maintain ordered seats and interval boundaries.

How to solve Exam Room in O(log n)?

Model the exam room as intervals of empty seats and store them in a max heap ordered by seating distance. When a student arrives, pop the largest interval, place the student at the optimal midpoint, then split the interval into two smaller ones and push them back. Heap operations keep each update at O(log n).

What is the best approach for Exam Room?

The interval-based design using a max heap (priority queue) is considered the best approach. It stores empty seat ranges and always selects the interval that maximizes distance to the nearest student. Both seat() and leave() operations run in O(log n) time, which is more efficient than scanning all occupied seats.

Is Exam Room asked at Google/Amazon/Meta?

Exam Room is a classic design-style interview problem that appears in large tech company preparation lists. Variations of seat allocation or interval scheduling have been reported in interviews at companies like Google, Amazon, and Meta. The problem tests data structure design, priority queues, and edge-case reasoning.

What data structure is used in Exam Room?

Common implementations use either a sorted set of occupied seats or a max heap storing empty intervals. The optimized design also uses hash maps to quickly merge adjacent intervals when a student leaves. Together these structures allow efficient seat selection and interval updates.

What is the time complexity of Exam Room?

Using a sorted list of occupied seats leads to O(n) time for seat() because you scan all gaps to find the maximum distance. The optimized heap-based interval solution reduces operations to O(log n) time. Space complexity in both designs is O(n) since you track occupied seats or intervals.

Exam Room solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorted List of Occupied Seats

Approach 2: Approach 2: Maximum Heap of Intervals

Approach 3: Ordered Set + Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Exam Room solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorted List of Occupied Seats

Approach 2: Approach 2: Maximum Heap of Intervals

Approach 3: Ordered Set + Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems