algoadvance

An exam room is a linear array of seats numbered from 0 to N-1 (inclusive). Students enter the room one at a time and choose seats based on the following logic:

• A student tries to sit as far away from any other student as possible.
• If there are multiple such seats, the student sits in the lowest-numbered one.

Implement the ExamRoom class:

• ExamRoom(int N) initializes the object with N seats.
• int seat() returns the seat index at which the next student will sit.
• void leave(int p) indicates that the student in seat p leaves the room. It is guaranteed that the given seat p will be occupied.

Clarifying Questions

1. What constraints on the number of students and seats should I be aware of?
   • The number of seats, N, is positive and at most 10^9.
   • seat() and leave() methods will be called at most 10^4 times.
2. Is real-time performance a concern for this problem?
   • Yes, methods need to be efficient given the constraints.
3. Can we assume that seat and leave operations are interleaved correctly?
   • Yes, a student will not leave if there are no students, and the student in seat p will always be present if leave(p) is called.

Strategy

1. Data Structures:
   • We’ll maintain a sorted list to keep track of occupied seats (seats). Sorting allows easier calculation of maximum distance.
2. Algorithm for seat():
   • If the room is empty, the first student sits at seat 0.
   • For subsequent students, find the maximum distance between adjacent students and consider distances from the first seat to the first student and the last student to the last seat.
   • Insert the student in the determined seat and keep the list sorted.
3. Algorithm for leave(p):
   • Simply remove p from the sorted list of occupied seats.

Code

class ExamRoom:

    def __init__(self, N: int):
        self.N = N
        self.seats = []

    def seat(self) -> int:
        if not self.seats:
            seat = 0
        else:
            # Consider the distance to the start and end
            max_distance = self.seats[0]
            prev_seat = -1
            seat = 0
            
            # Check the distances between the occupied seats
            for i in range(1, len(self.seats)):
                d = (self.seats[i] - self.seats[i - 1]) // 2
                if d > max_distance:
                    max_distance = d
                    seat = self.seats[i - 1] + d
            
            # Consider the distance to the last seat
            if self.N - 1 - self.seats[-1] > max_distance:
                seat = self.N - 1
            
        # Insert the new seat in the list and keep it sorted
        bisect.insort(self.seats, seat)
        return seat

    def leave(self, p: int) -> None:
        self.seats.remove(p)

Time Complexity

1. seat() Method:
   • Finding the max distance costs O(K) where K is the number of occupied seats.
   • Inserting into the sorted list costs O(K).
2. leave() Method:
   • Removing from the sorted list costs O(K).

Given that seat() and leave() may be called 10^4 times, where K will be proportional to 10^4 at maximum, these operations are efficient.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?