Exam Room

Medium

Quora

3 views

Topics:

ArraysGreedy Algorithms

There is an exam room with n seats in a single row labeled from 0 to n - 1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number 0.

Design a class that simulates the mentioned exam room.

Implement the ExamRoom class:

ExamRoom(int n) Initializes the object of the exam room with the number of the seats n.
int seat() Returns the label of the seat at which the next student will set.
void leave(int p) Indicates that the student sitting at seat p will leave the room. It is guaranteed that there will be a student sitting at seat p.

Example 1:

Input
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
Output
[null, 0, 9, 4, 2, null, 5]

Explanation
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
examRoom.seat(); // return 9, the student sits at the last seat number 9.
examRoom.seat(); // return 4, the student sits at the last seat number 4.
examRoom.seat(); // return 2, the student sits at the last seat number 2.
examRoom.leave(4);
examRoom.seat(); // return 5, the student sits at the last seat number 5.

Constraints:

1 <= n <= 10⁹
It is guaranteed that there is a student sitting at seat p.
At most 10⁴ calls will be made to seat and leave.

Try coding it in LeetCode

Exam Room

Medium

Quora

3 views

Topics:

ArraysGreedy Algorithms

There is an exam room with n seats in a single row labeled from 0 to n - 1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number 0.

Design a class that simulates the mentioned exam room.

Implement the ExamRoom class:

ExamRoom(int n) Initializes the object of the exam room with the number of the seats n.
int seat() Returns the label of the seat at which the next student will set.
void leave(int p) Indicates that the student sitting at seat p will leave the room. It is guaranteed that there will be a student sitting at seat p.

Example 1:

Input
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
Output
[null, 0, 9, 4, 2, null, 5]

Explanation
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
examRoom.seat(); // return 9, the student sits at the last seat number 9.
examRoom.seat(); // return 4, the student sits at the last seat number 4.
examRoom.seat(); // return 2, the student sits at the last seat number 2.
examRoom.leave(4);
examRoom.seat(); // return 5, the student sits at the last seat number 5.

Constraints:

1 <= n <= 10⁹
It is guaranteed that there is a student sitting at seat p.
At most 10⁴ calls will be made to seat and leave.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of students, n, that can be in the exam room?
When the exam room is empty, what seat should be assigned (e.g., 0, -1, the largest available, etc.)?
If multiple seats are equally far from the nearest student, which seat should be assigned (e.g., the lowest numbered, a random one)?
Will `leave()` ever be called with an invalid student id (i.e., a student id that was never assigned or has already left)?
What is the expected number of calls to `seat()` and `leave()`? Should I optimize for a particular frequency of these calls?

Brute Force Solution

Approach

The exam room problem is about figuring out the best seat to assign. A brute force approach means we'll check every single seat one by one to see which is the best.

Here's how the algorithm would work step-by-step:

When someone wants to sit, we'll go through each empty seat in the room.
For each empty seat, we'll measure how far it is from all the other people already sitting.
We want the seat that's furthest away from everyone else. So, for each empty seat, we find the shortest distance to another person.
After we've checked all the empty seats, we pick the seat that had the biggest shortest distance. That's the best seat!
When someone leaves, we simply mark their seat as empty again.

Code Implementation

class ExamRoom:

    def __init__(self, room_size):
        self.room_size = room_size
        self.students = []

    def seat(self): 
        if not self.students:
            self.students.append(0)
            return 0

        # Consider sitting at the beginning.
        max_distance = self.students[0]
        seat_position = 0

        # Check the distances between occupied seats.
        for i in range(1, len(self.students)):
            distance = (self.students[i] - self.students[i - 1]) // 2
            if distance > max_distance:

                # Because current distance is the largest
                max_distance = distance
                seat_position = self.students[i - 1] + distance

        # Consider sitting at the end.
        if self.room_size - 1 - self.students[-1] > max_distance:
            seat_position = self.room_size - 1

        # Find the correct position to insert
        insert_index = 0
        while insert_index < len(self.students) and self.students[insert_index] < seat_position:
            insert_index += 1

        # Insert the student into the sorted list
        self.students.insert(insert_index, seat_position)
        return seat_position

    def leave(self, student_position):
        self.students.remove(student_position)

Big(O) Analysis

Time Complexity

O(n²) – When a person enters the exam room, we iterate through all possible seats (up to n seats where n is the maximum seat number). For each empty seat, we calculate its distance to every occupied seat. In the worst case, all seats are occupied except for one, requiring us to iterate through approximately n occupied seats to find the minimum distance. This nested iteration results in roughly n * n operations, hence the time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm checks each empty seat and calculates distances. It does not mention storing all distances or using data structures that scale with the maximum seat number (N). The plain English explanation suggests only temporary calculations of shortest distances for each seat, which are not persistently stored. Therefore, the space used remains constant regardless of N, leading to O(1) space complexity.

Optimal Solution

Approach

The problem can be solved efficiently by focusing on maintaining the largest possible distance between students. We use a system that keeps track of occupied seats and then quickly identifies where to place the next student to maximize that distance.

Here's how the algorithm would work step-by-step:

Keep track of which seats are already taken, sorting them in order.
To find the best seat for a new student, look at the gaps between existing students.
Figure out the largest gap between any two students, and calculate the midpoint of that gap.
Also check the distances from the ends of the room to the first and last occupied seats.
Choose the location (either a midpoint of a gap or one of the ends) that gives the largest possible distance to the nearest student.
When a student leaves, simply remove their seat from the occupied seat list, which automatically updates the gaps.

Code Implementation

class ExamRoom:
    def __init__(self, room_size):
        self.room_size = room_size
        self.occupied_seats = []

    def seat(self): 
        if not self.occupied_seats:
            self.occupied_seats.append(0)
            return 0

        max_distance = self.occupied_seats[0]
        seat_position = 0

        #Find the maximum distance between occupied seats.
        for i in range(1, len(self.occupied_seats)):
            distance = (self.occupied_seats[i] - self.occupied_seats[i - 1]) // 2
            if distance > max_distance:
                max_distance = distance
                seat_position = self.occupied_seats[i - 1] + distance

        #Check the distance to the end of the room.
        if self.room_size - 1 - self.occupied_seats[-1] > max_distance:
            max_distance = self.room_size - 1 - self.occupied_seats[-1]
            seat_position = self.room_size - 1

        self.occupied_seats.append(seat_position)
        self.occupied_seats.sort()

        return seat_position

    def leave(self, seat_number):
        #Remove student from occupied seats when they leave.
        self.occupied_seats.remove(seat_number)

Big(O) Analysis

Time Complexity

O(n log n) – The primary operations driving the time complexity are related to maintaining the sorted order of occupied seats. Specifically, the add operation involves finding the optimal seat, which requires iterating through the occupied seats to find the largest gap (O(n) in the worst case). Because inserting a new seat requires maintaining the sorted order, a data structure such as a sorted list or a self-balancing tree is implicitly used. The add and remove operations, assuming usage of a self-balancing tree, therefore take O(log n). Since we perform these operations at most n times, the overall time complexity is O(n log n).

Space Complexity

O(N) – The solution maintains a sorted list of occupied seats. In the worst-case scenario, all N seats in the exam room could be occupied. Therefore, the auxiliary space used to store the occupied seats list grows linearly with the number of seats, N. No other significant data structures contribute to space complexity beyond this sorted list. Thus, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Initial exam room is empty (n=0)	Throw an exception or return an appropriate error code since an exam room must have a positive size.
Calling seat() when the room is full (all seats are occupied)	Return -1 to indicate no seat available or throw an exception if the API does not allow such action.
Calling leave(p) with an invalid seat number (p not seated)	Ignore the request, throw an exception or return an error code indicating the seat is not occupied.
Very large n (room size) impacting memory usage or performance of calculations	Use efficient data structures such as a balanced binary search tree or a priority queue to manage seated positions, reducing the time complexity of seat() and leave().
Floating-point calculations for distance between seats, potentially leading to precision errors	Avoid floating-point operations or use integers whenever possible, and if needed, use an epsilon value for comparisons to account for potential inaccuracies.
The same person tries to 'leave' multiple times	Ensure that after a person leaves, their ID is removed from any data structures storing seated people, preventing double removal issues.
leave(p) with p being a negative or zero value.	Throw IllegalArgumentException if p is a zero or negative number.
n (room size) is negative.	Throw IllegalArgumentException if n is a negative number.