Notes
Requirements
Fix the scope. Rooms have an id, a capacity and a floor. A booking request names the organizer, the number of people, a start and an end, and either asks for a specific room or lets the system pick one that fits. Bookings in the same room never overlap. People can cancel, set up weekly meetings, and see a room's free slots. Attendees get notified. Many people book at the same time.
Clarify the rules that change the code. Can one meeting end at eleven and the next start at eleven in the same room? Yes, so intervals are half-open: the end is not included. If several rooms fit, which one? The smallest, so big rooms stay free. If one week of a weekly series is taken, do we split rooms? No, the whole series goes in one room or fails. And a single occurrence can be cancelled by its id.
- rooms: id, capacity, floor
- book(who, people, start, end)
- any room that fits, or a
- specific room
- never two bookings overlapping
- in one room
- cancel(bookingId)
- weekly meetings
- notify attendees
- free slots in a room today
- many people booking at once
- 10-11 then 11-12, same room?
- allowed: end is exclusive
- which room if many fit?
- the smallest that fits
- weekly, one week is taken?
- same room for all, or fail
- cancel one of a series?
- yes, by booking id
- time zones? one, local time
Entities
The entities. A room is plain data. A booking ties an organizer and a head count to a room and an interval. A request is what the caller asks for before a room is chosen. The key design choice is a calendar per room, which holds that room's bookings and owns the conflict check. The scheduler is the service object on top: it picks rooms, keeps an index of bookings by id, and tells listeners.
Class diagram
Turn them into records. The interval validates that the end is after the start, and owns the overlap rule: two half-open intervals overlap when each one starts before the other ends. With that rule, ten to eleven and eleven to twelve do not overlap, which is what people expect. Room, booking and request are records too, so they are immutable and safe to pass between threads. Only the calendars change.
record Interval(LocalDateTime start,
LocalDateTime end) {
boolean overlaps(Interval o) {
return start.isBefore(o.end)
&& o.start.isBefore(end);
}
}
record Room(id, capacity, floor)
record Booking(id, roomId, organizer,
attendees, when, seriesId)
record Request(organizer, n, when, room) Conflict detection
Conflict detection. Keep each room's bookings in a tree map sorted by start time. Because stored bookings never overlap each other, only one can clash with a new slot: the one with the latest start before our end. Tree map's lower entry finds it in log time. If it ends after our start, we clash; otherwise the slot is free. Compare that with scanning every booking in the room, which is linear and is the answer interviewers hope you improve on.
TreeMap<LocalDateTime, Booking> byStart
e = byStart.lowerEntry(w.end)
free = e == null
|| !e.end.isAfter(w.start)
room has 10-11 and 11-12
ask 10:30-11:30:
lowerEntry(11:30) is 11-12
11-12 ends after 10:30: clash Sorted map or tree?
When do you need an interval tree? Only when the stored intervals can overlap each other, like one person's calendar with clashing invites, or one index across every room, and you ask for all intervals that touch a time. An interval tree keeps the maximum end in each subtree and answers in log n plus the number of matches. Inside one room nothing overlaps, so a sorted map is simpler and just as fast. Say that trade-off out loud.
- list + scan: O(n), fine for
- a demo, say why it is slow
- sorted map per room: O(log n)
- works when stored intervals
- never overlap each other
- interval tree: O(log n + k)
- when stored ones DO overlap,
- e.g. a person's calendar or
- all rooms in one index
Strategy: room choice
Which room should a meeting of three get? That is a policy, so it is a Strategy. The interface returns candidate rooms in the order to try. Our default, best fit, keeps rooms with enough seats and sorts by capacity, so a three-person meeting takes a four-seat room and leaves the twelve-seat boardroom free. Nearest to the organizer's floor, or rooms with video equipment, are new classes, and the scheduler does not change.
interface RoomSelection {
List<RoomCalendar> candidates(
List<RoomCalendar> all, Request r);
}
BestFit: capacity >= people,
smallest first, then by id
NearestFloor, HasVideo, Quietest:
new classes, scheduler unchanged Flow: book
Walk a booking. A tech lead wants four people from ten thirty. The strategy offers Focus-1 first, but it has a meeting until eleven, so its reserve fails. Huddle-2 is free, its reserve succeeds, and the booking is stored in an index by id and announced to listeners. If every candidate fails, throw a clear no-room error that says what was asked. A specific room request just narrows the candidates to that one room.
id = next id
for (c : candidates(request)) {
b = new Booking(id, c.room, ...)
if (c.tryReserve(b)) {
byId.put(id, b)
notify listeners; return b
}
}
throw: no room for 4 at 10:30 Flow: cancel
Cancelling removes the booking from the id index first. That removal is atomic on a concurrent map, so if two people press cancel together, only one finds it, and the other gets false. Then the room's calendar releases the slot, and listeners hear about the cancellation so attendees get a notice. In the demo the freed boardroom slot is booked again straight away.
b = byId.remove(id) if (b == null) return false calendar(b.room).release(b) listeners: onCancelled(b) return true second cancel(B4): false
Observer: notifications
Notifications use the Observer pattern. The scheduler knows one interface with two methods, booked and cancelled. Email invites, calendar sync, a reminder service and the screens outside each room all subscribe. The scheduler never knows how many there are or how they send things. In a real service these calls would go onto a queue so a slow mail server never holds up a booking.
interface BookingListener {
void onBooked(Booking b);
void onCancelled(Booking b);
}
listeners = CopyOnWriteArrayList
email invites, calendar sync,
reminders 10 min before,
room display panels Recurring meetings
Weekly meetings expand into one booking per week, all in the same room. For each candidate room, reserve the occurrences one by one. If any week is already taken, release the ones we made and move to the next room. In the demo, week three of Huddle-2 is taken, so the standup is rolled back there and lands in the boardroom for all four weeks. All or nothing per room is the rule we agreed while clarifying.
for (c : candidates) {
made = []
for (w in 0..weeks-1)
if (!c.tryReserve(occurrence w))
break
made.add(it)
if all made: notify, return made
made.forEach(c::release) // undo
}
throw: no room free every week Free slots
Finding free slots is one walk over the sorted map. Take the bookings inside the day's opening hours in start order, and move a cursor forward: whenever the next booking starts at least the minimum length after the cursor, that gap is free. Then the cursor jumps to the booking's end. After the last booking, the rest of the day may be free too. For Focus-1 between nine and one, that gives nine to ten and twelve to one.
cursor = day.start
for (b : byStart.subMap(day))
if (b.start - cursor >= min)
add [cursor, b.start)
cursor = max(cursor, b.end)
if (day.end - cursor >= min)
add [cursor, day.end)
Focus-1, 09-13, 30 min or more:
09:00-10:00, 12:00-13:00 Concurrency
Concurrency. If checking and inserting were separate steps, two people could both see the slot free and both insert. So try reserve does the check and the insert inside one synchronized method on that room's calendar. Each room has its own lock, so bookings for different rooms never wait for each other. In the demo ten threads race for the same room and hour, and exactly one wins, every run.
- tryReserve = isFree + put,
- one synchronized method
- lock per room: rooms never
- wait on each other
- byId: ConcurrentHashMap
- listeners: CopyOnWriteArrayList
- records: immutable
- test: 10 threads, one slot
- exactly 1 booked
Extensibility
Extensions. Monthly or custom repeats become a recurrence rule strategy that produces the dates. Boardroom bookings that need approval get a pending state. Holding a slot while someone fills in the form is a hold that expires after a few minutes. Cleaning time between meetings is a padded interval. Several offices are a map of schedulers by site. None of these touch the conflict check.
- monthly or custom repeats:
- a RecurrenceRule strategy
- approval for big rooms:
- booking state PENDING
- hold a slot while choosing:
- a hold that expires
- buffer between meetings:
- pad the interval by 5 min
- many offices: a map per site
Testing
The full code is below the player. The demo books four meetings and checks best fit, the move to the next room, and that eleven o'clock back to back is allowed. A ten-person meeting at ten fifteen finds no room until the boardroom booking is cancelled. A weekly standup rolls back from Huddle-2 and lands in the boardroom. Then free slots, and ten threads racing for one slot.
B1 Focus-1 10:00-11:00 B2 Huddle-2 10:30-11:30 B3 Focus-1 11:00-12:00 B4 Board-3 10:00-11:00 10 people at 10:15: no room for 10 at 10:15 after cancel: B6 Board-3 10:15-10:45 weekly standup x4 in Board-3, series S8 Focus-1 free (30+ min, 09-13): [09:00-10:00, 12:00-13:00] race for Focus-1 15:00: 10 tries, 1 booked all checks passed
Follow-ups
Expect follow-ups. The minimum number of rooms for a list of meetings: sort by start and keep a min-heap of end times, reusing a room when the earliest end is before the next start; the heap's largest size is the answer. Stopping a person from being in two meetings means a calendar per person too. With a database, an exclusion or unique constraint makes the store itself reject overlaps.
- fewest rooms for a day's
- meetings? sort starts, keep
- a min-heap of end times
- person double-booked?
- a calendar per person too
- thousands of rooms?
- index by capacity and floor
- persist? unique constraint or
- exclusion constraint in SQL
Say it like this
The short version. Intervals are half-open. Each room keeps its bookings in a tree map by start time, and lower entry of our end finds the only booking that could clash, in log time. Room choice is a strategy, notifications are observers, and a weekly series is reserved all or nothing in one room. Reserving is a check and insert inside one lock per room, so two people never get the same slot.
- "Intervals are half-open. Each
- room has a TreeMap by start;
- lowerEntry(end) finds the only
- booking that can clash, in
- log n. Room choice is a
- strategy, notices are
- observers, series are all or
- nothing, and reserve is
- synchronized per room."