Katkat
Back

Implement a Synchronized First-Available Seat Allocator

TargetBackend Engineer · Online Assessment
MediumBackend EngineerOnline AssessmentSoftware Engineering Fundamentals

Last updated

This problem tests your ability to design a thread-safe allocator that manages a finite resource pool under high concurrency, focusing on atomic updates and race condition prevention.

Problem Description

You are tasked with building a seat allocator for a high-traffic event. There are N seats, labeled 0 to N-1. You need to implement a class SeatAllocator that provides a thread-safe way to claim the lowest available seat number.

Once a seat is claimed, it cannot be reclaimed. If all seats are sold, the system should return -1. You are guaranteed that seats are only ever claimed, never released.

Requirements

  • Implement the method claimSeat() -> int.
  • The implementation must ensure that no two threads receive the same seat number.
  • The implementation should be performant under high contention (multiple threads calling claimSeat simultaneously).

Class Interface

class SeatAllocator:
    def __init__(self, n: int):
        # Initializes with n seats (0 to n-1)
        pass

    def claimSeat(self) -> int:
        # Returns the lowest unclaimed seat number, or -1 if none are left
        pass

Examples

Example 1:

  • allocator = SeatAllocator(3)
  • allocator.claimSeat() -> returns 0
  • allocator.claimSeat() -> returns 1
  • allocator.claimSeat() -> returns 2
  • allocator.claimSeat() -> returns -1

Constraints

  • 1 <= N <= 10^7
  • The solution must be thread-safe.
  • Minimize the duration of time spent holding locks (if using locks).

Hints

Hint 1

Consider using an atomic counter that tracks the index of the next available seat.

Hint 2

If using a language with atomic primitives, look for a 'fetch-and-add' style operation to increment the counter and retrieve the old value in one step.

Hint 3

If using locks, ensure the critical section is as small as possible to prevent bottlenecks during high concurrency.

Follow-up questions

  • How would you modify your design if seats could be returned (unclaimed) later?
  • What are the performance implications of using a Mutex versus an atomic integer (compare-and-swap) at extreme scales of N?
  • How would you ensure fairness (e.g., FIFO order) if there were thousands of threads waiting to claim a seat?