Design a Meeting Room Booking System
Every office has a version of this system, and almost every one has had the same bugs. Two teams turn up for the same room because two bookings were checked at the same moment. The Monday standup jumps an hour in March because someone stored "14:00 UTC" instead of "09:00 New York". And a London colleague's invite says 9 a.m. when the meeting is at 2 p.m. their time.
The interview version tests three things. Can you check an interval for overlaps efficiently, without scanning every booking? Can you make "check, then insert" atomic so two people can't win the same slot? And do you handle time zones and daylight saving properly, which is where most real calendar bugs come from? This page follows the LLD interview framework. The concurrency is a close relative of seat booking in booking and inventory concurrency, and notifications use Observer.
1. Requirements
Clarifying questions and the answers we'll assume:
| Question | Assumption |
|---|---|
| One office or several? | Several, in different time zones. People also travel and join from other zones. |
| What does a room have? | An ID, a capacity and equipment (TV, video conferencing, whiteboard). |
| Are back-to-back meetings allowed? | Yes. 9–10 and 10–11 don't conflict. |
| Recurring meetings? | Weekly, for N occurrences. Booking a series is all-or-nothing. |
| What if one occurrence of a series clashes? | Reject the whole series and report which dates clash. (Skipping clashes is a reasonable alternative, but ask.) |
| Cancellation? | The organizer cancels one occurrence, or "this and following". |
| Notifications? | Everyone involved is told, with times shown in their own time zone. |
| Search? | "Free rooms for N people with this equipment at this time", smallest suitable room first. |
Functional requirements
- Register rooms with capacity and equipment.
- Book a room for an interval given in the organizer's local time, optionally weekly.
- Reject bookings that overlap an existing one, exceed capacity, or start in the past.
- Cancel a single booking, or a booking and all later ones in its series.
- Find free rooms for an interval, a head count and required equipment.
- Notify the organizer and attendees when bookings are made or cancelled.
Non-functional requirements
- No double booking, even when two requests for the same slot arrive together.
- Fast conflict checks. O(log n) per room, not a scan of the room's history.
- Correct across daylight saving. A weekly 09:00 meeting stays at 09:00 local time all year.
- Rooms are independent. A busy room must not slow down bookings of other rooms.
2. Core entities
| Entity | Responsibility |
|---|---|
Interval | A half-open [start, end) pair of UTC instants. It's the unit of conflict checking. |
Room | ID, capacity, equipment. Immutable. |
Person | ID and home time zone, which is used for display only. |
Booking | Room, organizer, title, interval, attendees, optional series ID, status. |
RoomCalendar | One room's confirmed bookings, sorted by start, never overlapping. Owns conflict detection. |
BookingService | Validation, recurrence expansion, booking, cancelling, search. Owns one calendar per room. |
BookingListener | Observer interface for "booked" and "cancelled". |
Notifier | A listener that formats each message in the recipient's time zone. |
Time zones done right
This is the part interviewers probe hardest, so settle it before drawing classes.
- Store instants. Every stored time is a point on the UTC timeline (
Instant, awaredatetime, epoch milliseconds). Comparing two bookings is then plain number comparison, whatever zones they were made in. - Accept wall-clock time plus a zone at the edge. The UI sends "2026-03-02 09:00, America/New_York". Convert to an instant immediately, using the zone database, not a fixed offset. New York is UTC−5 in winter and UTC−4 in summer. An offset like "-05:00" is a fact about one instant, not about a place.
- Repeat in local time, then convert. A weekly meeting adds 7 days to the local date-time and converts each occurrence separately. Adding 7×24 hours to the instant would move the meeting to 10:00 after the clocks change.
- Display in the viewer's zone. The same booking reads 09:00 to the organizer in New York and 14:00 (or 13:00, depending on the week) to an attendee in London.
- Decide the DST edge cases. On the spring-forward night, 01:30 in London doesn't exist. On the fall-back night it exists twice. We follow
java.time's rules: a time in the gap moves forward by the gap length, and an ambiguous time takes the earlier instant. Python'szoneinfowithfold=0gives the same answers, and the TypeScript helper is written to match. The tests check all three agree.
The US and the UK change their clocks on different dates (8 March and 29 March in 2026), which makes for a nice test. For three weeks the New York to London gap is four hours instead of five.
3. Class diagram
classDiagram
class Interval {
+Instant start
+Instant end
+of(LocalDateTime, LocalDateTime, ZoneId) Interval
}
class Room {
+String id
+int capacity
+Set equipment
}
class Person {
+String id
+ZoneId zone
}
class Booking {
+String id
+String roomId
+String title
+String seriesId
+Status status
}
class Status {
<<enumeration>>
CONFIRMED
CANCELLED
}
class RoomCalendar {
-TreeMap byStart
+clash(Interval) Optional
+add(Booking)
+remove(Booking)
}
class BookingListener {
<<interface>>
+onBooked(List)
+onCancelled(List)
}
class Notifier
class BookingService {
+book(String, Person, String, LocalDateTime, LocalDateTime, ZoneId, List, int) List
+cancel(String, Person, boolean)
+freeRooms(LocalDateTime, LocalDateTime, ZoneId, int, Set) List
}
Booking --> Interval
Booking --> Person : organizer
Booking --> "many" Person : attendees
Booking --> Status
BookingService "1" *-- "many" RoomCalendar : one per room
BookingService --> Room
RoomCalendar o-- Booking
BookingService --> BookingListener : notifies
BookingListener <|.. Notifier
4. Key flows
Conflict detection with floor and ceiling
A room's bookings never overlap, so sorted by start they're also sorted by end. For a new interval [s, e), only two existing bookings can clash.
- The floor: the latest booking starting at or before
s. It clashes if it ends afters. - The ceiling: the earliest booking starting at or after
s. It clashes if it starts beforee.
Anything earlier than the floor ends before the floor starts, so before s. Anything later than the ceiling starts after the ceiling starts, so it can only clash if the ceiling does. Two O(log n) lookups replace a scan. Java has TreeMap.floorEntry and ceilingEntry. Python uses bisect on a sorted list, and TypeScript a hand-written binary search.
sequenceDiagram
participant S as BookingService
participant C as RoomCalendar
participant T as TreeMap
S->>C: clash([09:30, 10:30))
C->>T: floorEntry(09:30)
T-->>C: booking 09:00 to 10:00
C->>C: ends 10:00, after 09:30, so it clashes
C-->>S: clash found
Booking a weekly series
sequenceDiagram
participant O as Organizer
participant S as BookingService
participant C as RoomCalendar
participant N as Notifier
O->>S: book(A, 09:00 to 10:00 New York, weekly 3)
S->>S: check capacity and not in the past
S->>S: expand in local time, convert each to UTC
S->>C: lock room A
loop each occurrence
S->>C: clash(slot)
end
alt any clash
S->>C: unlock
S-->>O: BookingConflict with the clashing bookings
else all free
S->>C: add every occurrence
S->>C: unlock
S->>N: onBooked(series)
N->>N: format the first start in each person's zone
S-->>O: bookings
end
Cancelling "this and following"
sequenceDiagram
participant O as Organizer
participant S as BookingService
participant C as RoomCalendar
participant N as Notifier
O->>S: cancel(occurrence 2, whole series)
S->>S: check caller is the organizer
S->>C: lock room
S->>C: remove occurrences 2 onwards
S->>C: unlock
S->>N: onCancelled(removed occurrences)
Booking lifecycle
stateDiagram-v2
[*] --> CONFIRMED : book, no clash
CONFIRMED --> CANCELLED : organizer cancels
CONFIRMED --> CANCELLED : no-show released
CONFIRMED --> [*] : meeting ends
CANCELLED --> [*]
There's no PENDING state because booking is synchronous: it either succeeds against the calendar or fails. An approval workflow (for example "the boardroom needs an admin's OK") would add PENDING before CONFIRMED, with the slot held while it waits.
5. Patterns and why
| Pattern | Where | Why it fits | Rejected alternative |
|---|---|---|---|
| Observer | BookingListener, Notifier | Booking shouldn't know about email, chat or calendar sync. Each is a listener, and new ones need no change to booking. | Calling the email client inside book(). A slow mail server then slows or fails bookings. |
| Per-room aggregate | RoomCalendar | The invariant "no overlaps" is about one room, so one object owns it and its lock. | One big list of all bookings, which needs a global lock and a scan. |
| Value objects | Interval, Room, Person | Immutable, validated on construction. An Interval can't exist with start >= end. | Passing raw (start, end) pairs, where every method must re-validate. |
| Facade | BookingService | One place for validation, recurrence and notification order. | Clients calling calendars directly and forgetting to notify or validate. |
Why the calendar is the lock owner. The thing that must be atomic is "no clash found, so insert". That's a property of one room's bookings. Putting the lock on the calendar gives the finest grain that's still correct: two rooms never contend, and a series is atomic because all its occurrences are in the same room.
Why not an interval tree? An interval tree answers "which intervals overlap X?" for intervals that can overlap each other. A room's confirmed bookings never overlap, which is the special case where a sorted map is enough. An interval tree becomes useful for questions like "every meeting any of these 50 people is in this week", where the intervals come from many calendars.
Why recurrence is expanded eagerly. We store one booking per occurrence. That makes conflict checks trivial and lets each occurrence be cancelled or moved on its own. The alternative is to store a rule (an iCalendar RRULE) and expand it on demand. That's compact and handles "forever" series, but every conflict check must expand rules from both sides. Expand eagerly up to a horizon (say a year), and extend the series with a background job.
6. The code
The demo books a weekly standup at 09:00 New York time for three Mondays, starting 2 March 2026. The US moves its clocks on 8 March, so the stored UTC hour goes 14, 13, 13 while the local time stays 09:00. Ben in London is told "14:00". Then a back-to-back booking succeeds, an overlapping one fails, and a series that clashes on one date is rejected entirely. Search shows which rooms with a TV are free. Finally, cancelling one occurrence frees the room, and Ben is told in London time.
import java.time.*;
import java.time.format.DateTimeFormatter;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.Supplier;
/** Half-open [start, end) in UTC, so 9-10 and 10-11 do not overlap. */
record Interval(Instant start, Instant end) {
Interval {
if (!start.isBefore(end)) throw new IllegalArgumentException("start must be before end");
}
/** Wall-clock times in a zone. DST gaps move forward, overlaps take the earlier instant. */
static Interval of(LocalDateTime start, LocalDateTime end, ZoneId zone) {
return new Interval(start.atZone(zone).toInstant(), end.atZone(zone).toInstant());
}
}
record Room(String id, int capacity, Set<String> equipment) {}
record Person(String id, ZoneId zone) {}
enum Status { CONFIRMED, CANCELLED }
final class Booking {
final String id, roomId, title, seriesId;
final Person organizer;
final Interval interval;
final List<Person> attendees;
volatile Status status = Status.CONFIRMED;
Booking(String id, String roomId, Person organizer, String title, Interval interval, List<Person> attendees, String seriesId) {
this.id = id; this.roomId = roomId; this.organizer = organizer; this.title = title;
this.interval = interval; this.attendees = List.copyOf(attendees); this.seriesId = seriesId;
}
}
final class BookingConflictException extends RuntimeException {
final List<Booking> clashes;
BookingConflictException(List<Booking> clashes) { super(clashes.size() + " clash(es)"); this.clashes = clashes; }
}
/** One room's confirmed bookings keyed by start. They never overlap, so only the two neighbours can clash. */
final class RoomCalendar {
private final TreeMap<Instant, Booking> byStart = new TreeMap<>();
synchronized Optional<Booking> clash(Interval iv) {
var floor = byStart.floorEntry(iv.start()); // starts at or before us
if (floor != null && floor.getValue().interval.end().isAfter(iv.start())) return Optional.of(floor.getValue());
var ceiling = byStart.ceilingEntry(iv.start()); // starts at or after us
if (ceiling != null && ceiling.getKey().isBefore(iv.end())) return Optional.of(ceiling.getValue());
return Optional.empty();
}
synchronized void add(Booking b) { byStart.put(b.interval.start(), b); }
synchronized void remove(Booking b) { byStart.remove(b.interval.start(), b); }
}
interface BookingListener {
void onBooked(List<Booking> bookings);
void onCancelled(List<Booking> bookings);
}
/** Tells every participant, in their own time zone. */
final class Notifier implements BookingListener {
final List<String> sent = new CopyOnWriteArrayList<>();
private static final DateTimeFormatter FMT = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm");
private void tell(String verb, List<Booking> bs) {
Booking first = bs.get(0);
Set<Person> people = new LinkedHashSet<>(List.of(first.organizer));
people.addAll(first.attendees);
for (Person p : people) {
String local = FMT.format(first.interval.start().atZone(p.zone()));
sent.add(p.id() + ": " + verb + ": " + first.title + " " + local + " " + p.zone() + (bs.size() > 1 ? " (x" + bs.size() + ")" : ""));
}
}
public void onBooked(List<Booking> bs) { tell("Booked", bs); }
public void onCancelled(List<Booking> bs) { tell("Cancelled", bs); }
}
final class BookingService {
final Map<String, Room> rooms = new LinkedHashMap<>();
final Map<String, Booking> bookings = new ConcurrentHashMap<>();
final List<BookingListener> listeners = new CopyOnWriteArrayList<>();
private final Map<String, RoomCalendar> calendars = new HashMap<>();
private final Supplier<Instant> clock;
private final AtomicLong ids = new AtomicLong();
BookingService(List<Room> rooms, Supplier<Instant> clock) {
rooms.forEach(r -> { this.rooms.put(r.id(), r); calendars.put(r.id(), new RoomCalendar()); });
this.clock = clock;
}
/** Book start-end (wall-clock in zone), optionally repeating weekly. All occurrences or none. */
List<Booking> book(String roomId, Person organizer, String title, LocalDateTime start, LocalDateTime end,
ZoneId zone, List<Person> attendees, int weekly) {
Room room = rooms.get(roomId);
if (attendees.size() + 1 > room.capacity()) throw new IllegalArgumentException(roomId + " seats " + room.capacity());
List<Interval> slots = new ArrayList<>();
for (int k = 0; k < weekly; k++) slots.add(Interval.of(start.plusWeeks(k), end.plusWeeks(k), zone)); // repeat in local time
if (!slots.get(0).start().isAfter(clock.get())) throw new IllegalArgumentException("cannot book in the past");
String series = weekly > 1 ? "s" + ids.incrementAndGet() : null;
RoomCalendar cal = calendars.get(roomId);
List<Booking> made = new ArrayList<>();
synchronized (cal) { // check every slot and insert them as one step
List<Booking> clashes = slots.stream().map(cal::clash).flatMap(Optional::stream).toList();
if (!clashes.isEmpty()) throw new BookingConflictException(clashes);
for (Interval iv : slots) {
Booking b = new Booking("b" + ids.incrementAndGet(), roomId, organizer, title, iv, attendees, series);
cal.add(b);
bookings.put(b.id, b);
made.add(b);
}
}
listeners.forEach(l -> l.onBooked(made)); // outside the lock
return made;
}
void cancel(String bookingId, Person by, boolean wholeSeries) {
Booking target = bookings.get(bookingId);
if (!target.organizer.equals(by)) throw new SecurityException("only the organizer can cancel");
RoomCalendar cal = calendars.get(target.roomId);
List<Booking> group = new ArrayList<>();
synchronized (cal) {
for (Booking b : bookings.values()) {
boolean sameSeries = wholeSeries && target.seriesId != null && target.seriesId.equals(b.seriesId)
&& !b.interval.start().isBefore(target.interval.start());
if ((b == target || sameSeries) && b.status == Status.CONFIRMED) group.add(b);
}
group.sort(Comparator.comparing(b -> b.interval.start()));
for (Booking b : group) { cal.remove(b); b.status = Status.CANCELLED; }
}
if (!group.isEmpty()) listeners.forEach(l -> l.onCancelled(group));
}
/** Rooms that fit, smallest first. The answer can be stale a moment later: book() re-checks. */
List<Room> freeRooms(LocalDateTime start, LocalDateTime end, ZoneId zone, int people, Set<String> needs) {
Interval iv = Interval.of(start, end, zone);
return rooms.values().stream()
.filter(r -> r.capacity() >= people && r.equipment().containsAll(needs))
.sorted(Comparator.comparingInt(Room::capacity).thenComparing(Room::id))
.filter(r -> calendars.get(r.id()).clash(iv).isEmpty())
.toList();
}
RoomCalendar calendar(String roomId) { return calendars.get(roomId); }
}
public class Main {
static final ZoneId NY = ZoneId.of("America/New_York");
static final Person ANA = new Person("ana", NY), BEN = new Person("ben", ZoneId.of("Europe/London"));
static BookingService demoService(Notifier notifier) {
BookingService svc = new BookingService(List.of(
new Room("A", 4, Set.of("tv")), new Room("B", 8, Set.of("tv", "video")),
new Room("C", 20, Set.of("video", "whiteboard"))), () -> Instant.parse("2026-03-01T00:00:00Z"));
svc.listeners.add(notifier);
return svc;
}
static List<String> ids(List<Room> rooms) { return rooms.stream().map(Room::id).toList(); }
public static void main(String[] args) {
Notifier notifier = new Notifier();
BookingService svc = demoService(notifier);
LocalDateTime mon = LocalDateTime.of(2026, 3, 2, 9, 0); // a Monday. US clocks change on 8 March.
List<Booking> standup = svc.book("A", ANA, "Standup", mon, mon.plusHours(1), NY, List.of(BEN), 3);
assert standup.stream().map(b -> b.interval.start().atZone(ZoneOffset.UTC).getHour()).toList().equals(List.of(14, 13, 13));
assert notifier.sent.contains("ben: Booked: Standup 2026-03-02 14:00 Europe/London (x3)");
svc.book("A", ANA, "Next", mon.plusHours(1), mon.plusHours(2), NY, List.of(), 1); // back-to-back is fine
try {
svc.book("A", ANA, "Overlap", mon.plusWeeks(1).plusMinutes(30), mon.plusWeeks(1).plusMinutes(90), NY, List.of(), 1);
throw new AssertionError("expected a conflict");
} catch (BookingConflictException e) { assert e.clashes.get(0) == standup.get(1); }
try { // clashes on 2 March only, so nothing is booked
svc.book("A", ANA, "Weekly", mon.plusMinutes(90), mon.plusMinutes(150), NY, List.of(), 3);
throw new AssertionError("expected a conflict");
} catch (BookingConflictException expected) { }
LocalDateTime mar16 = mon.plusWeeks(2).plusMinutes(90);
assert ids(svc.freeRooms(mar16, mar16.plusMinutes(30), NY, 2, Set.of())).equals(List.of("A", "B", "C"));
LocalDateTime mar9 = mon.plusWeeks(1);
assert ids(svc.freeRooms(mar9, mar9.plusHours(1), NY, 3, Set.of("tv"))).equals(List.of("B"));
svc.cancel(standup.get(1).id, ANA, false);
assert ids(svc.freeRooms(mar9, mar9.plusHours(1), NY, 3, Set.of("tv"))).equals(List.of("A", "B"));
assert notifier.sent.contains("ben: Cancelled: Standup 2026-03-09 13:00 Europe/London");
System.out.println("Main.java: all assertions passed");
}
}
from __future__ import annotations
import itertools
import threading
from bisect import bisect_left
from dataclasses import dataclass, field
from datetime import datetime, timedelta, timezone
from enum import Enum
from typing import Callable, Protocol
from zoneinfo import ZoneInfo # on Windows: pip install tzdata
UTC = timezone.utc
def to_utc(local: datetime, zone: str) -> datetime:
"""Wall-clock time in a zone -> UTC instant. In a DST gap the time moves forward;
in an overlap the earlier instant wins (fold=0), the same as java.time."""
assert local.tzinfo is None, "pass naive wall-clock time plus a zone"
return local.replace(tzinfo=ZoneInfo(zone)).astimezone(UTC)
@dataclass(frozen=True)
class Interval:
"""Half-open [start, end) in UTC, so 9-10 and 10-11 do not overlap."""
start: datetime
end: datetime
def __post_init__(self) -> None:
if self.start.tzinfo is None or self.start >= self.end:
raise ValueError("need aware datetimes with start < end")
def overlaps(self, other: Interval) -> bool:
return self.start < other.end and other.start < self.end
@dataclass(frozen=True)
class Room:
id: str
capacity: int
equipment: frozenset[str]
@dataclass(frozen=True)
class Person:
id: str
zone: str
class Status(Enum):
CONFIRMED = "confirmed"
CANCELLED = "cancelled"
@dataclass
class Booking:
id: str
room_id: str
organizer: Person
title: str
interval: Interval
attendees: tuple[Person, ...]
series_id: str | None = None
status: Status = Status.CONFIRMED
class BookingConflict(Exception):
def __init__(self, clashes: list[Booking]) -> None:
super().__init__(f"{len(clashes)} clash(es), first with {clashes[0].title!r}")
self.clashes = clashes
class RoomCalendar:
"""One room's confirmed bookings, sorted by start and never overlapping."""
def __init__(self) -> None:
self.lock = threading.Lock()
self._starts: list[datetime] = []
self._items: list[Booking] = []
def clash(self, iv: Interval) -> Booking | None:
i = bisect_left(self._starts, iv.start)
if i < len(self._items) and self._items[i].interval.start < iv.end: # ceiling: starts at or after us
return self._items[i]
if i > 0 and self._items[i - 1].interval.end > iv.start: # floor: starts before us
return self._items[i - 1]
return None
def add(self, b: Booking) -> None:
# Simplification: list insert is O(n), use a balanced tree (sortedcontainers) for very busy rooms
i = bisect_left(self._starts, b.interval.start)
self._starts.insert(i, b.interval.start)
self._items.insert(i, b)
def remove(self, b: Booking) -> None:
i = bisect_left(self._starts, b.interval.start)
if i < len(self._items) and self._items[i] is b:
del self._starts[i], self._items[i]
class BookingListener(Protocol):
def on_booked(self, bookings: list[Booking]) -> None: ...
def on_cancelled(self, bookings: list[Booking]) -> None: ...
@dataclass
class Notifier:
"""Tells every participant, in their own time zone."""
sent: list[tuple[str, str]] = field(default_factory=list)
def _tell(self, verb: str, bookings: list[Booking]) -> None:
first = bookings[0]
for p in {first.organizer, *first.attendees}:
local = first.interval.start.astimezone(ZoneInfo(p.zone))
times = f" (x{len(bookings)})" if len(bookings) > 1 else ""
self.sent.append((p.id, f"{verb}: {first.title} {local:%Y-%m-%d %H:%M} {p.zone}{times}"))
def on_booked(self, bookings: list[Booking]) -> None:
self._tell("Booked", bookings)
def on_cancelled(self, bookings: list[Booking]) -> None:
self._tell("Cancelled", bookings)
class BookingService:
def __init__(self, rooms: list[Room], clock: Callable[[], datetime] = lambda: datetime.now(UTC)) -> None:
self.rooms = {r.id: r for r in rooms}
self.clock = clock
self.bookings: dict[str, Booking] = {}
self.listeners: list[BookingListener] = []
self._calendars = {r.id: RoomCalendar() for r in rooms}
self._ids = itertools.count(1)
self._ids_lock = threading.Lock()
def book(self, room_id: str, organizer: Person, title: str, start: datetime, end: datetime, zone: str,
attendees: tuple[Person, ...] = (), weekly: int = 1) -> list[Booking]:
"""Book start-end (wall-clock in `zone`), optionally repeating weekly. All occurrences or none."""
room = self.rooms[room_id]
if len(attendees) + 1 > room.capacity:
raise ValueError(f"{room_id} seats {room.capacity}")
# Repeat in wall-clock time, then convert. 09:00 stays 09:00 local across DST.
slots = [Interval(to_utc(start + timedelta(weeks=k), zone), to_utc(end + timedelta(weeks=k), zone))
for k in range(weekly)]
if slots[0].start <= self.clock():
raise ValueError("cannot book in the past")
series = self._next_id("s") if weekly > 1 else None
cal = self._calendars[room_id]
with cal.lock: # check every slot and insert them as one step
clashes = [c for c in map(cal.clash, slots) if c]
if clashes:
raise BookingConflict(clashes)
made = [Booking(self._next_id("b"), room_id, organizer, title, iv, attendees, series) for iv in slots]
for b in made:
cal.add(b)
self.bookings[b.id] = b
for listener in self.listeners: # outside the lock
listener.on_booked(made)
return made
def cancel(self, booking_id: str, by: Person, whole_series: bool = False) -> None:
target = self.bookings[booking_id]
if by != target.organizer:
raise PermissionError("only the organizer can cancel")
cal = self._calendars[target.room_id]
with cal.lock:
group = [b for b in self.bookings.values()
if b is target or (whole_series and target.series_id and b.series_id == target.series_id
and b.interval.start >= target.interval.start)]
group = [b for b in group if b.status is Status.CONFIRMED]
for b in group:
cal.remove(b)
b.status = Status.CANCELLED
if group:
for listener in self.listeners:
listener.on_cancelled(group)
def free_rooms(self, start: datetime, end: datetime, zone: str, people: int,
needs: frozenset[str] = frozenset()) -> list[Room]:
"""Rooms that fit, smallest first. The answer can be stale a moment later: book() re-checks."""
iv = Interval(to_utc(start, zone), to_utc(end, zone))
fits = sorted((r for r in self.rooms.values() if r.capacity >= people and needs <= r.equipment),
key=lambda r: (r.capacity, r.id))
free = []
for r in fits:
cal = self._calendars[r.id]
with cal.lock:
if cal.clash(iv) is None:
free.append(r)
return free
def calendar(self, room_id: str) -> RoomCalendar:
return self._calendars[room_id]
def _next_id(self, prefix: str) -> str:
with self._ids_lock:
return f"{prefix}{next(self._ids)}"
def demo_service() -> tuple[BookingService, Notifier, Person, Person]:
rooms = [Room("A", 4, frozenset({"tv"})), Room("B", 8, frozenset({"tv", "video"})),
Room("C", 20, frozenset({"video", "whiteboard"}))]
svc = BookingService(rooms, clock=lambda: datetime(2026, 3, 1, tzinfo=UTC))
notifier = Notifier()
svc.listeners.append(notifier)
return svc, notifier, Person("ana", "America/New_York"), Person("ben", "Europe/London")
if __name__ == "__main__":
svc, notifier, ana, ben = demo_service()
NY = "America/New_York"
day = datetime(2026, 3, 2) # a Monday. US clocks change on 8 March.
standup = svc.book("A", ana, "Standup", day.replace(hour=9), day.replace(hour=10), NY, (ben,), weekly=3)
assert [b.interval.start.hour for b in standup] == [14, 13, 13] # UTC hour moves, local 09:00 does not
assert ("ben", "Booked: Standup 2026-03-02 14:00 Europe/London (x3)") in notifier.sent
svc.book("A", ana, "Next", day.replace(hour=10), day.replace(hour=11), NY) # back-to-back is fine
try:
svc.book("A", ana, "Overlap", datetime(2026, 3, 9, 9, 30), datetime(2026, 3, 9, 10, 30), NY)
raise AssertionError("expected a conflict")
except BookingConflict as e:
assert e.clashes[0] is standup[1]
try: # clashes on 2 March only, so nothing is booked
svc.book("A", ana, "Weekly", day.replace(hour=10, minute=30), day.replace(hour=11, minute=30), NY, weekly=3)
raise AssertionError("expected a conflict")
except BookingConflict:
pass
assert [r.id for r in svc.free_rooms(datetime(2026, 3, 16, 10, 30), datetime(2026, 3, 16, 11), NY, 2)] == ["A", "B", "C"]
mon9 = (datetime(2026, 3, 9, 9), datetime(2026, 3, 9, 10), NY)
assert [r.id for r in svc.free_rooms(*mon9, people=3, needs=frozenset({"tv"}))] == ["B"]
svc.cancel(standup[1].id, ana)
assert [r.id for r in svc.free_rooms(*mon9, people=3, needs=frozenset({"tv"}))] == ["A", "B"]
assert ("ben", "Cancelled: Standup 2026-03-09 13:00 Europe/London") in notifier.sent
print("rooms.py: all assertions passed")
import assert from "node:assert/strict";
// ---------- time: instants are epoch milliseconds in UTC; wall-clock times are "YYYY-MM-DDTHH:mm" strings ----------
const MIN = 60_000, HOUR = 60 * MIN, DAY = 24 * HOUR;
const fmtCache = new Map<string, Intl.DateTimeFormat>();
/** Offset of `zone` from UTC at instant t, in ms. Uses the ICU time zone data built into Node. */
function offsetAt(t: number, zone: string): number {
let f = fmtCache.get(zone);
if (!f) {
f = new Intl.DateTimeFormat("en-US", { timeZone: zone, hourCycle: "h23", year: "numeric", month: "numeric",
day: "numeric", hour: "numeric", minute: "numeric" });
fmtCache.set(zone, f);
}
const p = Object.fromEntries(f.formatToParts(t).map((x) => [x.type, Number(x.value)]));
return Date.UTC(p.year, p.month - 1, p.day, p.hour, p.minute) - Math.floor(t / MIN) * MIN;
}
/** Wall-clock time in a zone -> UTC. DST gaps move forward, overlaps take the earlier instant, like java.time. */
export function toUtc(local: string, zone: string): number {
const wall = Date.parse(local + "Z"); // the wall-clock reading, as if it were UTC
const before = wall - offsetAt(wall - DAY / 4, zone); // try the offset in force before any transition
const after = wall - offsetAt(wall + DAY / 4, zone); // and the one after it
const valid = [before, after].filter((t) => t + offsetAt(t, zone) === wall);
return valid.length ? Math.min(...valid) : before; // none valid means a gap: keep the old offset
}
export function toLocal(t: number, zone: string): string {
return new Date(t + offsetAt(t, zone)).toISOString().slice(0, 16).replace("T", " ");
}
const addWeeks = (local: string, k: number) => new Date(Date.parse(local + "Z") + k * 7 * DAY).toISOString().slice(0, 16);
/** Half-open [start, end), so 9-10 and 10-11 do not overlap. */
export class Interval {
constructor(readonly start: number, readonly end: number) {
if (!(start < end)) throw new Error("start must be before end");
}
static of(start: string, end: string, zone: string): Interval { return new Interval(toUtc(start, zone), toUtc(end, zone)); }
}
export interface Room { readonly id: string; readonly capacity: number; readonly equipment: ReadonlySet<string> }
export interface Person { readonly id: string; readonly zone: string }
export type Status = "CONFIRMED" | "CANCELLED";
export class Booking {
status: Status = "CONFIRMED";
constructor(readonly id: string, readonly roomId: string, readonly organizer: Person, readonly title: string,
readonly interval: Interval, readonly attendees: readonly Person[], readonly seriesId: string | null) {}
}
export class BookingConflictError extends Error {
constructor(readonly clashes: Booking[]) { super(`${clashes.length} clash(es)`); }
}
/** One room's bookings sorted by start. They never overlap, so only the two neighbours can clash. */
export class RoomCalendar {
private readonly items: Booking[] = [];
/** Index of the first booking that starts at or after t (a TreeMap ceiling, by binary search). */
private ceilingIndex(t: number): number {
let lo = 0, hi = this.items.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (this.items[mid].interval.start < t) lo = mid + 1; else hi = mid;
}
return lo;
}
clash(iv: Interval): Booking | null {
const i = this.ceilingIndex(iv.start);
if (i < this.items.length && this.items[i].interval.start < iv.end) return this.items[i]; // ceiling
if (i > 0 && this.items[i - 1].interval.end > iv.start) return this.items[i - 1]; // floor
return null;
}
add(b: Booking): void { this.items.splice(this.ceilingIndex(b.interval.start), 0, b); }
remove(b: Booking): void {
const i = this.ceilingIndex(b.interval.start);
if (this.items[i] === b) this.items.splice(i, 1);
}
}
export interface BookingListener {
onBooked(bookings: Booking[]): void;
onCancelled(bookings: Booking[]): void;
}
/** Tells every participant, in their own time zone. */
export class Notifier implements BookingListener {
readonly sent: string[] = [];
private tell(verb: string, bs: Booking[]): void {
const first = bs[0];
for (const p of new Set([first.organizer, ...first.attendees])) {
const times = bs.length > 1 ? ` (x${bs.length})` : "";
this.sent.push(`${p.id}: ${verb}: ${first.title} ${toLocal(first.interval.start, p.zone)} ${p.zone}${times}`);
}
}
onBooked(bs: Booking[]): void { this.tell("Booked", bs); }
onCancelled(bs: Booking[]): void { this.tell("Cancelled", bs); }
}
export class BookingService {
readonly rooms: Map<string, Room>;
readonly bookings = new Map<string, Booking>();
readonly listeners: BookingListener[] = [];
private readonly calendars = new Map<string, RoomCalendar>();
private nextId = 1;
constructor(rooms: Room[], private readonly clock: () => number = Date.now) {
this.rooms = new Map(rooms.map((r) => [r.id, r]));
for (const r of rooms) this.calendars.set(r.id, new RoomCalendar());
}
/** Book start-end (wall-clock in zone), optionally repeating weekly. All occurrences or none.
* Synchronous, so no other booking can interleave between the check and the insert. */
book(roomId: string, organizer: Person, title: string, start: string, end: string, zone: string,
attendees: Person[] = [], weekly = 1): Booking[] {
const room = this.rooms.get(roomId)!;
if (attendees.length + 1 > room.capacity) throw new Error(`${roomId} seats ${room.capacity}`);
const slots = Array.from({ length: weekly }, (_, k) => Interval.of(addWeeks(start, k), addWeeks(end, k), zone));
if (slots[0].start <= this.clock()) throw new Error("cannot book in the past");
const cal = this.calendars.get(roomId)!;
const clashes = slots.map((s) => cal.clash(s)).filter((b): b is Booking => b !== null);
if (clashes.length) throw new BookingConflictError(clashes);
const series = weekly > 1 ? `s${this.nextId++}` : null;
const made = slots.map((iv) => new Booking(`b${this.nextId++}`, roomId, organizer, title, iv, attendees, series));
for (const b of made) { cal.add(b); this.bookings.set(b.id, b); }
for (const l of this.listeners) l.onBooked(made);
return made;
}
cancel(bookingId: string, by: Person, wholeSeries = false): void {
const target = this.bookings.get(bookingId)!;
if (target.organizer.id !== by.id) throw new Error("only the organizer can cancel");
const group = [...this.bookings.values()].filter((b) => b.status === "CONFIRMED" && (b === target ||
(wholeSeries && target.seriesId !== null && b.seriesId === target.seriesId && b.interval.start >= target.interval.start)));
const cal = this.calendars.get(target.roomId)!;
for (const b of group) { cal.remove(b); b.status = "CANCELLED"; }
if (group.length) for (const l of this.listeners) l.onCancelled(group);
}
/** Rooms that fit, smallest first. The answer can be stale a moment later: book() re-checks. */
freeRooms(start: string, end: string, zone: string, people: number, needs: string[] = []): Room[] {
const iv = Interval.of(start, end, zone);
return [...this.rooms.values()]
.filter((r) => r.capacity >= people && needs.every((n) => r.equipment.has(n)))
.sort((a, b) => a.capacity - b.capacity || a.id.localeCompare(b.id))
.filter((r) => this.calendars.get(r.id)!.clash(iv) === null);
}
}
export const NY = "America/New_York";
export const ana: Person = { id: "ana", zone: NY }, ben: Person = { id: "ben", zone: "Europe/London" };
export function demoService(): [BookingService, Notifier] {
const svc = new BookingService([
{ id: "A", capacity: 4, equipment: new Set(["tv"]) },
{ id: "B", capacity: 8, equipment: new Set(["tv", "video"]) },
{ id: "C", capacity: 20, equipment: new Set(["video", "whiteboard"]) },
], () => Date.parse("2026-03-01T00:00Z"));
const notifier = new Notifier();
svc.listeners.push(notifier);
return [svc, notifier];
}
if (process.argv[1]?.endsWith("rooms.ts")) {
const [svc, notifier] = demoService();
const ids = (rooms: Room[]) => rooms.map((r) => r.id);
// 2 March is a Monday. US clocks change on 8 March.
const standup = svc.book("A", ana, "Standup", "2026-03-02T09:00", "2026-03-02T10:00", NY, [ben], 3);
assert.deepEqual(standup.map((b) => new Date(b.interval.start).getUTCHours()), [14, 13, 13]);
assert.ok(notifier.sent.includes("ben: Booked: Standup 2026-03-02 14:00 Europe/London (x3)"));
svc.book("A", ana, "Next", "2026-03-02T10:00", "2026-03-02T11:00", NY); // back-to-back is fine
assert.throws(() => svc.book("A", ana, "Overlap", "2026-03-09T09:30", "2026-03-09T10:30", NY),
(e: unknown) => e instanceof BookingConflictError && e.clashes[0] === standup[1]);
assert.throws(() => svc.book("A", ana, "Weekly", "2026-03-02T10:30", "2026-03-02T11:30", NY, [], 3), BookingConflictError);
assert.deepEqual(ids(svc.freeRooms("2026-03-16T10:30", "2026-03-16T11:00", NY, 2)), ["A", "B", "C"]);
assert.deepEqual(ids(svc.freeRooms("2026-03-09T09:00", "2026-03-09T10:00", NY, 3, ["tv"])), ["B"]);
svc.cancel(standup[1].id, ana);
assert.deepEqual(ids(svc.freeRooms("2026-03-09T09:00", "2026-03-09T10:00", NY, 3, ["tv"])), ["A", "B"]);
assert.ok(notifier.sent.includes("ben: Cancelled: Standup 2026-03-09 13:00 Europe/London"));
// DST edge cases agree with java.time and Python's zoneinfo.
assert.equal(new Date(toUtc("2026-03-29T01:30", "Europe/London")).toISOString(), "2026-03-29T01:30:00.000Z"); // gap
assert.equal(new Date(toUtc("2026-10-25T01:30", "Europe/London")).toISOString(), "2026-10-25T00:30:00.000Z"); // overlap
console.log("rooms.ts: all assertions passed");
}
Notes:
- The TypeScript
toUtcneeds no library. Node ships the IANA time zone data inside ICU, andIntl.DateTimeFormatcan tell you the wall-clock reading at any instant. From that, the offset follows. The function tries the offset in force just before and just after the wall time, and keeps whichever candidates round-trip. When the Temporal API is available in your runtime,Temporal.ZonedDateTimereplaces all of it. - Python on Windows needs
pip install tzdata, becausezoneinforeads the operating system's zone files and Windows has none. free_roomstakes each room's lock briefly and returns a snapshot. By the time the user clicks "Book", the room may be gone, andbookchecks again. Search is advisory. Booking is authoritative.
7. Concurrency
| Shared state | Contended by | Protection |
|---|---|---|
| A room's calendar | all bookings and cancellations of that room, and searches | the calendar's lock, held for check-and-insert as one step |
bookings map (ID to booking) | every booking | ConcurrentHashMap in Java; in Python, writes happen under a calendar lock and dict operations are atomic |
Booking.status | cancel versus no-show release | written under the room lock, volatile in Java for readers |
| ID counter | every booking | AtomicLong / a small lock |
The race
sequenceDiagram
participant A as Alice
participant C as Room C calendar
participant B as Bob
Note over A,B: Broken: check and insert are separate
A->>C: clash(9 to 10)? none
B->>C: clash(9:30 to 10:30)? none
A->>C: insert 9 to 10
B->>C: insert 9:30 to 10:30
Note over A,B: the room is double-booked from 9:30 to 10
The two intervals aren't even equal, so a unique key on (room, start) wouldn't catch it. The invariant is about overlap, so the protection has to cover the overlap check and the insert together. book holds the room's lock while it checks every occurrence and inserts them all. Bob's call waits, then finds Alice's booking as its floor and gets a BookingConflict.
Rules that keep this correct:
- One lock per room, never a global one. Different rooms proceed in parallel.
- Notify after unlocking. A listener that sends email or calls a chat API must never run while the room is locked.
- Validation that doesn't depend on the calendar (capacity, the past, time-zone conversion) runs before taking the lock, keeping the critical section short.
- Multi-room operations lock rooms in a fixed order. That's the deadlock rule, used by the multi-room extension below.
In a database the same invariant is enforced with a lock on the room row (SELECT … FOR UPDATE) around the overlap query and insert. PostgreSQL can even enforce it declaratively with an exclusion constraint: EXCLUDE USING gist (room_id WITH =, tstzrange(start_at, end_at) WITH &&), which needs the btree_gist extension for the = part. With the constraint in place, a racing insert fails at commit and two bookings can never overlap (PostgreSQL docs: exclusion constraints). That's the strongest answer to give, because the database enforces the rule no matter which code path writes.
TypeScript. Node runs one thread, and book is synchronous from the clash check to the insert, so nothing can interleave. If you add an await (a database call, an approval check) between them, you need the database-side guarantee above.
8. The interviewer adds…
"Book a room in two offices at once, both or neither"
A video call needs room C in New York and a room in London for the same instant. It's all-or-nothing across rooms, so take every room's lock first. To avoid deadlock with a concurrent call locking the same rooms in another order, always lock in sorted room ID order.
import java.time.*;
import java.util.*;
/** "Book the same slot in Delhi and London rooms for a video call: both or neither." */
final class MultiRoomBooker {
private final BookingService svc;
MultiRoomBooker(BookingService svc) { this.svc = svc; }
List<Booking> bookAll(List<String> roomIds, Person organizer, String title, Interval iv) {
List<String> ordered = roomIds.stream().sorted().distinct().toList(); // one global lock order: no deadlock
return lockThen(ordered, 0, () -> {
for (String id : ordered)
svc.calendar(id).clash(iv).ifPresent(c -> { throw new BookingConflictException(List.of(c)); });
List<Booking> made = new ArrayList<>();
for (String id : ordered) {
Booking b = new Booking("m-" + UUID.randomUUID(), id, organizer, title, iv, List.of(), null);
svc.calendar(id).add(b);
svc.bookings.put(b.id, b);
made.add(b);
}
return made;
});
}
private <T> T lockThen(List<String> ids, int i, java.util.function.Supplier<T> body) {
if (i == ids.size()) return body.get();
synchronized (svc.calendar(ids.get(i))) { return lockThen(ids, i + 1, body); }
}
}
public class ExtMultiRoom {
public static void main(String[] args) {
BookingService svc = Main.demoService(new Notifier());
MultiRoomBooker multi = new MultiRoomBooker(svc);
Interval iv = Interval.of(LocalDateTime.of(2026, 4, 1, 9, 0), LocalDateTime.of(2026, 4, 1, 10, 0), Main.NY);
svc.book("B", Main.ANA, "taken", LocalDateTime.of(2026, 4, 1, 9, 30), LocalDateTime.of(2026, 4, 1, 11, 0), Main.NY, List.of(), 1);
try { multi.bookAll(List.of("C", "A", "B"), Main.ANA, "sync", iv); throw new AssertionError(); }
catch (BookingConflictException expected) { }
assert svc.calendar("A").clash(iv).isEmpty() && svc.calendar("C").clash(iv).isEmpty(); // nothing half-booked
assert multi.bookAll(List.of("C", "A"), Main.ANA, "sync", iv).size() == 2;
System.out.println("ExtMultiRoom: ok");
}
}
Because RoomCalendar's methods also synchronise on the calendar, and Java monitors are reentrant, calling clash and add while holding the locks is safe. In a database this is one transaction that locks the room rows in ID order.
"Release rooms nobody shows up to"
Ghost bookings, where a recurring meeting nobody attends any more holds a room every week, are the most common complaint about real room systems. A check-in policy releases a booking if nobody checks in within 10 minutes of the start. It reuses cancel, so every listener (including notifications) hears about it.
from datetime import datetime, timedelta
from rooms import UTC, Booking, BookingService, Status, demo_service
GRACE = timedelta(minutes=10)
class CheckInPolicy:
"""Rooms nobody checks into within 10 minutes of the start go back to the pool."""
def __init__(self, svc: BookingService) -> None:
self.svc = svc
self.checked_in: set[str] = set()
def check_in(self, booking: Booking, now: datetime) -> None:
if not booking.interval.start - GRACE <= now <= booking.interval.start + GRACE:
raise ValueError("check-in opens 10 minutes either side of the start")
self.checked_in.add(booking.id)
def release_no_shows(self, now: datetime) -> list[Booking]:
"""Run every minute from a scheduler. Reuses cancel(), so listeners hear about it."""
due = [b for b in list(self.svc.bookings.values())
if b.status is Status.CONFIRMED and b.id not in self.checked_in
and b.interval.start + GRACE < now < b.interval.end]
for b in due:
self.svc.cancel(b.id, b.organizer)
return due
svc, notifier, ana, ben = demo_service()
policy = CheckInPolicy(svc)
kept = svc.book("A", ana, "kept", datetime(2026, 4, 1, 9), datetime(2026, 4, 1, 10), "UTC")[0]
ghost = svc.book("B", ana, "ghost", datetime(2026, 4, 1, 9), datetime(2026, 4, 1, 10), "UTC")[0]
policy.check_in(kept, datetime(2026, 4, 1, 9, 3, tzinfo=UTC))
released = policy.release_no_shows(datetime(2026, 4, 1, 9, 11, tzinfo=UTC))
assert released == [ghost] and kept.status is Status.CONFIRMED and ghost.status is Status.CANCELLED
assert [r.id for r in svc.free_rooms(datetime(2026, 4, 1, 9, 15), datetime(2026, 4, 1, 10), "UTC", 2)] == ["B", "C"]
print("ext_no_show: ok")
The release job runs on a schedule, and it can race with a late check-in. Both go through the room's lock in production, by doing the check-in and the release under the calendar lock or as conditional updates (UPDATE … WHERE status = 'CONFIRMED' AND checked_in = false), so a check-in at 09:10:59 and a release at 09:11:00 can't both win.
"Add 10 minutes of cleaning time after each meeting"
Change the conflict rule, not the bookings. Pad the existing booking's end when comparing (floor.end + buffer > s) and the candidate's end against the ceiling (e + buffer > ceiling.start). Booked times shown to people stay accurate, and the buffer is a per-room setting.
9. Testing
Unit tests pin the interval maths and the DST conversions. Stress tests check an invariant that must hold under any interleaving: no two confirmed bookings of a room overlap. Inject the clock so "not in the past" tests are deterministic, as described in designing for testability.
import random
import threading
from datetime import datetime, timedelta
from rooms import UTC, BookingConflict, Interval, Status, demo_service, to_utc
NY = "America/New_York"
def at(h: float) -> datetime:
return datetime(2026, 4, 1, tzinfo=UTC) + timedelta(hours=h)
def test_half_open_intervals_and_neighbour_checks():
svc, _, ana, _ = demo_service()
svc.book("A", ana, "x", datetime(2026, 4, 1, 9), datetime(2026, 4, 1, 10), "UTC")
cal = svc.calendar("A")
cases = {(8, 9): False, (8, 9.02): True, (9.98, 11): True, (10, 11): False, (8, 11): True, (9.25, 9.75): True}
for (s, e), clashes in cases.items():
assert (cal.clash(Interval(at(s), at(e))) is not None) == clashes, (s, e)
def test_dst_gap_and_overlap_match_java_time():
assert to_utc(datetime(2026, 3, 29, 1, 30), "Europe/London") == datetime(2026, 3, 29, 1, 30, tzinfo=UTC)
assert to_utc(datetime(2026, 10, 25, 1, 30), "Europe/London") == datetime(2026, 10, 25, 0, 30, tzinfo=UTC)
def test_validation():
svc, _, ana, ben = demo_service()
for bad in [lambda: svc.book("A", ana, "past", datetime(2026, 2, 1, 9), datetime(2026, 2, 1, 10), NY),
lambda: svc.book("A", ana, "big", datetime(2026, 4, 1, 9), datetime(2026, 4, 1, 10), NY, (ben,) * 4),
lambda: svc.book("A", ana, "backwards", datetime(2026, 4, 1, 10), datetime(2026, 4, 1, 9), NY)]:
try:
bad()
raise AssertionError("expected ValueError")
except ValueError:
pass
def test_cancel_this_and_following_only_by_organizer():
svc, notifier, ana, ben = demo_service()
series = svc.book("B", ana, "1:1", datetime(2026, 4, 6, 15), datetime(2026, 4, 6, 15, 30), NY, (ben,), weekly=4)
try:
svc.cancel(series[1].id, ben, whole_series=True)
raise AssertionError("expected PermissionError")
except PermissionError:
pass
svc.cancel(series[1].id, ana, whole_series=True)
assert [b.status for b in series] == [Status.CONFIRMED] + [Status.CANCELLED] * 3
assert any(m.startswith("Cancelled: 1:1") and m.endswith("(x3)") for _, m in notifier.sent)
def test_sixteen_threads_one_slot_one_winner():
svc, _, ana, _ = demo_service()
wins, barrier = [], threading.Barrier(16)
def attempt() -> None:
barrier.wait()
try:
wins.append(svc.book("C", ana, "race", datetime(2026, 4, 1, 9), datetime(2026, 4, 1, 10), NY))
except BookingConflict:
pass
threads = [threading.Thread(target=attempt) for _ in range(16)]
[t.start() for t in threads]
[t.join() for t in threads]
assert len(wins) == 1
def test_random_concurrent_bookings_never_overlap():
svc, _, ana, _ = demo_service()
def spam(seed: int) -> None:
rnd = random.Random(seed)
for _ in range(100):
start = datetime(2026, 4, 1, 8) + timedelta(minutes=15 * rnd.randrange(40))
try:
svc.book("C", ana, "r", start, start + timedelta(minutes=15 * rnd.randint(1, 8)), NY)
except BookingConflict:
pass
threads = [threading.Thread(target=spam, args=(i,)) for i in range(8)]
[t.start() for t in threads]
[t.join() for t in threads]
live = sorted((b.interval for b in svc.bookings.values() if b.status is Status.CONFIRMED), key=lambda iv: iv.start)
assert all(a.end <= b.start for a, b in zip(live, live[1:]))
if __name__ == "__main__":
for name, fn in list(globals().items()):
if name.startswith("test_"):
fn()
print("ok", name)
The Java stress test uses real parallel threads. Sixteen threads each try 200 random bookings on one room, over 30 rounds, and the test checks that the winners never overlap.
import java.time.*;
import java.util.*;
import java.util.concurrent.*;
public class RoomRaceTest {
public static void main(String[] args) throws Exception {
for (int round = 0; round < 30; round++) {
BookingService svc = Main.demoService(new Notifier());
LocalDateTime base = LocalDateTime.of(2026, 4, 1, 8, 0);
List<Booking> wins = new CopyOnWriteArrayList<>();
CountDownLatch go = new CountDownLatch(1);
try (ExecutorService pool = Executors.newFixedThreadPool(16)) {
for (int t = 0; t < 16; t++) {
long seed = round * 100L + t;
pool.submit(() -> {
Random rnd = new Random(seed);
go.await();
for (int i = 0; i < 200; i++) {
LocalDateTime s = base.plusMinutes(15L * rnd.nextInt(40));
try { wins.addAll(svc.book("C", Main.ANA, "r", s, s.plusMinutes(15L * (1 + rnd.nextInt(8))), Main.NY, List.of(), 1)); }
catch (BookingConflictException lost) { }
}
return null;
});
}
go.countDown();
}
List<Interval> live = wins.stream().map(b -> b.interval).sorted(Comparator.comparing(Interval::start)).toList();
for (int i = 1; i < live.size(); i++)
assert !live.get(i - 1).end().isAfter(live.get(i).start()) : "overlap in round " + round;
}
System.out.println("RoomRaceTest: no overlaps in 30 rounds");
}
}
Edge cases worth a test of their own: a meeting that crosses midnight, one that spans a DST change (a 01:00–03:00 booking on the fall-back night lasts three real hours), an attendee whose zone is the same as the organizer's, and a series whose first occurrence falls in a DST gap.
10. Common mistakes
- Storing local times, or fixed offsets. "09:00-05:00" is wrong half the year. Store instants and keep the zone for display and recurrence.
- Recurring by adding 7×24 hours. The meeting moves an hour after every clock change.
- Closed intervals. If
[9, 10]and[10, 11]overlap, nobody can book back-to-back. Use half-open[start, end). - Getting the overlap test wrong. The whole test is
a.start < b.end && b.start < a.end. Hand-written versions with four cases usually miss "contains" or "contained by". - Scanning every booking for conflicts. It's O(n) per check and gets slower every week. Floor and ceiling make it O(log n).
- Check then insert without a lock. Two overlapping requests both pass the check.
- A global lock. Correct, but the whole company queues behind one popular room.
- Notifying inside the lock. A slow mail server stalls every booking of that room.
- Booking half a series. If occurrence 3 of 10 clashes and you've already inserted 1 and 2, the organizer gets a partial series they didn't ask for. Check all, then insert all.
- Showing everyone the organizer's time. The London attendee needs London time.
11. Interview follow-ups
How would you suggest the next free slot when the requested one is taken?
Start from the clashing booking and walk forward through the calendar's sorted entries. The first gap of at least the requested length is the answer: higherEntry in Java, or the next index in the sorted list. Across several rooms, merge the rooms' next gaps and keep the earliest.
How do you find a time when all attendees are free? Gather each attendee's busy intervals for the day from their own calendars, merge them into one sorted list, coalesce overlaps, and read the gaps. That's O(n log n) over all intervals. Intersect the result with working hours in each attendee's zone, which is where time zones bite again.
How would you support "every second Tuesday" or "last Friday of the month"?
Use an iCalendar RRULE (RFC 5545) as the series definition, and a library to expand it. Keep the eager expansion up to a horizon, and keep the rule on the series so you can extend it and so exceptions (one moved occurrence) are stored as overrides.
A country abolishes daylight saving with three months' notice. What breaks? Future bookings were converted to instants using the old rules, so after the tzdata update they're an hour off in local time. This is why careful calendar systems store future events as local time plus zone and compute the instant when needed, or recompute stored instants for future events when tzdata changes. Mentioning this is a strong signal. For past events, the stored instant is right.
How would you scale this to a company with 5,000 rooms?
Calendars are independent per room, so shard by room ID. Search fans out to the rooms that match capacity and equipment (an index narrows this a lot), and each check is O(log n). In a database, an index on (room_id, start_at) plus the exclusion constraint does the work.
What if a room's capacity is reduced after bookings exist? Find future bookings whose attendee count is over the new capacity and notify their organizers. Don't cancel them automatically. Capacity was valid when they booked.
Should a cancelled booking be deleted?
No, keep it with status CANCELLED. People ask "who cancelled my meeting?", and analytics on cancellations and no-shows help with planning space.
How would you integrate with Google Calendar or Outlook? As another listener that pushes changes out, plus an inbound sync that maps external events to bookings. The hard part is conflict resolution when both sides change the same event, so make one side authoritative for room availability. The delivery side looks like the notification service case study.