Meeting Room Scheduler
medium · interval overlap, greedy room choice
Brief-reported interview attribution (unverified): Google, Amazon, Meta
How to approach an LLD roundRequirements
- Functional: add rooms, book a half-open interval (back-to-back allowed), cancel, list a room's bookings sorted by start, find the smallest free room that fits a capacity.
- Non-functional: overlapping bookings in the same room are rejected; the overlap rule and the room choice must be separate from the booking store.
- Out of scope: recurring meetings, attendees, notifications.
Statement
Design a meeting room scheduler. Rooms have capacities. A booking
is a half-open interval [start, end) in integer minutes: back-to-back meetings
(end == next start) are allowed, overlapping ones are not. find_room returns
the smallest room (by capacity) that is free for the interval and big enough;
ties break to the lowest room id.
class MeetingRoomScheduler:
def __init__(self):
def add_room(self, room_id, capacity):
def book(self, room_id, start, end, title):
# -> booking id (int, starting at 1), or None if the room is unknown,
# start >= end, or the interval overlaps an existing booking in that room
def cancel(self, booking_id):
# -> True if the booking existed, False otherwise
def bookings(self, room_id):
# -> [{"booking_id":, "start":, "end":, "title":}, ...] sorted by start
def find_room(self, start, end, min_capacity):
# -> room id, or None if no room fitsRules. Overlap is start < existing_end and existing_start < end (half-open).
Booking ids start at 1 and increase. bookings returns entries sorted by start.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
Room (capacity + its bookings + the free check; SRP). Booking (room, time, title; SRP). MeetingRoomScheduler orchestrates and finds the smallest sufficient free room. No pattern is forced; the split (room vs booking vs scheduler) is the point.
Public demo
# Public demo: run after implementing the class API above.
m = MeetingRoomScheduler()
m.add_room('A', 4)
m.add_room('B', 10)
m.add_room('C', 6)
print(m.book('A', 60, 120, 'Standup'))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
Two people booking the same room and time must not both succeed: the overlap check and the insert must be atomic — one lock per room (or per scheduler) around book/cancel. The reference is single-threaded; the lock is described here.
Trade-offs & extensions
Overlap is checked by scanning a room's bookings (fine for a few bookings per room). Extending: an interval tree per room for many bookings, and a Recurrence rule for repeating meetings.
Starter code
class Room:
def __init__(self, room_id, capacity):
"""Initialize the state described in the problem."""
pass
def is_free(self, start, end):
"""Implement the return value and rules in the API contract."""
pass
def add_booking(self, booking):
"""Implement the return value and rules in the API contract."""
pass
def remove_booking(self, booking):
"""Implement the return value and rules in the API contract."""
pass
class Booking:
def __init__(self, booking_id, room, start, end, title):
"""Initialize the state described in the problem."""
pass
def view(self):
"""Implement the return value and rules in the API contract."""
pass
class MeetingRoomScheduler:
def __init__(self):
"""Initialize the state described in the problem."""
pass
def add_room(self, room_id, capacity):
"""Implement the return value and rules in the API contract."""
pass
def book(self, room_id, start, end, title):
"""-> booking id (int, starting at 1), or None if the room is unknown, start >= end, or the interval overlaps an existing booking in that room"""
pass
def cancel(self, booking_id):
"""-> True if the booking existed, False otherwise"""
pass
def bookings(self, room_id):
"""-> [{"booking_id":, "start":, "end":, "title":}, ...] sorted by start"""
pass
def find_room(self, start, end, min_capacity):
"""-> room id, or None if no room fits"""
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter