Meeting Room Scheduler

medium · interval overlap, greedy room choice

Brief-reported interview attribution (unverified): Google, Amazon, Meta

How to approach an LLD round

Requirements

  • 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 fits

Rules. 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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

4 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. AntyCharacter joke · No posting date

    This problem has 8 hidden tests. I found 9 ways to fail them.

  2. The GraderCharacter joke · No posting date

    Edge case? Never met her.

  3. InterviewerCharacter joke · No posting date

    Walk me through your thinking. No, not out loud. In code. In silence. While I watch.

  4. Me at 2amCharacter joke · No posting date

    My code works. I have no idea why. I am afraid to touch it. I am going to bed.