FastPrepImplement a Semaphore
Problems/Implement a Semaphore

Implement a Semaphore

NVIDIA logoNVIDIA● MediumINTERNPHONE SCREEN

Updated Oct 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The interview report asks for a semaphore implementation but gives no interface, fairness policy, or examples. FIFO wakeups and the bounded concurrent trace wrapper are practice assumptions; the core synchronization task matches at about 65%.

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 id assigns 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 append id to the trace. Otherwise append 0 and 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

Interview reports that mention this question

  • NVIDIA Software Intern Interview Questions: 9 Experiences

NVIDIA interview experiences

  • NVIDIA DevOps, QA and Infra Intern Interviews: 12 Experiences
  • NVIDIA Ignite Internship OA Experience
  • NVIDIA Ignite SWE Intern OA Questions: 6 Experiences
All NVIDIA interview questionsSee NVIDIA hiring insights
Saved
class Solution {
    public int[] semaphoreTrace(int initialPermits, int[] operations) {
        // Implement the semaphore and run the concurrent workers.
    }

}
Checking account…