31 — LLD: Meeting Room Reservation System

Frequently Asked at Uber — Reported repeatedly in recent L5A R3 (Coding-Depth) rounds.

Understanding the Problem

A meeting room reservation system lets users book a room for a time interval and prevents overlapping bookings on the same room. It looks simple on the surface, but the real exercise is picking the right data structure for interval overlap checks and handling concurrent bookings without serializing the whole service.

What is a Meeting Room Reservation System?

Think of it as a calendar per room. Each room has a schedule of [start, end) intervals. A new booking succeeds only if no existing booking overlaps. The system must also support cancellation and a "what is free right now?" query across rooms.

---

Requirements

Clarifying Questions

You: Is this a single in-memory process or distributed across hosts?

Interviewer: Single process for now — but design it so it could shard by roomId later.

Good. No cross-host coordination, but the shape should be shard-friendly — no global sorted structure across all rooms.

You: Can a booking be modified in place, or is it cancel-and-rebook?

Interviewer: Cancel-and-rebook is fine.

That simplifies the state machine — no update method needed.

You: Max concurrent rooms? Max bookings per room per day?

Interviewer: Around 10k rooms, a few hundred bookings per room per day.

Small enough that per-room data structures stay in memory. You can use a TreeMap per room without worrying about cardinality.

You: Are intervals closed or half-open? If a booking ends at 10:00 and another starts at 10:00, is that a conflict?

Interviewer: Half-open — [start, end). Adjacent non-overlapping is fine.

Critical for the overlap predicate. prev.end > new.start (strict), not >=.

You: Recurring meetings?

Interviewer: Not in the core. Mention it as an extension.

Final Requirements

1. book(roomId, start, end, userId) — returns true if booked; rejects on overlap with an existing booking on the same room.
2. cancel(roomId, start) — removes the booking starting at that time.
3. listAvailable(atEpoch) — rooms that are free at the given instant.
4. Half-open intervals [start, end).
5. Thread-safe — many users book concurrently across rooms.

Out of scope: Recurring meetings, modification in place, multi-host persistence, attendees/invitations.

Deferred tradeoff: Read-heavy listAvailable shares the same per-room locks as writes — fine for 10k rooms, revisit at 10M.

---

Core Entities and Relationships

Walking the nouns: Room, Booking, User, Schedule. A User is just an opaque id — no need for a class. A Schedule belongs to a room, so it is not freestanding data — it is per-room state. That gives us a clean lock boundary.

Entity	Responsibility
Room	Immutable value — id, capacity, building.
Booking	Immutable value — id, roomId, start, end, ownerId.
RoomSchedule	Per-room sorted interval map. Owns the lock. Checks overlap, inserts, removes.
ReservationService	Facade. Fans out operations to the right RoomSchedule.

Why does RoomSchedule deserve its own class? Because it owns a non-trivial invariant (no overlaps) and a concurrency primitive (a per-room lock). That is a natural unit of encapsulation.

Design is iterative. If you later need cross-room queries (e.g., "any 5-person room free at 2pm"), you will add a secondary index in ReservationService.

---

Class Design

Room (value object)

• id, capacity, building — all immutable. Nothing to lock.

Booking (value object)

• id, roomId, start, end, ownerId — immutable after creation.

RoomSchedule

State:

• byStart: TreeMap<Long, Booking> — bookings keyed by start epoch, sorted.
• lock: ReentrantLock — per-room.

Methods:

• tryBook(booking) -> boolean — atomic overlap check + insert.
• cancel(start) -> boolean.
• isFreeAt(time) -> boolean.

The crux of the design is tryBook. Given bookings sorted by start, a new [s, e) overlaps iff the floor entry's end > s OR the ceiling entry's start < e. Both lookups are O(log N).

ReservationService

State:

• rooms: Map<String, Room> — static reference data.
• schedules: ConcurrentHashMap<String, RoomSchedule> — per-room schedules.

Methods:

• book(roomId, start, end, userId).
• cancel(roomId, start).
• listAvailable(atEpoch).

Java

public record Room(String id, int capacity, String building) {}

public record Booking(String id, String roomId, long start, long end, String ownerId) {}

public class RoomSchedule {
    private final TreeMap<Long, Booking> byStart = new TreeMap<>();
    private final ReentrantLock lock = new ReentrantLock();

    public boolean tryBook(Booking b) { /* ... */ }
    public boolean cancel(long start) { /* ... */ }
    public boolean isFreeAt(long t) { /* ... */ }
}

public class ReservationService {
    private final Map<String, Room> rooms;
    private final Map<String, RoomSchedule> schedules = new ConcurrentHashMap<>();

    public boolean book(String roomId, long start, long end, String userId) { /* ... */ }
    public boolean cancel(String roomId, long start) { /* ... */ }
    public List<Room> listAvailable(long atEpoch) { /* ... */ }
}

C++

struct Room { std::string id; int capacity; std::string building; };
struct Booking { std::string id, roomId, ownerId; long start, end; };

class RoomSchedule {
    std::map<long, Booking> byStart;
    std::mutex mtx;
public:
    bool tryBook(const Booking& b);
    bool cancel(long start);
    bool isFreeAt(long t);
};

class ReservationService {
    std::unordered_map<std::string, Room> rooms;
    std::unordered_map<std::string, std::shared_ptr<RoomSchedule>> schedules;
    std::mutex scheduleMapMtx;
public:
    bool book(const std::string& roomId, long s, long e, const std::string& user);
    bool cancel(const std::string& roomId, long s);
    std::vector<Room> listAvailable(long t);
};

TypeScript

export interface Room { id: string; capacity: number; building: string; }
export interface Booking { id: string; roomId: string; start: number; end: number; ownerId: string; }

export class RoomSchedule {
  private byStart = new Map<number, Booking>();
  private sortedStarts: number[] = [];

  tryBook(b: Booking): boolean { /* ... */ }
  cancel(start: number): boolean { /* ... */ }
  isFreeAt(t: number): boolean { /* ... */ }
}

Design principles at play:

• Single Responsibility: RoomSchedule does intervals. ReservationService does routing. Nothing mixes.
• Facade: ReservationService is a thin dispatcher — callers never touch RoomSchedule directly.
• Strategy (optional): An OverlapPolicy interface can let you switch between strict non-overlap and "allow adjacent" if requirements shift.

---

Implementation

Core Logic: tryBook

1. Reject invalid input (start >= end).
2. Lock the room schedule.
3. Look up the floor entry — largest booking whose start ≤ new start. If its end > new.start, overlap.
4. Look up the ceiling entry — smallest booking whose start ≥ new start. If its start < new.end, overlap.
5. Insert and return true.

Bad Solution: Linear scan through all bookings checking each for overlap. O(N) per booking. At a few hundred bookings per room, fine — but you should not reach for this in a senior interview.

Good Solution: TreeMap with floorEntry and ceilingEntry. O(log N). Natural per-room lock granularity.

Great Solution: Same data structure, but swap the ReentrantLock for a ConcurrentSkipListMap if read throughput matters. Writes still need a retry loop with a version counter since the overlap check becomes inherently racy (two threads can both pass the predicate).

Implementations

Java

public boolean tryBook(Booking b) {
    if (b.start() >= b.end()) return false;
    lock.lock();
    try {
        Map.Entry<Long, Booking> prev = byStart.floorEntry(b.start());
        if (prev != null && prev.getValue().end() > b.start()) return false;
        Map.Entry<Long, Booking> next = byStart.ceilingEntry(b.start());
        if (next != null && next.getKey() < b.end()) return false;
        byStart.put(b.start(), b);
        return true;
    } finally {
        lock.unlock();
    }
}

public boolean cancel(long start) {
    lock.lock();
    try {
        return byStart.remove(start) != null;
    } finally {
        lock.unlock();
    }
}

public boolean isFreeAt(long t) {
    lock.lock();
    try {
        Map.Entry<Long, Booking> prev = byStart.floorEntry(t);
        return prev == null || prev.getValue().end() <= t;
    } finally {
        lock.unlock();
    }
}

C++

bool RoomSchedule::tryBook(const Booking& b) {
    if (b.start >= b.end) return false;
    std::lock_guard<std::mutex> g(mtx);
    auto it = byStart.lower_bound(b.start);
    if (it != byStart.begin()) {
        auto prev = std::prev(it);
        if (prev->second.end > b.start) return false;
    }
    if (it != byStart.end() && it->first < b.end) return false;
    byStart.emplace(b.start, b);
    return true;
}

bool RoomSchedule::cancel(long start) {
    std::lock_guard<std::mutex> g(mtx);
    return byStart.erase(start) > 0;
}

TypeScript

tryBook(b: Booking): boolean {
  if (b.start >= b.end) return false;
  const idx = lowerBound(this.sortedStarts, b.start);
  if (idx > 0) {
    const prevStart = this.sortedStarts[idx - 1];
    const prev = this.byStart.get(prevStart)!;
    if (prev.end > b.start) return false;
  }
  if (idx < this.sortedStarts.length) {
    const nextStart = this.sortedStarts[idx];
    if (nextStart < b.end) return false;
  }
  this.sortedStarts.splice(idx, 0, b.start);
  this.byStart.set(b.start, b);
  return true;
}

function lowerBound(arr: number[], target: number): number {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (arr[mid] < target) lo = mid + 1; else hi = mid;
  }
  return lo;
}

Thread Safety

Each RoomSchedule owns its own lock. Because bookings for different rooms never conflict, you get per-room striping for free. The schedules map is a ConcurrentHashMap — safe for concurrent registration of new rooms.

Critical section = only the overlap check + insertion. No I/O, no callbacks, no network inside the lock.

Verification

Room R1, operations:

Op	byStart (start → end)	Result
book(9, 10)	{9 → 10}	true
book(10, 11)	{9 → 10, 10 → 11}	true (adjacent, non-overlapping)
book(9:30, 10:30)	unchanged	false (floor 9→10 ends at 10, > 9:30)
cancel(9)	{10 → 11}	true
book(9, 10:30)	unchanged	false (ceiling 10→11, start 10 < end 10:30)

Trace through the second-to-last: floor(9) = null (empty since we cancelled). Ceiling(9) = {10 → 11}. 10 < 10:30 → overlap → reject.

---

Complete Code Implementation

Java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;

public record Room(String id, int capacity, String building) {}
public record Booking(String id, String roomId, long start, long end, String ownerId) {}

public class RoomSchedule {
    private final TreeMap<Long, Booking> byStart = new TreeMap<>();
    private final ReentrantLock lock = new ReentrantLock();

    public boolean tryBook(Booking b) {
        if (b.start() >= b.end()) return false;
        lock.lock();
        try {
            Map.Entry<Long, Booking> prev = byStart.floorEntry(b.start());
            if (prev != null && prev.getValue().end() > b.start()) return false;
            Map.Entry<Long, Booking> next = byStart.ceilingEntry(b.start());
            if (next != null && next.getKey() < b.end()) return false;
            byStart.put(b.start(), b);
            return true;
        } finally { lock.unlock(); }
    }

    public boolean cancel(long start) {
        lock.lock();
        try { return byStart.remove(start) != null; }
        finally { lock.unlock(); }
    }

    public boolean isFreeAt(long t) {
        lock.lock();
        try {
            Map.Entry<Long, Booking> prev = byStart.floorEntry(t);
            return prev == null || prev.getValue().end() <= t;
        } finally { lock.unlock(); }
    }
}

public class ReservationService {
    private final Map<String, Room> rooms;
    private final Map<String, RoomSchedule> schedules = new ConcurrentHashMap<>();

    public ReservationService(Map<String, Room> rooms) { this.rooms = rooms; }

    public boolean book(String roomId, long start, long end, String userId) {
        if (!rooms.containsKey(roomId)) return false;
        RoomSchedule s = schedules.computeIfAbsent(roomId, k -> new RoomSchedule());
        Booking b = new Booking(UUID.randomUUID().toString(), roomId, start, end, userId);
        return s.tryBook(b);
    }

    public boolean cancel(String roomId, long start) {
        RoomSchedule s = schedules.get(roomId);
        return s != null && s.cancel(start);
    }

    public List<Room> listAvailable(long atEpoch) {
        List<Room> out = new ArrayList<>();
        for (Room r : rooms.values()) {
            RoomSchedule s = schedules.get(r.id());
            if (s == null || s.isFreeAt(atEpoch)) out.add(r);
        }
        return out;
    }
}

C++

#include <map>
#include <unordered_map>
#include <mutex>
#include <vector>
#include <memory>

struct Room { std::string id; int capacity; std::string building; };
struct Booking { std::string id, roomId, ownerId; long start, end; };

class RoomSchedule {
    std::map<long, Booking> byStart;
    std::mutex mtx;
public:
    bool tryBook(const Booking& b) {
        if (b.start >= b.end) return false;
        std::lock_guard<std::mutex> g(mtx);
        auto it = byStart.lower_bound(b.start);
        if (it != byStart.begin()) {
            auto prev = std::prev(it);
            if (prev->second.end > b.start) return false;
        }
        if (it != byStart.end() && it->first < b.end) return false;
        byStart.emplace(b.start, b);
        return true;
    }
    bool cancel(long start) {
        std::lock_guard<std::mutex> g(mtx);
        return byStart.erase(start) > 0;
    }
    bool isFreeAt(long t) {
        std::lock_guard<std::mutex> g(mtx);
        auto it = byStart.upper_bound(t);
        if (it == byStart.begin()) return true;
        auto prev = std::prev(it);
        return prev->second.end <= t;
    }
};

TypeScript

export interface Room { id: string; capacity: number; building: string; }
export interface Booking { id: string; roomId: string; start: number; end: number; ownerId: string; }

function lowerBound(arr: number[], target: number): number {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (arr[mid] < target) lo = mid + 1; else hi = mid;
  }
  return lo;
}

export class RoomSchedule {
  private byStart = new Map<number, Booking>();
  private sortedStarts: number[] = [];

  tryBook(b: Booking): boolean {
    if (b.start >= b.end) return false;
    const idx = lowerBound(this.sortedStarts, b.start);
    if (idx > 0) {
      const prev = this.byStart.get(this.sortedStarts[idx - 1])!;
      if (prev.end > b.start) return false;
    }
    if (idx < this.sortedStarts.length) {
      if (this.sortedStarts[idx] < b.end) return false;
    }
    this.sortedStarts.splice(idx, 0, b.start);
    this.byStart.set(b.start, b);
    return true;
  }

  cancel(start: number): boolean {
    const idx = lowerBound(this.sortedStarts, start);
    if (idx >= this.sortedStarts.length || this.sortedStarts[idx] !== start) return false;
    this.sortedStarts.splice(idx, 1);
    this.byStart.delete(start);
    return true;
  }

  isFreeAt(t: number): boolean {
    const idx = lowerBound(this.sortedStarts, t + 1);
    if (idx === 0) return true;
    const prev = this.byStart.get(this.sortedStarts[idx - 1])!;
    return prev.end <= t;
  }
}

export class ReservationService {
  private schedules = new Map<string, RoomSchedule>();
  constructor(private rooms: Map<string, Room>) {}

  book(roomId: string, start: number, end: number, userId: string): boolean {
    if (!this.rooms.has(roomId)) return false;
    if (!this.schedules.has(roomId)) this.schedules.set(roomId, new RoomSchedule());
    const b: Booking = { id: crypto.randomUUID(), roomId, start, end, ownerId: userId };
    return this.schedules.get(roomId)!.tryBook(b);
  }

  listAvailable(t: number): Room[] {
    const out: Room[] = [];
    for (const r of this.rooms.values()) {
      const s = this.schedules.get(r.id);
      if (!s || s.isFreeAt(t)) out.push(r);
    }
    return out;
  }
}

---

Extensibility

1. "How would you handle recurring bookings?"

Store a RecurrenceRule (RRULE-style, like iCalendar). On book, materialize occurrences within a horizon (say 90 days) and insert each as a separate booking tied to the same seriesId. On cancel, offer two modes: cancel the entire series or a single occurrence.

public record RecurrenceRule(Frequency freq, int interval, DayOfWeek[] byDay, long until) {}

Tradeoff: Materialization is simple but bloats storage. An alternative is lazy evaluation — store the rule and compute occurrences on the fly during overlap checks. The rule-based approach is cleaner until your overlap predicate gets too expensive.

2. "Shard by roomId across hosts?"

Consistent-hash roomId onto a shard. Because no cross-room booking exists, there are no distributed transactions. The ReservationService becomes a smart client that picks the right shard.

client → hash(roomId) → shard k → RoomSchedule

Tradeoff: listAvailable becomes a scatter-gather across all shards. Add a Bloom filter or a rough "any bookings at time t" digest per shard to short-circuit.

3. "Waitlist when the room is taken?"

Each Room owns a PriorityQueue<WaitlistEntry>. On tryBook failure, optionally enqueue. On cancel, promote the head of the queue and notify the user via an Observer.

public class Room {
    private final PriorityQueue<WaitlistEntry> waitlist = new PriorityQueue<>();
    // ...
}

Tradeoff: Adds a side-effect path (notifications) to cancel. Keep the notifications async — do not send emails inside the lock.

---

What is Expected at Each Level

Level	Expectations
Junior (L4)	Linear scan for overlaps per booking. Single global lock. Gets happy path right.
Mid (L5)	TreeMap with floorEntry/ceilingEntry, per-room lock, correct half-open interval predicate. Identifies RoomSchedule as a separate class.
Senior (L5A)	All of the above plus explicit discussion of lock granularity, the shard-friendly design, the Strategy seam for OverlapPolicy, and a clean path to the recurring-bookings extension.
Staff (L6)	Sharded multi-region design, conflict resolution via optimistic concurrency with a version column, calendar integration (ICS feed), SLOs on book latency.