How to Solve an LLD Interview

package main

import (
	"errors"
	"fmt"
)

// Entities from the requirements: Room, Booking, and the Scheduler that owns the rules.

type Room struct {
	Name     string
	Capacity int
}

// Booking holds a half-open time range [Start, End) in whole hours.
type Booking struct {
	Room       *Room
	Start, End int
	Who        string
}

func (b Booking) Overlaps(start, end int) bool { return b.Start < end && start < b.End }

var (
	ErrNoRoomFits = errors.New("no room for that many people")
	ErrAllBusy    = errors.New("all rooms that fit are busy")
	ErrBadTime    = errors.New("end must be after start")
)

type Scheduler struct {
	rooms    []*Room // kept smallest first, so the first free fit is the best fit
	bookings []Booking
}

func (s *Scheduler) free(r *Room, start, end int) bool {
	for _, b := range s.bookings {
		if b.Room == r && b.Overlaps(start, end) {
			return false
		}
	}
	return true
}

// Book picks the smallest free room that fits. One method owns the whole rule.
func (s *Scheduler) Book(people, start, end int, who string) (*Room, error) {
	if end <= start {
		return nil, ErrBadTime
	}
	fits := false
	for _, r := range s.rooms {
		if r.Capacity < people {
			continue
		}
		fits = true
		if s.free(r, start, end) {
			s.bookings = append(s.bookings, Booking{r, start, end, who})
			return r, nil
		}
	}
	if !fits {
		return nil, ErrNoRoomFits
	}
	return nil, ErrAllBusy
}

func (s *Scheduler) Cancel(who string, start int) bool {
	for i, b := range s.bookings {
		if b.Who == who && b.Start == start {
			s.bookings = append(s.bookings[:i], s.bookings[i+1:]...)
			return true
		}
	}
	return false
}

func main() {
	s := &Scheduler{rooms: []*Room{{"Jamuna", 2}, {"Padma", 6}, {"Meghna", 10}}}

	try := func(people, start, end int, who string) {
		label := fmt.Sprintf("book %2d people %d-%d %-6s", people, start, end, who)
		if r, err := s.Book(people, start, end, who); err != nil {
			fmt.Printf("%s -> refused: %v\n", label, err)
		} else {
			fmt.Printf("%s -> %s (%d seats)\n", label, r.Name, r.Capacity)
		}
	}
	try(4, 10, 11, "Nadia")
	try(4, 10, 11, "Rahim")
	try(12, 10, 11, "Tania")
	try(4, 10, 11, "Sabbir")
	try(4, 11, 12, "Sabbir")
	try(2, 12, 11, "Karim")
	if s.Cancel("Nadia", 10) {
		fmt.Printf("%-27s -> Padma is free again\n", "cancel Nadia 10-11")
	}
	try(3, 10, 11, "Karim")
}

from __future__ import annotations

from dataclasses import dataclass

# Entities from the requirements: Room, Booking, and the Scheduler that owns the rules.


@dataclass(frozen=True)
class Room:
    name: str
    capacity: int


@dataclass(frozen=True)
class Booking:
    """A half-open time range [start, end) in whole hours."""
    room: Room
    start: int
    end: int
    who: str

    def overlaps(self, start: int, end: int) -> bool:
        return self.start < end and start < self.end


class BookingError(Exception):
    pass


class Scheduler:
    def __init__(self, rooms: list[Room]):
        self.rooms = sorted(rooms, key=lambda r: r.capacity)  # smallest first: first free fit is best
        self.bookings: list[Booking] = []

    def _free(self, room: Room, start: int, end: int) -> bool:
        return not any(b.room == room and b.overlaps(start, end) for b in self.bookings)

    def book(self, people: int, start: int, end: int, who: str) -> Room:
        """Picks the smallest free room that fits. One method owns the whole rule."""
        if end <= start:
            raise BookingError("end must be after start")
        fitting = [r for r in self.rooms if r.capacity >= people]
        if not fitting:
            raise BookingError("no room for that many people")
        for room in fitting:
            if self._free(room, start, end):
                self.bookings.append(Booking(room, start, end, who))
                return room
        raise BookingError("all rooms that fit are busy")

    def cancel(self, who: str, start: int) -> bool:
        for b in self.bookings:
            if b.who == who and b.start == start:
                self.bookings.remove(b)
                return True
        return False


s = Scheduler([Room("Jamuna", 2), Room("Padma", 6), Room("Meghna", 10)])


def attempt(people: int, start: int, end: int, who: str) -> None:
    label = f"book {people:2d} people {start}-{end} {who:<6}"
    try:
        r = s.book(people, start, end, who)
        print(f"{label} -> {r.name} ({r.capacity} seats)")
    except BookingError as e:
        print(f"{label} -> refused: {e}")


attempt(4, 10, 11, "Nadia")
attempt(4, 10, 11, "Rahim")
attempt(12, 10, 11, "Tania")
attempt(4, 10, 11, "Sabbir")
attempt(4, 11, 12, "Sabbir")
attempt(2, 12, 11, "Karim")
if s.cancel("Nadia", 10):
    print(f"{'cancel Nadia 10-11':<27} -> Padma is free again")
attempt(3, 10, 11, "Karim")

// Entities from the requirements: Room, Booking, and the Scheduler that owns the rules.

interface Room {
  readonly name: string;
  readonly capacity: number;
}

// A half-open time range [start, end) in whole hours.
interface Booking {
  readonly room: Room;
  readonly start: number;
  readonly end: number;
  readonly who: string;
}

const overlaps = (b: Booking, start: number, end: number) => b.start < end && start < b.end;

class Scheduler {
  readonly rooms: Room[];
  bookings: Booking[] = [];
  constructor(rooms: Room[]) {
    this.rooms = [...rooms].sort((a, b) => a.capacity - b.capacity); // smallest first: first free fit is best
  }
  private free(room: Room, start: number, end: number): boolean {
    return !this.bookings.some((b) => b.room === room && overlaps(b, start, end));
  }
  // Picks the smallest free room that fits. One method owns the whole rule.
  book(people: number, start: number, end: number, who: string): Room {
    if (end <= start) throw new Error("end must be after start");
    const fitting = this.rooms.filter((r) => r.capacity >= people);
    if (fitting.length === 0) throw new Error("no room for that many people");
    const room = fitting.find((r) => this.free(r, start, end));
    if (!room) throw new Error("all rooms that fit are busy");
    this.bookings.push({ room, start, end, who });
    return room;
  }
  cancel(who: string, start: number): boolean {
    const i = this.bookings.findIndex((b) => b.who === who && b.start === start);
    if (i < 0) return false;
    this.bookings.splice(i, 1);
    return true;
  }
}

const s = new Scheduler([
  { name: "Jamuna", capacity: 2 },
  { name: "Padma", capacity: 6 },
  { name: "Meghna", capacity: 10 },
]);

function attempt(people: number, start: number, end: number, who: string): void {
  const label = `book ${String(people).padStart(2)} people ${start}-${end} ${who.padEnd(6)}`;
  try {
    const r = s.book(people, start, end, who);
    console.log(`${label} -> ${r.name} (${r.capacity} seats)`);
  } catch (e) {
    console.log(`${label} -> refused: ${(e as Error).message}`);
  }
}

attempt(4, 10, 11, "Nadia");
attempt(4, 10, 11, "Rahim");
attempt(12, 10, 11, "Tania");
attempt(4, 10, 11, "Sabbir");
attempt(4, 11, 12, "Sabbir");
attempt(2, 12, 11, "Karim");
if (s.cancel("Nadia", 10)) console.log(`${"cancel Nadia 10-11".padEnd(27)} -> Padma is free again`);
attempt(3, 10, 11, "Karim");

// Entities from the requirements: Room, Booking, and the Scheduler that owns the rules.

struct Room { name: &'static str, capacity: u32 }

// A half-open time range [start, end) in whole hours. `room` is an index into Scheduler.rooms.
struct Booking { room: usize, start: u32, end: u32, who: String }

impl Booking {
    fn overlaps(&self, start: u32, end: u32) -> bool { self.start < end && start < self.end }
}

struct Scheduler { rooms: Vec<Room>, bookings: Vec<Booking> } // rooms kept smallest first

impl Scheduler {
    fn free(&self, room: usize, start: u32, end: u32) -> bool {
        !self.bookings.iter().any(|b| b.room == room && b.overlaps(start, end))
    }

    // Picks the smallest free room that fits. One method owns the whole rule.
    fn book(&mut self, people: u32, start: u32, end: u32, who: &str) -> Result<&Room, &'static str> {
        if end <= start { return Err("end must be after start"); }
        let fitting: Vec<usize> = (0..self.rooms.len()).filter(|&i| self.rooms[i].capacity >= people).collect();
        if fitting.is_empty() { return Err("no room for that many people"); }
        let room = fitting.into_iter().find(|&i| self.free(i, start, end)).ok_or("all rooms that fit are busy")?;
        self.bookings.push(Booking { room, start, end, who: who.to_string() });
        Ok(&self.rooms[room])
    }

    fn cancel(&mut self, who: &str, start: u32) -> bool {
        match self.bookings.iter().position(|b| b.who == who && b.start == start) {
            Some(i) => { self.bookings.remove(i); true }
            None => false,
        }
    }
}

fn main() {
    let mut s = Scheduler {
        rooms: vec![Room { name: "Jamuna", capacity: 2 }, Room { name: "Padma", capacity: 6 }, Room { name: "Meghna", capacity: 10 }],
        bookings: vec![],
    };
    let attempt = |s: &mut Scheduler, people: u32, start: u32, end: u32, who: &str| {
        let label = format!("book {people:2} people {start}-{end} {who:<6}");
        match s.book(people, start, end, who) {
            Ok(r) => println!("{label} -> {} ({} seats)", r.name, r.capacity),
            Err(e) => println!("{label} -> refused: {e}"),
        }
    };
    attempt(&mut s, 4, 10, 11, "Nadia");
    attempt(&mut s, 4, 10, 11, "Rahim");
    attempt(&mut s, 12, 10, 11, "Tania");
    attempt(&mut s, 4, 10, 11, "Sabbir");
    attempt(&mut s, 4, 11, 12, "Sabbir");
    attempt(&mut s, 2, 12, 11, "Karim");
    if s.cancel("Nadia", 10) { println!("{:<27} -> Padma is free again", "cancel Nadia 10-11"); }
    attempt(&mut s, 3, 10, 11, "Karim");
}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
    // Entities from the requirements: Room, Booking, and the Scheduler that owns the rules.

    record Room(String name, int capacity) {}

    // A half-open time range [start, end) in whole hours.
    record Booking(Room room, int start, int end, String who) {
        boolean overlaps(int s, int e) { return start < e && s < end; }
    }

    static final class BookingException extends Exception {
        private static final long serialVersionUID = 1L;
        BookingException(String msg) { super(msg); }
    }

    static final class Scheduler {
        private final List<Room> rooms;
        private final List<Booking> bookings = new ArrayList<>();

        Scheduler(List<Room> rooms) {
            this.rooms = rooms.stream().sorted(Comparator.comparingInt(Room::capacity)).toList(); // smallest first
        }

        private boolean free(Room r, int start, int end) {
            return bookings.stream().noneMatch(b -> b.room().equals(r) && b.overlaps(start, end));
        }

        // Picks the smallest free room that fits. One method owns the whole rule.
        Room book(int people, int start, int end, String who) throws BookingException {
            if (end <= start) throw new BookingException("end must be after start");
            List<Room> fitting = rooms.stream().filter(r -> r.capacity() >= people).toList();
            if (fitting.isEmpty()) throw new BookingException("no room for that many people");
            for (Room r : fitting) {
                if (free(r, start, end)) {
                    bookings.add(new Booking(r, start, end, who));
                    return r;
                }
            }
            throw new BookingException("all rooms that fit are busy");
        }

        boolean cancel(String who, int start) {
            return bookings.removeIf(b -> b.who().equals(who) && b.start() == start);
        }
    }

    static Scheduler s = new Scheduler(List.of(new Room("Jamuna", 2), new Room("Padma", 6), new Room("Meghna", 10)));

    static void attempt(int people, int start, int end, String who) {
        String label = String.format("book %2d people %d-%d %-6s", people, start, end, who);
        try {
            Room r = s.book(people, start, end, who);
            System.out.printf("%s -> %s (%d seats)%n", label, r.name(), r.capacity());
        } catch (BookingException e) {
            System.out.printf("%s -> refused: %s%n", label, e.getMessage());
        }
    }

    public static void main(String[] args) {
        attempt(4, 10, 11, "Nadia");
        attempt(4, 10, 11, "Rahim");
        attempt(12, 10, 11, "Tania");
        attempt(4, 10, 11, "Sabbir");
        attempt(4, 11, 12, "Sabbir");
        attempt(2, 12, 11, "Karim");
        if (s.cancel("Nadia", 10)) System.out.printf("%-27s -> Padma is free again%n", "cancel Nadia 10-11");
        attempt(3, 10, 11, "Karim");
    }
}

#include <algorithm>
#include <cstdio>
#include <stdexcept>
#include <string>
#include <vector>

// Entities from the requirements: Room, Booking, and the Scheduler that owns the rules.

struct Room {
    std::string name;
    int capacity;
};

// A half-open time range [start, end) in whole hours. `room` indexes Scheduler::rooms_.
struct Booking {
    size_t room;
    int start, end;
    std::string who;
    bool overlaps(int s, int e) const { return start < e && s < end; }
};

struct BookingError : std::runtime_error {
    using std::runtime_error::runtime_error;
};

class Scheduler {
public:
    explicit Scheduler(std::vector<Room> rooms) : rooms_(std::move(rooms)) {
        std::sort(rooms_.begin(), rooms_.end(), [](const Room& a, const Room& b) { return a.capacity < b.capacity; });
    }

    // Picks the smallest free room that fits. One method owns the whole rule.
    const Room& book(int people, int start, int end, const std::string& who) {
        if (end <= start) throw BookingError("end must be after start");
        bool fits = false;
        for (size_t i = 0; i < rooms_.size(); i++) {
            if (rooms_[i].capacity < people) continue;
            fits = true;
            if (free(i, start, end)) {
                bookings_.push_back({i, start, end, who});
                return rooms_[i];
            }
        }
        throw BookingError(fits ? "all rooms that fit are busy" : "no room for that many people");
    }

    bool cancel(const std::string& who, int start) {
        auto it = std::find_if(bookings_.begin(), bookings_.end(),
                               [&](const Booking& b) { return b.who == who && b.start == start; });
        if (it == bookings_.end()) return false;
        bookings_.erase(it);
        return true;
    }

private:
    bool free(size_t room, int start, int end) const {
        return std::none_of(bookings_.begin(), bookings_.end(),
                            [&](const Booking& b) { return b.room == room && b.overlaps(start, end); });
    }
    std::vector<Room> rooms_;  // smallest first: the first free fit is the best fit
    std::vector<Booking> bookings_;
};

int main() {
    Scheduler s({{"Jamuna", 2}, {"Padma", 6}, {"Meghna", 10}});
    auto attempt = [&](int people, int start, int end, const std::string& who) {
        char label[64];
        std::snprintf(label, sizeof label, "book %2d people %d-%d %-6s", people, start, end, who.c_str());
        try {
            const Room& r = s.book(people, start, end, who);
            std::printf("%s -> %s (%d seats)\n", label, r.name.c_str(), r.capacity);
        } catch (const BookingError& e) {
            std::printf("%s -> refused: %s\n", label, e.what());
        }
    };
    attempt(4, 10, 11, "Nadia");
    attempt(4, 10, 11, "Rahim");
    attempt(12, 10, 11, "Tania");
    attempt(4, 10, 11, "Sabbir");
    attempt(4, 11, 12, "Sabbir");
    attempt(2, 12, 11, "Karim");
    if (s.cancel("Nadia", 10)) std::printf("%-27s -> Padma is free again\n", "cancel Nadia 10-11");
    attempt(3, 10, 11, "Karim");
}