Real-World SystemsProblem 8 of 16
Real-World SystemsIntermediate
Meeting Scheduler
Strategy PatternState PatternObserver PatternFacade Pattern
Rooms, recurring series, RSVP, single-instance vs series cancel. The trick is modeling Meeting as a series and MeetingInstance as the occurrence — each attendee has their own calendar that a decline removes the slot from.
Key Abstractions
Meeting
The series. Owns organizer, attendees, room, and a map of MeetingInstances keyed by instance id.
MeetingInstance
One concrete occurrence. Start, end, per-attendee RSVP status, cancelled flag.
Recurrence
Strategy — OneShot, Daily, Weekly. Expands a start + seriesEnd into a list of occurrence starts.
Room
Physical room with capacity and a TreeMap of booked MeetingInstances for O(log n) conflict check.
UserCalendar
Per-user TreeMap of busy MeetingInstances. A declined instance is removed from this calendar only.
RoomSelectionStrategy
Picks a room that's free for every instance in the series — smallest-that-fits, nearest-floor
Scheduler
Facade. Book, respond, cancel-instance, cancel-series, free-busy queries.
NotificationBus
Publishes booked / response / cancelled events to calendar integrations.
Class Diagram
The Key Insight
A meeting is not one row in a table. It's a series with occurrences. A weekly stand-up generates 52 MeetingInstance rows a year; cancelling one Tuesday touches exactly one of them; the other 51 live on. Any design that stores one interval per meeting falls over the moment recurrence shows up.
The second load-bearing idea is per-user calendars. The conference room has its own booking table; so does every attendee. When someone declines, the instance disappears from their calendar only — the room stays booked, the organizer still has the slot on their own calendar, the declining user is simply free. A single shared "meeting" table can't express this cleanly; per-user calendars can, with the same O(log n) TreeMap trick applied twice.
Half-open intervals, TreeMap floorEntry / ceilingEntry, and the RoomSelectionStrategy carry over from the simpler version. The new pieces — Recurrence, MeetingInstance, UserCalendar, RSVP state — slot in without disturbing them.
Requirements
Functional
- Book a meeting with organizer, attendees, room, and duration
- Support one-time and recurring meetings (daily, weekly)
- Track per-attendee RSVP: PENDING, ACCEPTED, DECLINED
- Decline removes the instance from the attendee's calendar only
- Cancel a single occurrence or the entire series (organizer-only)
- Query per-user free/busy over a window
- Reject booking on room conflict or any participant conflict
Non-Functional
- O(log n) conflict check per room and per user
- Booking a series is atomic: either all occurrences reserve or none do
- Cancellation preserves history (flag, not delete)
- Thread-safe under concurrent booking and response
Design Decisions
Why Meeting (series) vs MeetingInstance (occurrence)?
A recurring meeting isn't one thing that happens many times — it's many things with a shared template. Modeling each occurrence as its own MeetingInstance lets "cancel just Tuesday" and "Dan declined only the first" be trivial state on the instance. Collapsing them into one meeting object forces ad-hoc exception lists everywhere.
Why per-user calendars?
If a declined meeting stays on the decliner's calendar, any future availability check for that user wrongly returns "busy." Per-user TreeMaps make DECLINED → remove from my calendar the single surgical change that fixes this. The room calendar is untouched — the organizer and accepted attendees still have the slot.
Why eager recurrence expansion?
A weekly meeting over a year generates 52 instances. Eagerly materializing them into the room and user calendars keeps conflict checks uniform — every future query hits the same O(log n) path. Lazy expansion is cleaner in theory but forces every query to consult the recurrence rule before it can answer. The eager approach is what commercial calendars (Google, Outlook) actually do past a short horizon.
Why does PENDING block the calendar?
An invitation a user hasn't responded to yet still holds the slot tentatively. If PENDING didn't block, a second meeting could schedule over it; the user accepts the first; now they're double-booked. Making PENDING behave like ACCEPTED until the user takes action matches how Google Calendar and Outlook work.
Why cancel-as-flag instead of delete?
A deleted meeting can't answer "when was it cancelled and by whom?" The flag + remove-from-calendars pattern preserves history while making sure the cancelled instance stops showing up in anyone's free/busy. Audit questions stay answerable.
Why organizer-only cancellation?
Otherwise any attendee can cancel for everyone. Only the organizer has the authority; attendees express "I'm not coming" through a DECLINE response. Enforcing this at the cancel path keeps the authorization in one place.
Interview Follow-ups
- "How would you support exceptions in a recurring series?" Store per-instance overrides. The
MeetingInstancealready has its ownstart/end/cancelled— extend it with anoverriddenStartso one Tuesday can shift to Wednesday without affecting the series. - "How would RRULE support fit?" Replace the hand-rolled
Recurrencehierarchy with an RRULE parser (RFC 5545). Thegenerate(start, seriesEnd)contract stays the same; the parser figures out "every second Tuesday except the 14th." - "How do you handle time zones?" Store everything in UTC. Each user has a display zone for their UI. Cross-zone attendee conflicts resolve naturally since UTC instants compare globally.
- "How does find-free-time-for-all-attendees work?" For each attendee, call
freeBusyover the window. Merge the busy intervals, invert to get each person's free intervals, intersect across everyone. Return the first intersection long enough to fit the meeting. - "What about lazy expansion for long-running series?" Keep the
Meetingwith itsRecurrence, but only materialize instances within a rolling window (e.g. next 180 days). A nightly job expands the next window. Cancellations and RSVPs on out-of-window instances are stored as pending overrides. - "How do you avoid distributed double-booking?" Row-level database locks per room for bookings, or optimistic concurrency with a
versioncolumn. The in-memoryReentrantLockonly covers a single process; production needs DB-level guarantees.
Code Implementation
1 from __future__ import annotations
2 from abc import ABC, abstractmethod
3 from dataclasses import dataclass, field
4 from datetime import datetime, timedelta
5 from enum import Enum
6 from threading import RLock
7 from typing import Callable
8 from sortedcontainers import SortedDict # pip install sortedcontainers
9 import uuid
10
11
12 class ResponseStatus(Enum):
13 PENDING = "pending"
14 ACCEPTED = "accepted"
15 DECLINED = "declined"
16
17
18 @dataclass
19 class MeetingInstance:
20 instance_id: str
21 meeting_id: str
22 start: datetime
23 end: datetime
24 responses: dict[str, ResponseStatus] = field(default_factory=dict)
25 cancelled: bool = False
26
27
28 # ---- Recurrence strategies ----
29
30 class Recurrence(ABC):
31 @abstractmethod
32 def generate(self, start: datetime, series_end: datetime) -> list[datetime]: ...
33
34 @property
35 def is_one_shot(self) -> bool:
36 return False
37
38
39 class OneShot(Recurrence):
40 def generate(self, start, series_end):
41 return [start]
42
43 @property
44 def is_one_shot(self):
45 return True
46
47
48 class DailyRecurrence(Recurrence):
49 def __init__(self, interval_days: int = 1):
50 if interval_days < 1:
51 raise ValueError("interval_days must be >= 1")
52 self._interval = timedelta(days=interval_days)
53
54 def generate(self, start, series_end):
55 out, current = [], start
56 while current <= series_end:
57 out.append(current)
58 current += self._interval
59 return out
60
61
62 class WeeklyRecurrence(Recurrence):
63 def __init__(self, weeks: int = 1):
64 if weeks < 1:
65 raise ValueError("weeks must be >= 1")
66 self._interval = timedelta(weeks=weeks)
67
68 def generate(self, start, series_end):
69 out, current = [], start
70 while current <= series_end:
71 out.append(current)
72 current += self._interval
73 return out
74
75
76 # ---- Room and user calendars: same TreeMap pattern, two key spaces ----
77
78 class Room:
79 """Bookings kept in a sorted map keyed by start. Cancellation removes entries so
80 is_free only ever sees live instances."""
81
82 def __init__(self, room_id: str, capacity: int, floor: int = 0):
83 self.id = room_id
84 self.capacity = capacity
85 self.floor = floor
86 self._bookings: SortedDict[datetime, MeetingInstance] = SortedDict()
87 self._lock = RLock()
88
89 def is_free(self, start: datetime, end: datetime) -> bool:
90 if end <= start:
91 raise ValueError("end must be after start")
92 with self._lock:
93 # Prior booking (if any) — only candidate that could spill into [start, end).
94 idx = self._bookings.bisect_right(start) - 1
95 if idx >= 0:
96 prior = self._bookings.peekitem(idx)[1]
97 if prior.end > start:
98 return False
99 # Next booking — overlaps if it starts before our end.
100 idx_next = self._bookings.bisect_left(start)
101 if idx_next < len(self._bookings):
102 nxt = self._bookings.peekitem(idx_next)[1]
103 if nxt.start < end:
104 return False
105 return True
106
107 def book(self, instance: MeetingInstance) -> None:
108 with self._lock:
109 if not self.is_free(instance.start, instance.end):
110 raise RuntimeError(f"Room {self.id} not free at {instance.start}")
111 self._bookings[instance.start] = instance
112
113 def remove(self, instance: MeetingInstance) -> None:
114 with self._lock:
115 self._bookings.pop(instance.start, None)
116
117
118 class UserCalendar:
119 """One per user. A declined instance is removed here so the user appears free for
120 overlapping invites. The room still shows that instance as booked."""
121
122 def __init__(self, user_id: str):
123 self.user_id = user_id
124 self._busy: SortedDict[datetime, MeetingInstance] = SortedDict()
125 self._lock = RLock()
126
127 def is_free(self, start: datetime, end: datetime) -> bool:
128 if end <= start:
129 raise ValueError("end must be after start")
130 with self._lock:
131 idx = self._busy.bisect_right(start) - 1
132 if idx >= 0:
133 prior = self._busy.peekitem(idx)[1]
134 if prior.end > start:
135 return False
136 idx_next = self._busy.bisect_left(start)
137 if idx_next < len(self._busy):
138 nxt = self._busy.peekitem(idx_next)[1]
139 if nxt.start < end:
140 return False
141 return True
142
143 def add(self, instance: MeetingInstance) -> None:
144 with self._lock:
145 if not self.is_free(instance.start, instance.end):
146 raise RuntimeError(f"User {self.user_id} busy at {instance.start}")
147 self._busy[instance.start] = instance
148
149 def remove_by_id(self, instance_id: str) -> bool:
150 with self._lock:
151 for key, inst in list(self._busy.items()):
152 if inst.instance_id == instance_id:
153 del self._busy[key]
154 return True
155 return False
156
157 def busy_intervals(self, window_start: datetime, window_end: datetime) -> list[tuple[datetime, datetime]]:
158 with self._lock:
159 out = []
160 for inst in self._busy.values():
161 if inst.start < window_end and window_start < inst.end:
162 out.append((inst.start, inst.end))
163 return out
164
165
166 # ---- Meeting (series) + request ----
167
168 @dataclass
169 class Meeting:
170 id: str
171 organizer: str
172 attendees: list[str]
173 room_id: str
174 recurrence: Recurrence
175 instances: dict[str, MeetingInstance] = field(default_factory=dict)
176
177
178 @dataclass
179 class BookingRequest:
180 organizer: str
181 attendees: list[str]
182 start: datetime
183 end: datetime
184 recurrence: Recurrence = field(default_factory=OneShot)
185 # For one-shot, series_end == start is fine. For recurring, caller supplies the cutoff.
186 series_end: datetime | None = None
187
188
189 # ---- Strategies ----
190
191 class RoomSelectionStrategy(ABC):
192 @abstractmethod
193 def pick_for_series(self, rooms: list[Room], starts: list[datetime],
194 duration: timedelta, attendees: int) -> Room | None: ...
195
196
197 class SmallestThatFits(RoomSelectionStrategy):
198 """Chooses the smallest room that has capacity and is free for every instance."""
199
200 def pick_for_series(self, rooms, starts, duration, attendees):
201 for room in sorted(rooms, key=lambda r: r.capacity):
202 if room.capacity < attendees:
203 continue
204 if all(room.is_free(s, s + duration) for s in starts):
205 return room
206 return None
207
208
209 # ---- Notifications ----
210
211 class NotificationBus:
212 def __init__(self):
213 self._subs: list[Callable[[str, object], None]] = []
214
215 def subscribe(self, handler: Callable[[str, object], None]) -> None:
216 self._subs.append(handler)
217
218 def publish(self, event: str, payload: object) -> None:
219 for h in self._subs:
220 h(event, payload)
221
222
223 # ---- Scheduler ----
224
225 class Scheduler:
226 def __init__(self, rooms: list[Room], strategy: RoomSelectionStrategy | None = None):
227 if not rooms:
228 raise ValueError("need at least one room")
229 self._rooms = rooms
230 self._strategy = strategy or SmallestThatFits()
231 self._bus = NotificationBus()
232 self._meetings: dict[str, Meeting] = {}
233 self._calendars: dict[str, UserCalendar] = {}
234 self._lock = RLock()
235
236 def subscribe(self, handler: Callable[[str, object], None]) -> None:
237 self._bus.subscribe(handler)
238
239 def _calendar(self, user_id: str) -> UserCalendar:
240 if user_id not in self._calendars:
241 self._calendars[user_id] = UserCalendar(user_id)
242 return self._calendars[user_id]
243
244 def book(self, req: BookingRequest) -> Meeting:
245 if req.end <= req.start:
246 raise ValueError("Meeting end must be after start")
247
248 recurrence = req.recurrence
249 series_end = req.series_end or req.start
250 if series_end < req.start:
251 raise ValueError("series_end must be >= start")
252
253 duration = req.end - req.start
254 starts = recurrence.generate(req.start, series_end)
255 if not starts:
256 raise ValueError("Recurrence produced no occurrences")
257
258 participants = [req.organizer] + list(req.attendees)
259
260 with self._lock:
261 room = self._strategy.pick_for_series(self._rooms, starts, duration, len(participants))
262 if room is None:
263 raise RuntimeError("No room available for the entire series")
264
265 # Up-front conflict check across every instance and every participant.
266 for s in starts:
267 e = s + duration
268 for uid in participants:
269 if not self._calendar(uid).is_free(s, e):
270 raise RuntimeError(f"User {uid} is busy at {s}")
271
272 meeting_id = str(uuid.uuid4())[:8]
273 instances: dict[str, MeetingInstance] = {}
274 for i, s in enumerate(starts, 1):
275 e = s + duration
276 responses = {
277 u: ResponseStatus.ACCEPTED if u == req.organizer else ResponseStatus.PENDING
278 for u in participants
279 }
280 inst = MeetingInstance(
281 instance_id=f"{meeting_id}-{i}",
282 meeting_id=meeting_id,
283 start=s, end=e,
284 responses=responses,
285 )
286 instances[inst.instance_id] = inst
287 room.book(inst)
288 # PENDING blocks the calendar — tentative holds the slot until declined.
289 for uid in participants:
290 self._calendar(uid).add(inst)
291
292 meeting = Meeting(
293 id=meeting_id,
294 organizer=req.organizer,
295 attendees=list(req.attendees),
296 room_id=room.id,
297 recurrence=recurrence,
298 instances=instances,
299 )
300 self._meetings[meeting_id] = meeting
301 self._bus.publish("booked", meeting)
302 return meeting
303
304 def respond(self, user_id: str, instance_id: str, status: ResponseStatus) -> None:
305 meeting, inst = self._find_instance(instance_id)
306 if meeting is None:
307 raise ValueError("Unknown instance")
308 if inst.cancelled:
309 raise RuntimeError("Cannot respond to a cancelled instance")
310 if user_id not in inst.responses:
311 raise PermissionError("User is not an attendee of this meeting")
312
313 prior = inst.responses[user_id]
314 if prior == status:
315 return
316
317 if status == ResponseStatus.DECLINED:
318 # Free the user's calendar. Room stays booked; organizer still has the slot.
319 self._calendar(user_id).remove_by_id(instance_id)
320 elif prior == ResponseStatus.DECLINED:
321 # Re-accepting (or going back to pending) — verify the user isn't double-booked.
322 try:
323 self._calendar(user_id).add(inst)
324 except RuntimeError:
325 raise RuntimeError(
326 f"Cannot change response: user {user_id} now has a conflicting meeting"
327 )
328
329 inst.responses[user_id] = status
330 self._bus.publish("response", {"user": user_id, "instance": instance_id, "status": status.value})
331
332 def cancel_instance(self, instance_id: str, actor: str) -> None:
333 meeting, inst = self._find_instance(instance_id)
334 if meeting is None:
335 raise ValueError("Unknown instance")
336 if actor != meeting.organizer:
337 raise PermissionError("Only the organizer can cancel")
338 if inst.cancelled:
339 return
340 inst.cancelled = True
341 self._release_instance(meeting, inst)
342 self._bus.publish("instance_cancelled", inst)
343
344 def cancel_series(self, meeting_id: str, actor: str) -> None:
345 meeting = self._meetings.get(meeting_id)
346 if meeting is None:
347 raise ValueError("Unknown meeting")
348 if actor != meeting.organizer:
349 raise PermissionError("Only the organizer can cancel")
350 for inst in meeting.instances.values():
351 if not inst.cancelled:
352 inst.cancelled = True
353 self._release_instance(meeting, inst)
354 self._bus.publish("series_cancelled", meeting)
355
356 def _release_instance(self, meeting: Meeting, inst: MeetingInstance) -> None:
357 room = next(r for r in self._rooms if r.id == meeting.room_id)
358 room.remove(inst)
359 for uid in inst.responses:
360 self._calendar(uid).remove_by_id(inst.instance_id)
361
362 def _find_instance(self, instance_id: str):
363 for m in self._meetings.values():
364 inst = m.instances.get(instance_id)
365 if inst is not None:
366 return m, inst
367 return None, None
368
369 def free_busy(self, user_id: str, start: datetime, end: datetime) -> list[tuple[datetime, datetime]]:
370 return self._calendar(user_id).busy_intervals(start, end)
371
372
373 if __name__ == "__main__":
374 rooms = [
375 Room("R-small", capacity=4, floor=1),
376 Room("R-medium", capacity=8, floor=2),
377 Room("R-board", capacity=20, floor=3),
378 ]
379 sched = Scheduler(rooms)
380 sched.subscribe(lambda ev, payload: print(f"[notify] {ev}"))
381
382 base = datetime(2026, 4, 14, 10, 0)
383
384 # 1. One-time meeting.
385 m1 = sched.book(BookingRequest("alice", ["bob"], base, base + timedelta(hours=1)))
386 print(f"One-time booked {m1.id} in {m1.room_id} ({len(m1.instances)} instance)")
387
388 # 2. Back-to-back is allowed (half-open intervals).
389 m2 = sched.book(BookingRequest("alice", ["bob"], base + timedelta(hours=1), base + timedelta(hours=2)))
390 print(f"Back-to-back in same room: {m1.room_id == m2.room_id}")
391
392 # 3. Overlap for a participant is rejected.
393 try:
394 sched.book(BookingRequest("alice", ["bob"],
395 base + timedelta(minutes=30), base + timedelta(hours=1, minutes=30)))
396 except RuntimeError as e:
397 print(f"Overlap rejected: {e}")
398
399 # 4. Weekly recurring, 3 occurrences (Mon 5/4, 5/11, 5/18).
400 rec = sched.book(BookingRequest(
401 organizer="carol",
402 attendees=["dan", "eve"],
403 start=datetime(2026, 5, 4, 14, 0),
404 end=datetime(2026, 5, 4, 15, 0),
405 recurrence=WeeklyRecurrence(1),
406 series_end=datetime(2026, 5, 18, 14, 0),
407 ))
408 print(f"Recurring booked {rec.id}: {len(rec.instances)} instances")
409
410 # 5. Dan declines the first occurrence — only his calendar frees up.
411 month_start = datetime(2026, 5, 1)
412 month_end = datetime(2026, 5, 31)
413 first_id = next(iter(rec.instances.keys()))
414 print(f"Before decline dan busy={len(sched.free_busy('dan', month_start, month_end))} "
415 f"eve busy={len(sched.free_busy('eve', month_start, month_end))}")
416 sched.respond("dan", first_id, ResponseStatus.DECLINED)
417 print(f"After decline dan busy={len(sched.free_busy('dan', month_start, month_end))} "
418 f"eve busy={len(sched.free_busy('eve', month_start, month_end))}")
419 assert len(sched.free_busy("dan", month_start, month_end)) == 2
420 assert len(sched.free_busy("eve", month_start, month_end)) == 3
421
422 # 6. Dan re-accepts — slot returns (provided he hasn't double-booked meanwhile).
423 sched.respond("dan", first_id, ResponseStatus.ACCEPTED)
424 print(f"After re-accept dan busy={len(sched.free_busy('dan', month_start, month_end))}")
425 assert len(sched.free_busy("dan", month_start, month_end)) == 3
426
427 # 7. Cancel just the second instance. Dan and Eve lose only that slot.
428 second_id = list(rec.instances.keys())[1]
429 sched.cancel_instance(second_id, actor="carol")
430 print(f"After cancel_instance dan busy={len(sched.free_busy('dan', month_start, month_end))} "
431 f"eve busy={len(sched.free_busy('eve', month_start, month_end))}")
432 assert rec.instances[second_id].cancelled
433 assert sum(1 for i in rec.instances.values() if not i.cancelled) == 2
434
435 # 8. Non-organizer cannot cancel.
436 try:
437 sched.cancel_series(rec.id, actor="dan")
438 except PermissionError as e:
439 print(f"Non-organizer cancel rejected: {e}")
440
441 # 9. Cancel the remaining series.
442 sched.cancel_series(rec.id, actor="carol")
443 print(f"After cancel_series dan busy={len(sched.free_busy('dan', month_start, month_end))} "
444 f"eve busy={len(sched.free_busy('eve', month_start, month_end))}")
445 assert all(i.cancelled for i in rec.instances.values())
446 assert len(sched.free_busy("dan", month_start, month_end)) == 0
447 print("All assertions passed.")Common Mistakes
- ✗Treating a meeting as a single row. A weekly series with one cancelled Tuesday becomes impossible to represent.
- ✗Keeping a declined attendee's slot on their calendar. Future availability queries return a wrong answer.
- ✗Deleting cancelled meetings. Audit trail is gone and 'who cancelled what' questions can't be answered.
- ✗Closed intervals [a, b]. A 10:00-11:00 meeting conflicts with an 11:00-12:00 meeting for no reason.
- ✗Linear scan of all bookings. Fine at ten meetings, broken at ten thousand.
- ✗Checking the room but not individual attendees. The room is free; Bob is double-booked; nobody notices until the meeting starts.
- ✗Letting anyone cancel. Authorization belongs on the cancel path — only the organizer.
Key Points
- ✓Meeting is the series; MeetingInstance is the occurrence. Cancelling Tuesday in a weekly series is a one-instance operation.
- ✓Each user has their own TreeMap calendar. Room conflict and user conflict are two separate O(log n) checks.
- ✓RSVP is per-instance. DECLINED removes the instance from that user's calendar only — others still see it and the room stays booked.
- ✓Half-open intervals [start, end). Back-to-back meetings don't conflict.
- ✓Booking atomically checks every instance against the room and every participant's calendar — either all reserve or none do.
- ✓Only the organizer may cancel, and cancellation flags the instance (preserves history) while removing it from every calendar.