We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Exam Room

Number: 885

Difficulty: Medium

Paid? No

Companies: Uber, Bloomberg, Quip (Salesforce), Quora, Google

Problem Description

Design a system to simulate an exam room with n seats in a single row (indexed 0 to n-1). When a student enters the room, they choose a seat that maximizes the distance to the closest person (choosing the lowest-indexed seat in case of ties). If the room is empty, the student sits at seat 0. Additionally, implement a method for a student to leave their seat.

Key Insights

  • The main challenge is quickly finding the optimal seat on each call of seat() while maintaining the ordered structure of occupied seats.
  • Using an ordered container (like a TreeSet or sorted list) allows efficient identification of adjacent seated students.
  • The maximum distance could occur at the beginning (seat 0), at the end (seat n-1), or between two occupied seats. For the middle case, the optimal seat is the midpoint.
  • When a student leaves, simply remove the seat from the ordered container.

Space and Time Complexity

Time Complexity: O(m) per seat() or leave() call in worst case, where m is the number of occupied seats (with m up to O(10^4)).
Space Complexity: O(m), as we store the occupied seats.

Solution

We maintain a sorted list (or equivalent ordered set in other languages) to keep track of occupied seats. For seat():

  1. If the room is empty, return seat 0.
  2. Otherwise, calculate the distance from 0 to the first occupied seat and from the last occupied seat to n - 1.
  3. For every pair of adjacent occupied seats, compute the distance as half the gap.
  4. Select the position that gives the maximum distance to the nearest student; if multiple positions yield the same distance, choose the smallest seat number.
  5. Insert the seat into the sorted list.

For leave(p):

  1. Remove p from the sorted list.
  2. No merging of intervals is explicitly needed since the sorted list always reflects the current seating arrangement.

This approach leverages ordered data structures and scanning of adjacent elements to always find the best seat efficiently.

Code Solutions

# Python Implementation
import bisect

class ExamRoom:
    def __init__(self, n: int):
        # Total number of seats.
        self.n = n
        # Sorted list to store the positions of seated students.
        self.seated = []

    def seat(self) -> int:
        # If the room is empty, seat the student at 0.
        if not self.seated:
            bisect.insort(self.seated, 0)
            return 0
        
        # Initialize the best seat and maximum distance.
        best_seat = 0
        max_distance = self.seated[0]  # Distance from seat 0 to first student.
        
        # Check distances between adjacent seated students.
        for i in range(1, len(self.seated)):
            prev = self.seated[i-1]
            curr = self.seated[i]
            # Candidate seat is the midpoint.
            candidate = prev + (curr - prev) // 2
            # Distance is the minimum distance to either neighbor.
            distance = candidate - prev
            if distance > max_distance:
                max_distance = distance
                best_seat = candidate
        
        # Check the distance from the last occupied seat to the end (n - 1).
        if (self.n - 1) - self.seated[-1] > max_distance:
            best_seat = self.n - 1
        
        # Insert the selected seat while maintaining sorted order.
        bisect.insort(self.seated, best_seat)
        return best_seat

    def leave(self, p: int) -> None:
        # Remove seat p from the list.
        index = bisect.bisect_left(self.seated, p)
        if index < len(self.seated) and self.seated[index] == p:
            self.seated.pop(index)
← Back to All Questions