← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
Design and implement a conference room booking system that manages multiple rooms and their reservations. The system should handle booking requests, check for scheduling conflicts, cancel existing bookings, and help users find available rooms for specific time slots.
Your system needs to track which rooms are booked during which time periods, prevent double-booking of the same room, and provide functionality to query room availability.
Example 1: Basic Booking Flow
System: Create booking system System.add_room("Room-A", capacity=10) System.book_room("Room-A", 900, 1100) → "booking-1" System.check_availability("Room-A", 1000, 1200) → False (conflict with 900-1100) System.check_availability("Room-A", 1100, 1300) → True (no conflict)
Example 2: Multiple Rooms
System.add_room("Room-A", capacity=10) System.add_room("Room-B", capacity=8) System.book_room("Room-A", 900, 1100) → "booking-1" System.find_available_rooms(1000, 1200) → ["Room-B"] Explanation: Room-A is occupied 900-1100, which overlaps with 1000-1200
Example 3: Cancellation
booking_id = System.book_room("Room-A", 1400, 1600) → "booking-2" System.check_availability("Room-A", 1500, 1700) → False System.cancel_booking("booking-2") → True System.check_availability("Room-A", 1500, 1700) → True
Hint 1: Data Structure for Bookings For each room, maintain a list or sorted structure of bookings. When checking availability, you need to verify that the requested time slot doesn't overlap with any existing booking. Consider sorting bookings by start time to make conflict detection more efficient.
Hint 2: Overlap Detection Two time intervals [start1, end1) and [start2, end2) overlap if and only if:
start1 < end2 AND start2 < end1This condition captures all overlap scenarios. If this condition is false, the intervals are either adjacent or completely separate.
Hint 3: Managing Booking IDs Use a counter or UUID to generate unique booking IDs. You'll need to maintain a mapping from booking IDs to the room where the booking was made, so you can find and remove the booking during cancellation.
Full Solution `` Complexity Analysis:
Time Complexity:
add_room: O(1)book_room: O(n) where n is the number of bookings in the room (checking conflicts)cancel_booking: O(n) where n is the number of bookings in the roomcheck_availability: O(n) where n is the number of bookings in the roomfind_available_rooms: O(r × n) where r is the number of rooms and n is average bookings per roomSpace Complexity: O(r + b) where r is the number of rooms and b is the total number of bookings
Design Decisions:
- Separation of Concerns: Split into three classes (Booking, Room, BookingSystem) for clear responsibility division
- Sorted Bookings: Keeping bookings sorted by start time enables potential optimizations like binary search or early termination in conflict checking
- Booking ID Mapping: Maintained a separate map for quick booking cancellation without searching through all rooms
- Overlap Logic: Used standard interval overlap formula that handles all edge cases including adjacent bookings
Potential Enhancements:
- Use interval trees or segment trees for O(log n) conflict detection
- Add booking priorities or waitlist functionality
- Support recurring bookings
- Add user authentication and booking ownership
- Implement capacity-based booking (partial room booking)
- Add notification system for booking confirmations and reminders
class Booking {
roomId: string;
startTime: number;
endTime: number;
bookingId: string;
constructor(roomId: string, startTime: number, endTime: number, bookingId: string) {
}
}
class Room {
roomId: string;
capacity: number;
bookings: Booking[];
constructor(roomId: string, capacity: number) {
}
isAvailable(startTime: number, endTime: number): boolean {
}
addBooking(startTime: number, endTime: number, bookingId: string): boolean {
}
cancelBooking(bookingId: string): boolean {
}
}
class BookingSystem {
rooms: Map<string, Room>;
bookingCounter: number;
constructor() {
}
addRoom(roomId: string, capacity: number): void {
}
bookRoom(roomId: string, startTime: number, endTime: number): string | null {
}
cancelBooking(bookingId: string): boolean {
}
checkAvailability(roomId: string, startTime: number, endTime: number): boolean {
}
findAvailableRooms(startTime: number, endTime: number): string[] {
}
}