Print Zero Even Odd

Print Zero Even Odd

What is this problem about?

The Print Zero Even Odd concurrency problem requires four threads to print numbers in the sequence 0,1,0,2,0,3,...,0,n using coordinated methods: zero() prints 0, even() prints even numbers, and odd() prints odd numbers. The threads must interleave correctly. This medium concurrency coding problem uses multiple semaphores for ordering. The concurrency interview pattern is demonstrated at a higher level than Print in Order.

Why is this asked in interviews?

Goldman Sachs asks this to test multi-phase semaphore coordination. Three threads must alternate in a specific pattern, and the correct synchronization prevents race conditions while ensuring the right sequence.

Algorithmic pattern used

Three-semaphore coordination. zero_sem=1, odd_sem=0, even_sem=0. zero(): loop n times: wait zero_sem, print 0, signal odd_sem (if i odd) or even_sem (if i even). odd(): loop n//2 or ceil(n/2) times: wait odd_sem, print, signal zero_sem. even(): loop n//2 times: wait even_sem, print, signal zero_sem.

Example explanation

n=4. Sequence: 0,1,0,2,0,3,0,4.

• zero thread: prints 0, signals odd (for 1).
• odd thread: prints 1, signals zero.
• zero thread: prints 0, signals even (for 2).
• even thread: prints 2, signals zero. Continue until 4 printed. Output: "01020304".

Common mistakes candidates make

• Initializing all semaphores to 0 (deadlock on first zero print).
• Not distinguishing even/odd signal from zero thread.
• Incorrect loop counts for even vs odd threads.
• Semaphore leaks on n=1 (only one number, odd thread runs once, even thread runs 0 times).

Interview preparation tip

Multi-semaphore concurrency problems require drawing the signal flow before coding. Draw: zero→(odd or even)→zero→... as a directed graph. Each arrow is a semaphore signal. Initialize semaphores based on which thread runs first. For n=4: 2 odd prints, 2 even prints, 5 zero prints. Practice mapping signal flows to semaphore initialization for complex ordering patterns.