How do you approach Print Zero, Even, Odd in Order?

In the real concurrent version: zero() holds permission until released, then signals odd or even based on a counter.

What are common mistakes on Print Zero, Even, Odd in Order?

Re-checking a condition with if instead of while after waiting. Spurious wakeups are real. Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock. Assuming statements execute in program order without a barrier, a volatile read, or an atomic.

gitGood.dev

← Back to problems

Print Zero, Even, Odd in Order

HardOperating Systems

Description

**Concurrency design problem (paper-only).** This problem exercises threading / synchronisation primitives that the gitGood code-execution sandbox does not expose. The auto-grader instead validates a single-threaded *simulation* of the protocol so you can still verify your scheduler logic; in a real interview you would write the multi-threaded version. You have a class `ZeroEvenOdd` shared by three threads: - Thread A repeatedly calls `zero()`, which prints `0`. - Thread B repeatedly calls `even()`, which prints an even number. - Thread C repeatedly calls `odd()`, which prints an odd number. For a given integer `n`, the three threads collectively print the sequence `0102030405...` up through `n`, i.e. for `n = 5` the output is `"0102030405"`. The threads coordinate using two semaphores (one gating `even`, one gating `odd`). Thread A toggles which side it releases after each zero. **For the auto-grader:** implement `zeroEvenOdd(n)` that returns the string the three threads would collectively produce for input `n`. Your single-threaded simulation must follow the protocol described in the explanation (don't just return `"01020304..."` by string concatenation - work through the state machine).

Example 1

Input: n = 2

Output: "0102"

Explanation: Thread A prints 0, thread C prints 1, thread A prints 0, thread B prints 2.

Example 2

Input: n = 5

Output: "0102030405"

Constraints

- 1 <= n <= 1000

Print Zero, Even, Odd in Order: approach, complexity and pitfalls

A hard concurrency problem, graded against 5 test cases (2 of them hidden).

The pattern: Concurrency

Coordinating threads with locks, semaphores, and condition variables.

Reach for it when you see: Ordering guarantees between threads, bounded buffers, or classic synchronisation puzzles.

More Concurrencyproblems →

If you are stuck

Show the 3-step hint ladder

In the real concurrent version: zero() holds permission until released, then signals odd or even based on a counter.
Two semaphores: oddSem (initial 0) and evenSem (initial 0). zero() increments a counter then releases oddSem if odd, evenSem if even, then waits on its own zeroSem.
For the simulation, walk a state machine: who is allowed to act next given the count printed so far.

The optimal approach

Show the approach: Real concurrent design (what you would write in an interview)

```

class ZeroEvenOdd:

n: int

counter: int # last number printed by even/odd, starts at 0

zeroSem: Semaphore(1) # zero() may run when this is up

oddSem: Semaphore(0) # odd() may run when this is up

evenSem: Semaphore(0) # even() may run when this is up

zero():

for i in 1..n:

zeroSem.acquire()

print(0)

if i is odd: oddSem.release()

else: evenSem.release()

odd():

for each odd i in 1..n:

oddSem.acquire()

print(i)

zeroSem.release()

even():

for each even i in 1..n:

evenSem.acquire()

print(i)

zeroSem.release()

```

The two-semaphore handshake guarantees ordering: `zero` only runs when zeroSem is up, `odd`/`even` only when their gate is up, and each role releases the next role's gate.

Why this is paper-only here

Our sandbox executors strip threading / asyncio / signal-based scheduling for safety. The simulation faithfully walks the same state machine; the test cases would all pass with a correctly synchronised real implementation.

Time / Space: O(n) prints, O(1) extra state.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Concurrency mistakes

These apply to the pattern as a whole, not just this problem.

Re-checking a condition with `if` instead of `while` after waiting. Spurious wakeups are real.
Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock.
Assuming statements execute in program order without a barrier, a volatile read, or an atomic.

← Back to problems

Print Zero, Even, Odd in Order

HardOperating Systems

Description

Example 1

Input: n = 2

Output: "0102"

Explanation: Thread A prints 0, thread C prints 1, thread A prints 0, thread B prints 2.

Example 2

Input: n = 5

Output: "0102030405"

Constraints

- 1 <= n <= 1000

Print Zero, Even, Odd in Order: approach, complexity and pitfalls

A hard concurrency problem, graded against 5 test cases (2 of them hidden).

The pattern: Concurrency

Coordinating threads with locks, semaphores, and condition variables.

Reach for it when you see: Ordering guarantees between threads, bounded buffers, or classic synchronisation puzzles.

More Concurrencyproblems →

If you are stuck

Show the 3-step hint ladder

In the real concurrent version: zero() holds permission until released, then signals odd or even based on a counter.
Two semaphores: oddSem (initial 0) and evenSem (initial 0). zero() increments a counter then releases oddSem if odd, evenSem if even, then waits on its own zeroSem.
For the simulation, walk a state machine: who is allowed to act next given the count printed so far.

The optimal approach

Show the approach: Real concurrent design (what you would write in an interview)

```

class ZeroEvenOdd:

n: int

counter: int # last number printed by even/odd, starts at 0

zeroSem: Semaphore(1) # zero() may run when this is up

oddSem: Semaphore(0) # odd() may run when this is up

evenSem: Semaphore(0) # even() may run when this is up

zero():

for i in 1..n:

zeroSem.acquire()

print(0)

if i is odd: oddSem.release()

else: evenSem.release()

odd():

for each odd i in 1..n:

oddSem.acquire()

print(i)

zeroSem.release()

even():

for each even i in 1..n:

evenSem.acquire()

print(i)

zeroSem.release()

```

The two-semaphore handshake guarantees ordering: `zero` only runs when zeroSem is up, `odd`/`even` only when their gate is up, and each role releases the next role's gate.

Why this is paper-only here

Time / Space: O(n) prints, O(1) extra state.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Concurrency mistakes

These apply to the pattern as a whole, not just this problem.

Re-checking a condition with `if` instead of `while` after waiting. Spurious wakeups are real.
Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock.
Assuming statements execute in program order without a barrier, a volatile read, or an atomic.