Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using design strategy.
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 <= 109p.104 calls will be made to seat and leave.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Design · Segment Tree
["ExamRoom","seat","seat","seat","seat","leave","seat"] [[10],[],[],[],[],[4],[]]
maximize-distance-to-closest-person)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #855: Exam Room
class ExamRoom {
private TreeSet<int[]> ts = new TreeSet<>((a, b) -> {
int d1 = dist(a), d2 = dist(b);
return d1 == d2 ? a[0] - b[0] : d2 - d1;
});
private Map<Integer, Integer> left = new HashMap<>();
private Map<Integer, Integer> right = new HashMap<>();
private int n;
public ExamRoom(int n) {
this.n = n;
add(new int[] {-1, n});
}
public int seat() {
int[] s = ts.first();
int p = (s[0] + s[1]) >> 1;
if (s[0] == -1) {
p = 0;
} else if (s[1] == n) {
p = n - 1;
}
del(s);
add(new int[] {s[0], p});
add(new int[] {p, s[1]});
return p;
}
public void leave(int p) {
int l = left.get(p), r = right.get(p);
del(new int[] {l, p});
del(new int[] {p, r});
add(new int[] {l, r});
}
private int dist(int[] s) {
int l = s[0], r = s[1];
return l == -1 || r == n ? r - l - 1 : (r - l) >> 1;
}
private void add(int[] s) {
ts.add(s);
left.put(s[1], s[0]);
right.put(s[0], s[1]);
}
private void del(int[] s) {
ts.remove(s);
left.remove(s[1]);
right.remove(s[0]);
}
}
/**
* Your ExamRoom object will be instantiated and called as such:
* ExamRoom obj = new ExamRoom(n);
* int param_1 = obj.seat();
* obj.leave(p);
*/
// Accepted solution for LeetCode #855: Exam Room
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);
*/
# Accepted solution for LeetCode #855: Exam Room
class ExamRoom:
def __init__(self, n: int):
def dist(x):
l, r = x
return r - l - 1 if l == -1 or r == n else (r - l) >> 1
self.n = n
self.ts = SortedList(key=lambda x: (-dist(x), x[0]))
self.left = {}
self.right = {}
self.add((-1, n))
def seat(self) -> int:
s = self.ts[0]
p = (s[0] + s[1]) >> 1
if s[0] == -1:
p = 0
elif s[1] == self.n:
p = self.n - 1
self.delete(s)
self.add((s[0], p))
self.add((p, s[1]))
return p
def leave(self, p: int) -> None:
l, r = self.left[p], self.right[p]
self.delete((l, p))
self.delete((p, r))
self.add((l, r))
def add(self, s):
self.ts.add(s)
self.left[s[1]] = s[0]
self.right[s[0]] = s[1]
def delete(self, s):
self.ts.remove(s)
self.left.pop(s[1])
self.right.pop(s[0])
# Your ExamRoom object will be instantiated and called as such:
# obj = ExamRoom(n)
# param_1 = obj.seat()
# obj.leave(p)
// Accepted solution for LeetCode #855: Exam Room
use std::cmp::Reverse;
use std::collections::BTreeSet;
use std::collections::HashMap;
// (distance, left, right)
type Segment = (Reverse<i32>, i32, i32);
#[derive(Debug)]
struct ExamRoom {
n: i32,
segments: BTreeSet<Segment>,
l_indexes: HashMap<i32, i32>,
r_indexes: HashMap<i32, i32>,
}
impl ExamRoom {
fn new(n: i32) -> Self {
let mut segments = BTreeSet::new();
segments.insert(Self::segment(0, n - 1, n));
let mut l_indexes = HashMap::new();
let mut r_indexes = HashMap::new();
l_indexes.insert(0, n - 1);
r_indexes.insert(n - 1, 0);
ExamRoom {
n,
segments,
l_indexes,
r_indexes,
}
}
fn seat(&mut self) -> i32 {
let mut it = self.segments.iter();
if let Some(&first) = it.next() {
let l = first.1;
let r = first.2;
let p = Self::split(&first, self.n);
self.segments.remove(&first);
self.segments.insert(Self::segment(l, p - 1, self.n));
self.segments.insert(Self::segment(p + 1, r, self.n));
self.l_indexes.insert(l, p - 1);
self.r_indexes.insert(p - 1, l);
self.l_indexes.insert(p + 1, r);
self.r_indexes.insert(r, p + 1);
p
} else {
-1
}
}
fn leave(&mut self, p: i32) {
let r1 = p - 1;
let l1 = self.r_indexes[&r1];
let l2 = p + 1;
let r2 = self.l_indexes[&l2];
self.segments.remove(&Self::segment(l1, r1, self.n));
self.segments.remove(&Self::segment(l2, r2, self.n));
self.segments.insert(Self::segment(l1, r2, self.n));
self.r_indexes.remove(&r1);
self.l_indexes.remove(&l2);
self.l_indexes.insert(l1, r2);
self.r_indexes.insert(r2, l1);
}
fn segment(l: i32, r: i32, n: i32) -> Segment {
if l == 0 {
return (Reverse(r), l, r);
}
if r == n - 1 {
return (Reverse(n - 1 - l), l, r);
}
if l <= r {
(Reverse((r - l) / 2), l, r)
} else {
(Reverse(-1), l, r)
}
}
fn split(s: &Segment, n: i32) -> i32 {
let l = s.1;
let r = s.2;
if l == 0 {
return 0;
}
if r == n - 1 {
return n - 1;
}
l + (r - l) / 2
}
}
#[test]
fn test() {
let mut exam_room = ExamRoom::new(10);
assert_eq!(exam_room.seat(), 0);
assert_eq!(exam_room.seat(), 9);
assert_eq!(exam_room.seat(), 4);
assert_eq!(exam_room.seat(), 2);
exam_room.leave(4);
assert_eq!(exam_room.seat(), 5);
let mut exam_room = ExamRoom::new(4);
assert_eq!(exam_room.seat(), 0);
assert_eq!(exam_room.seat(), 3);
assert_eq!(exam_room.seat(), 1);
assert_eq!(exam_room.seat(), 2);
exam_room.leave(1);
exam_room.leave(3);
assert_eq!(exam_room.seat(), 1);
}
// Accepted solution for LeetCode #855: Exam Room
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)
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.