## Implement a Synchronized First-Available Seat Allocator Implement the core of a concurrent ticket-booking service with `N` seats numbered `1` through `N`. Seats are initially available, and the only operation is `allocateFirstAvailable()`: - A successful call atomically claims and returns the lowest available seat number. - Once claimed, a seat is never released in this exercise. - If all seats have been claimed, the call returns `-1`. Up to `Q` calls may overlap across threads. No seat may be returned twice. The observed results must be linearizable: they must be explainable by one serial ordering that respects calls that completed before later calls began. ### Constraints & Assumptions - `1 <= N <= 1,000,000` and `1 <= Q <= 1,000,000`. - A process crash, distributed replication, cancellations, and payments are outside this exercise. - The implementation may use a lock or a compare-and-set primitive supplied by the language runtime. - Returning `-1` must not make a later call appear to allocate a seat that was already available at that call's linearization point. ### Clarifying Questions to Ask - Is fairness among waiting threads required, or only correctness and progress? - May calls be interrupted while waiting, and what cancellation behavior is expected? - Is a lock-free implementation required, or is a short critical section acceptable? ```hint Use the no-release property Because successful allocations never create holes, identify the smallest state that represents every seat already claimed. ``` ### What a Strong Answer Covers - A precise linearization point for both successful and sold-out calls. - Mutual exclusion or atomic compare-and-set logic that prevents duplicate seats. - Correct handling of contention at seat `N` without an off-by-one allocation. - Time, memory, fairness, overflow, and test considerations for the chosen primitive. ### Follow-up Questions 1. How would the representation change if cancellations could return arbitrary seats? 2. How would you test a duplicate-allocation race reliably? 3. What trade-off does a fair lock make compared with an atomic counter under heavy contention? 4. Which extra guarantees would be needed if allocation moved across several service instances?