Katkat
Back

Implement in-memory data structures and booking API

OracleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a thread-safe, in-memory booking system using efficient data structures to handle temporal queries and capacity management.

Problem Statement

You are tasked with designing an in-memory Booking System for a cinema. The system must track seat availability across multiple theater halls and handle concurrent reservation requests.

Requirements

  1. add_hall(hall_id, capacity): Register a new hall with a fixed number of seats.
  2. book_seat(hall_id, user_id): Reserve a seat in the specified hall. If successful, return a unique booking_id. If the hall is full, return null.
  3. cancel_booking(booking_id): Free up the seat associated with the booking. If the ID is invalid, return false, otherwise true.
  4. get_hall_status(hall_id): Return the current number of available seats in the hall.

Constraints

  • Hall IDs are strings, user_id are strings, booking_id can be any unique identifier.
  • Efficiency is critical: operations should be faster than O(N) where N is the number of bookings.
  • Assume the system must be thread-safe (you may use language-specific primitives like locks or mutexes).

Example

system = BookingSystem()
system.add_hall("Hall_A", 2)
system.book_seat("Hall_A", "User_1") # Returns "B1"
system.book_seat("Hall_A", "User_2") # Returns "B2"
system.book_seat("Hall_A", "User_3") # Returns null
system.cancel_booking("B1")
system.get_hall_status("Hall_A") # Returns 1

Considerations

  • How will you handle seat allocation to ensure you can quickly identify which seat index is available?
  • What data structures allow for O(1) booking and cancellation?

Hints

Hint 1

Use a Hash Map to store halls and their current capacity/set of available seats.

Hint 2

Use a secondary Hash Map to store the mapping of `booking_id` to its corresponding `hall_id` for quick lookup during cancellation.

Hint 3

Consider using a `Deque` or a `Set` to store available seat numbers to maintain O(1) allocation and deallocation.

Follow-up questions

  • How would you modify this system to support time-based bookings (e.g., booking a seat for a specific showtime)?
  • If the system needs to persist data to disk, what strategy would you use to minimize write latency?
  • How would you handle distributed consistency if this service is replicated across multiple nodes?