Implement a Semaphore
Updated
Problem statement
Implement a thread-safe counting semaphore with acquire and release. An acquire consumes one available permit; when none is available, the calling worker must block until a release grants it a permit. A release either wakes one waiting worker or stores one additional permit. Protect shared state against concurrent access and tolerate spurious wakeups.
For this exercise, assume waiting acquires are served in first-in, first-out order. Implement the semaphore yourself using mutexes, condition variables, atomic wait/notify, or equivalent blocking primitives; do not use a built-in semaphore.
Expose the implementation through semaphoreTrace(initialPermits, operations). For this exercise, assume a coordinator processes the following operations in array order:
- A positive value
idassigns a concurrent worker that ID. The worker calls acquire exactly once. The coordinator waits until the request is registered: either the worker consumed an available permit, or it joined the FIFO wait queue. If it acquired immediately, wait for that acquire to complete and appendidto the trace. Otherwise append0and leave the worker blocked. - A zero calls release. If a worker was waiting, grant the permit to the oldest waiting request, wait for that acquire to complete, and append its ID. Otherwise store the permit and append
0.
Finish each coordinator step before starting the next one. A completed worker does not automatically release its permit. All positive IDs are unique, and the input supplies enough permits for every acquire to complete by the end. Wait for all acquires to finish before returning the trace.
The workers must execute concurrently: use threads in Python, Java, and C++, goroutines in Go, or Node.js worker threads with shared atomic state in JavaScript. Acquires without permits must actually block and be awakened by release. Computing the trace with a sequential queue or counter alone does not satisfy the task. Registration and completion signals are wrapper bookkeeping, separate from the semaphore permit count.
Function
semaphoreTrace(initialPermits: int, operations: int[]) → int[]Examples
Example 1
initialPermits = 0operations = [7,3,0,0]return = [0,0,7,3]Workers 7 and 3 block because no permit is available. The first release wakes worker 7; the second wakes worker 3. The acquisition steps therefore return 0, 0, followed by completion IDs 7, 3.
Example 2
initialPermits = 1operations = [9,2,0,0]return = [9,0,2,0]Worker 9 consumes the initial permit. Worker 2 blocks, then completes on the first release. The next release stores a permit because nobody is waiting, so it returns 0.
Example 3
initialPermits = 2operations = [8,0,5]return = [8,0,5]Worker 8 consumes one of the two initial permits. The release stores another permit because nobody is waiting. Worker 5 then consumes one available permit.
Example 4
initialPermits = 0operations = []return = []There are no operations or workers, so the returned trace is empty.
Constraints
0 <= initialPermits <= 8.0 <= operations.length <= 24.0 <= operations[i] <= 1000.- There are at most 2 positive operations, and their IDs are distinct.
initialPermits + number of zero operations >= number of positive operations.
More NVIDIA Phone Screen questions
- Summarize Server Healthcheck LogsPHONE SCREEN · Seen Oct 2026
- Hash Partition OffsetsPHONE SCREEN · Seen Oct 2026
- Filter Paginated Medical RecordsPHONE SCREEN · Seen Oct 2026
- Least Frequently Used CachePHONE SCREEN · Seen Oct 2026
- Parallel String Counts with a Custom Hash TablePHONE SCREEN · Seen Oct 2026
- Simulate a Reference-Counted Smart PointerPHONE SCREEN · Seen Aug 2026
- Streaming Top-K Frequent ElementsPHONE SCREEN · Seen Aug 2026
- Merge Multiple Sorted StreamsPHONE SCREEN · Seen Aug 2026
- Linked List Palindrome in Constant SpacePHONE SCREEN · Seen Aug 2026
- LRU Key-Value Cache OperationsPHONE SCREEN · Seen Aug 2026
Similar questions at other companies
- Simulate a Queued Multi-Rule Rate LimiterSnowflake · PHONE SCREENSnowflake interview questions
- Modal Lock and Fair Modal LockOpenAI · PHONE SCREENOpenAI interview questions
- Fixed Worker Pool with a Shared QueueSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Bounded Producer–Consumer QueueMakeMyTrip.com · ONSITE INTERVIEWMakeMyTrip.com interview questions
- Concurrent Buffered File LoggerDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Implement a Multithreaded Bounded QueueAMD · ONSITE INTERVIEWAMD interview questions
- Blocking Connection Pool Operation TraceGoogle · ONSITE INTERVIEWGoogle interview questions
- Keyed Bounded Executor ScheduleMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- One-Shot Callback Event DispatchPure Storage · ONSITE INTERVIEWPure Storage interview questions
- Design Hit CounterCharta Health · PHONE SCREENCharta Health interview questions