Problem 9 Print in Order using multithreading

Problem Statement

Ensure the ordered execution of methods across different threads. We have three methods — first(), second(), and third() — and we must guarantee that first() completes before second(), and second() completes before third(), regardless of the order in which the threads are started or scheduled.

Solution

We use two CountDownLatch objects as one-shot signals between threads. A CountDownLatch initialized to 1 blocks any thread that calls await() until another thread calls countDown().

• firstDone starts at 1. second() waits on it; first() counts it down after printing.
• secondDone starts at 1. third() waits on it; second() counts it down after printing.

This is a minimal-change, coherent design: even if the JVM schedules third() before first(), the latch forces third() to wait until second() has run, and second() waits until first() has run.

Trace — reverse start order (third, second, first)

Threads are scheduled in the worst order; latches still force print order:

Start order ≠ run order. The signal chain is the only authority.

Why this latch can't miss its signal: level-triggered, not edge-triggered

The trace above shows the awaiters blocking first and then being released — but the design is correct even in the opposite race, and understanding why is the point an interviewer digs at. A CountDownLatch is level-triggered: its count is durable state, and await() is a test of that state, not a wait for an event. Once countDown() drives the count to 0 it stays 0, so a later await() reads “already 0” and returns immediately — the signal cannot be missed because it was never a fleeting pulse, it is a persistent fact.

Play the reordering the reverse-start trace didn’t cover — first() runs entirely before second() ever reaches its wait:

Now contrast the edge-triggered primitive, Object.notify() / Condition.signal(). A notify is a one-shot pulse delivered only to threads currently waiting; it is not remembered. Run the same race with a bare monitor: if T1 calls obj.notify() before T2 has called obj.wait(), the pulse wakes nobody, T2 then wait()s, and — with no further signal coming — hangs forever. That is the classic lost wakeup. The only fix is to pair the condition with durable state and re-check it in a loop (while (!done) cond.await();) — i.e. you must manually rebuild the level-triggered behaviour the latch gives you for free. This is exactly why the latch (and the semaphore, whose released permit is likewise remembered) is the right primitive for one-shot ordering, while a raw condition variable needs the defensive while-loop to be safe.

Code

import java.util.concurrent.CountDownLatch;

/**
 * This Foo class ensures that its methods are called in a specific order:
 * `first`, followed by `second`, and then `third`.
 */
public class Solution {

  // CountDownLatches are synchronization aids that allow one or more threads to wait
  // until a set of operations being performed in other threads completes.

  // This latch ensures that `second` waits until `first` has finished executing.
  private final CountDownLatch firstDone = new CountDownLatch(1);

  // This latch ensures that `third` waits until `second` has finished executing.
  private final CountDownLatch secondDone = new CountDownLatch(1);

  public Solution() {}

  public void first() {
    // This is the first method, and it can proceed without waiting.
    print("first");
    // Decrement the count of the latch, signaling that this method is done.
    firstDone.countDown();
  }

  public void second() throws InterruptedException {
    // Wait for the first method to complete.
    firstDone.await();
    print("second");
    // Signal that the second method has now completed.
    secondDone.countDown();
  }

  public void third() throws InterruptedException {
    // Wait for the second method to complete.
    secondDone.await();
    print("third");
  }

  private void print(String msg) {
    System.out.print(msg);
  }

  public static void main(String[] args) {
    Solution foo = new Solution();

    Thread threadA = new Thread(() -> {
      try {
        foo.first();
      } catch (Exception e) {
        e.printStackTrace();
      }
    });

    Thread threadB = new Thread(() -> {
      try {
        foo.second();
      } catch (Exception e) {
        e.printStackTrace();
      }
    });

    Thread threadC = new Thread(() -> {
      try {
        foo.third();
      } catch (Exception e) {
        e.printStackTrace();
      }
    });

    // The actual order in which the threads start and get scheduled is up to the
    // JVM and the OS, but the CountDownLatches ensure they complete as first,
    // second, third.
    threadA.start();
    threadB.start();
    threadC.start();
  }
}

Go version: channel gates (close-as-signal)

Idiomatic dual: two channels; first closes g2; second receives g2 then closes g3; third receives g3. close happens-before every receive that sees the closed channel — same edge as latch countDown→await.

package main

import (
    "fmt"
    "sync"
)

func main() {
    g2, g3 := make(chan struct{}), make(chan struct{})
    var wg sync.WaitGroup
    wg.Add(3)

    // start in reverse order — still prints firstsecondthird
    go func() {
        defer wg.Done()
        <-g3
        fmt.Print("third")
    }()
    go func() {
        defer wg.Done()
        <-g2
        fmt.Print("second")
        close(g3)
    }()
    go func() {
        defer wg.Done()
        fmt.Print("first")
        close(g2)
    }()

    wg.Wait()
    fmt.Println()
}

Which primitive should you use?

For a fixed three-step pipeline, CountDownLatch is the clearest answer; channels are the idiomatic Go equivalent.

Time Complexity

O(1) per method call. await() blocks until the corresponding signal, but does no extra work.

Space Complexity

O(1) — only two latch objects are allocated.

Takeaways

• Use a one-shot synchronization aid when the ordering requirement is "wait for step N, then signal step N+1."
• CountDownLatch is a clean fit here because each transition happens exactly once.
• Always start the threads; the latches guarantee completion order even if startup order is different.
• Go dual: g2, g3 := make(chan struct{}), …; first closes g2; second receives then closes g3; third receives g3.
• Prove with reverse-start interleaving (T3/T2 block; T1 countDown; cascade).

Problem and solution structure adapted from DesignGurus. Re-authored and corrected for this guide.

When NOT to over-engineer Print-in-Order

• Production request path — this is a coordination drill, not a throughput pattern; prefer structured pipelines.
• Need multi-round cyclic barrier — WaitGroup/CountDownLatch one-shot is wrong; use CyclicBarrier/Phaser or re-Add carefully.

Interviewer follow-ups & drills

1. Why not sleep/retry? Timing hacks race under load; use happens-before via lock/sem/channel.
2. Failure: missed signal → permanent hang; always check condition in loop (spurious wakeups).
3. Drill: three threads first/second/third — show semaphore gate or channel handoff order.