[Uber] Design 🏢(LLD) Meeting Scheduler - Machine Coding Interview

We are designing a meeting scheduler with the following requirements:

1. There are N rooms.

2. We are given a stream of meeting requests (start time, end time, capacity).

3. We have to assign a room to the meeting if available, considering:

   • The room must be free during the requested time.

   • The room must have at least the required capacity.

4. We must minimize spillage of free time (i.e., use the room that has the least free time that can accommodate the meeting).

5. We have to store audit logs for each room (when a meeting is scheduled, etc.) and delete audit logs after X days.

Additional considerations:

• Concurrency: multiple requests may come in simultaneously.

Solution/Approaches

Core LLD Components

1. Room Management

   1.  public class Room {
           private final String roomId;
           private final int capacity;
           private final NavigableMap<LocalDateTime, Interval> bookings; // TreeMap for sorted intervals
           private final ReentrantReadWriteLock rwLock;
           
           public Room(String roomId, int capacity) {
               this.roomId = roomId;
               this.capacity = capacity;
               this.bookings = new TreeMap<>();
               this.rwLock = new ReentrantReadWriteLock(true); // Fair lock
           }
           
           public boolean isAvailable(Interval requested) {
               rwLock.readLock().lock();
               try {
                   // Check using interval tree or binary search
                   Entry<LocalDateTime, Interval> floor = bookings.floorEntry(requested.getStart());
                   Entry<LocalDateTime, Interval> ceiling = bookings.ceilingEntry(requested.getStart());
                   
                   return !conflictsWith(floor, requested) && !conflictsWith(ceiling, requested);
               } finally {
                   rwLock.readLock().unlock();
               }
           }
           
           private boolean conflictsWith(Entry<LocalDateTime, Interval> existing, Interval requested) {
               return existing != null && existing.getValue().overlaps(requested);
           }
       }
      

2. Interval Management

   1.  public class Interval implements Comparable<Interval> {
           private final LocalDateTime start;
           private final LocalDateTime end;
           
           public boolean overlaps(Interval other) {
               return !(this.end.isBefore(other.start) || this.start.isAfter(other.end));
           }
           
           // Calculate spillage when this interval is inserted into existing intervals
           public Duration calculateSpillage(List<Interval> existingIntervals) {
               List<Interval> merged = new ArrayList<>(existingIntervals);
               merged.add(this);
               Collections.sort(merged);
               
               Duration spillage = Duration.ZERO;
               for (int i = 0; i < merged.size() - 1; i++) {
                   Duration gap = Duration.between(merged.get(i).getEnd(), merged.get(i + 1).getStart());
                   if (!gap.isNegative() && !gap.isZero()) {
                       spillage = spillage.plus(gap);
                   }
               }
               return spillage;
           }
       }
      

3. Meeting Scheduler Core

   1.  public class MeetingScheduler {
           private final List<Room> rooms;
           private final Map<String, Room> roomMap;
           private final AuditLogger auditLogger;
           private final SpillageOptimizer spillageOptimizer;
           
           // Different scheduling strategies
           public enum SchedulingStrategy {
               MIN_SPILLAGE,
               BEST_FIT_CAPACITY,
               ROUND_ROBIN,
               LEAST_UTILIZED
           }
           
           public Optional<String> scheduleMeeting(MeetingRequest request) {
               List<CandidateRoom> candidates = findCandidateRooms(request);
               
               if (candidates.isEmpty()) {
                   return Optional.empty();
               }
               
               // Apply optimization strategy
               CandidateRoom selected = spillageOptimizer.selectRoom(candidates, request);
               
               // Attempt to book with optimistic locking
               return attemptBookingWithRetry(selected, request);
           }
           
           private List<CandidateRoom> findCandidateRooms(MeetingRequest request) {
               List<CandidateRoom> candidates = new ArrayList<>();
               
               for (Room room : rooms) {
                   if (room.getCapacity() >= request.getCapacity()) {
                       if (room.isAvailable(request.getInterval())) {
                           double spillage = calculateSpillageForRoom(room, request);
                           candidates.add(new CandidateRoom(room, spillage));
                       }
                   }
               }
               return candidates;
           }
       }
      

**

Gaps / issues in design**

1. Too much logic in MeetingScheduler

   • findCandidateRooms is doing filtering + availability + spillage calculation.

   • Could be moved into:

     • RoomSelector / CandidateFinder, or

     • At least a separate component responsible for candidate discovery.

2. Enum SchedulingStrategy not wired in

   • Enum is declared but not used in scheduleMeeting; ideally SpillageOptimizer should be a family of strategies.

   • Better: Map<SchedulingStrategy, SchedulingStrategyHandler> or StrategyFactory.

3. Data structure for rooms

   • Assumes a simple List<Room> scan.

   • For big systems, would need:

     • Indexing by capacity,

     • Indexing by building / floor / equipment,

     • Sharding across nodes.

Concurrency issues in this design

Assume multiple threads calling scheduleMeeting simultaneously.

a) Check-then-act race on availability

Problem area:

if (room.isAvailable(request.getInterval())) {
    double spillage = calculateSpillageForRoom(room, request);
    candidates.add(new CandidateRoom(room, spillage));
}

Then later:

return attemptBookingWithRetry(selected, request);

Between isAvailable() and the actual booking:

• Another thread might book the same room for overlapping interval.

• Both threads saw available == true → double booking risk.

b) Non-thread-safe data structures

• List<Room> rooms;

• Map<String, Room> roomMap;

If rooms can be added/removed at runtime:

• Concurrent modification without synchronization → ConcurrentModificationException or stale views.

Even if the list itself is not mutated, Room internals (its schedule) are mutable and accessed from multiple threads → must be made thread-safe.

c) Lost updates on room schedule

Room schedule is some structure (e.g., List<Booking>) inside Room.

• If two threads call room.addBooking(...) simultaneously without proper synchronization:

  • The underlying list / tree can be corrupted or some booking updates can be lost.

d) Thundering herd around popular time slots

If many users try to book for the same popular time:

• Lots of threads will compute candidates, all select the same “best” room, and then race to book it.

• Without control, this causes many retries/failures.

Concurrency control patterns to use