LLD
Machine Coding
Interview Course
Java • Interview Prep
🧪 Concurrency Practice/

Print Sequence with Multiple Threads

Lesson 2 of 5
Prerequisites
ReentrantLock & Condition: Advanced Wait/Notify

Print Sequence with Multiple Threads

The Problem

Three threads must print numbers in strict sequence: Thread-1 prints 1, Thread-2 prints 2, Thread-3 prints 3, Thread-1 prints 4, Thread-2 prints 5, and so on, up to a given limit.

Output must be:

java
1Thread-1: 1
2Thread-2: 2
3Thread-3: 3
4Thread-1: 4
5Thread-2: 5
6Thread-3: 6
7...

The challenge: threads run concurrently, but must take turns in a fixed order. This is a classic interview coordination problem.

Let us See It Break

What if each thread just tries to print when it is "its turn" without proper synchronization?

java
1public class BrokenSequencePrinter {
2    private static int current = 1;
3    private static final int LIMIT = 15;
4
5    public static void main(String[] args) {
6        for (int threadId = 0; threadId < 3; threadId++) {
7            final int id = threadId;
8            new Thread(() -> {
9                while (current <= LIMIT) {
10                    if (current % 3 == id) {
11                        System.out.println("Thread-" + (id + 1) + ": " + current);
12                        current++;
13                    }
14                    // Busy-waiting with no synchronization
15                }
16            }, "Thread-" + (threadId + 1)).start();
17        }
18    }
19}

Run it. You might see:

  • Duplicated numbers (two threads read the same current)
  • Missing numbers (increment lost)
  • The program might never terminate (thread sees stale current due to CPU caching)

The third problem is the sneakiest. Without volatile or synchronization, a thread can cache current in a CPU register and spin forever, never seeing another thread's update.

Why It Breaks

Three issues at play:

  1. Visibility: Without volatile or a memory barrier, Thread-1 might increment current but Thread-2 never sees the new value. Each CPU core can cache variables locally.
  2. Atomicity: The check current % 3 == id and the increment current++ are separate operations. Between the check and the increment, another thread can sneak in.
  3. Busy-waiting: Even if it worked, spinning in a tight loop wastes CPU. We need threads to sleep until it is their turn.

Fix #1: The Simple Way (synchronized + wait/notify)

java
1public class SequenceWithWaitNotify {
2    private static int current = 1;
3    private static final int LIMIT = 15;
4    private static final Object lock = new Object();
5
6    public static void main(String[] args) {
7        for (int threadId = 0; threadId < 3; threadId++) {
8            final int id = threadId;
9            new Thread(() -> {
10                while (true) {
11                    synchronized (lock) {
12                        while (current <= LIMIT && current % 3 != id) {
13                            try {
14                                lock.wait();
15                            } catch (InterruptedException e) {
16                                Thread.currentThread().interrupt();
17                                return;
18                            }
19                        }
20                        if (current > LIMIT) {
21                            lock.notifyAll();
22                            return;
23                        }
24                        System.out.println("Thread-" + (id + 1) + ": " + current);
25                        current++;
26                        lock.notifyAll();
27                    }
28                }
29            }, "Thread-" + (threadId + 1)).start();
30        }
31    }
32}

The pattern is:

  1. Acquire the lock.
  2. While it is not my turn, wait (release the lock and sleep).
  3. When woken up, re-check the condition (this is why we use while, not if -- spurious wakeups are real).
  4. Do the work, then notifyAll so the next thread can check if it is its turn.

Note the id mapping: Thread-0 prints when current % 3 == 0, Thread-1 when current % 3 == 1, Thread-2 when current % 3 == 2. We start current = 1, so Thread-1 (id = 0, since 1 % 3 = 1) -- wait, that does not match. Let us fix the modular arithmetic:

java
1// Better mapping: thread prints when (current - 1) % 3 == id
2// current=1 -> (1-1)%3 = 0 -> Thread-0 prints (Thread-1)
3// current=2 -> (2-1)%3 = 1 -> Thread-1 prints (Thread-2)
4// current=3 -> (3-1)%3 = 2 -> Thread-2 prints (Thread-3)
5while (current <= LIMIT && (current - 1) % 3 != id) {
6    lock.wait();
7}

Fix #2: The Better Way (ReentrantLock + Condition)

With Condition objects, we can wake up only the specific thread that should go next, instead of waking everyone with notifyAll:

java
1import java.util.concurrent.locks.Condition;
2import java.util.concurrent.locks.ReentrantLock;
3
4public class SequenceWithCondition {
5    private static int current = 1;
6    private static final int LIMIT = 15;
7    private static final int NUM_THREADS = 3;
8    private static final ReentrantLock lock = new ReentrantLock();
9    private static final Condition[] conditions = new Condition[NUM_THREADS];
10
11    public static void main(String[] args) {
12        for (int i = 0; i < NUM_THREADS; i++) {
13            conditions[i] = lock.newCondition();
14        }
15
16        for (int threadId = 0; threadId < NUM_THREADS; threadId++) {
17            final int id = threadId;
18            new Thread(() -> {
19                while (true) {
20                    lock.lock();
21                    try {
22                        while (current <= LIMIT && (current - 1) % NUM_THREADS != id) {
23                            conditions[id].await();
24                        }
25                        if (current > LIMIT) {
26                            // Wake all threads so they can exit
27                            for (Condition c : conditions) {
28                                c.signal();
29                            }
30                            return;
31                        }
32                        System.out.println("Thread-" + (id + 1) + ": " + current);
33                        current++;
34                        // Signal only the NEXT thread
35                        int nextId = current <= LIMIT
36                                ? (current - 1) % NUM_THREADS
37                                : (id + 1) % NUM_THREADS;
38                        conditions[nextId].signal();
39                    } catch (InterruptedException e) {
40                        Thread.currentThread().interrupt();
41                        return;
42                    } finally {
43                        lock.unlock();
44                    }
45                }
46            }, "Thread-" + (threadId + 1)).start();
47        }
48    }
49}

Key improvement: Instead of notifyAll() waking all three threads (two of which just go back to sleep), we signal exactly the one thread that should go next. This is more efficient when you have many threads.

Fix #3: The Java Way (Semaphores)

Each thread has its own semaphore. Only the "current" thread's semaphore has a permit:

java
1import java.util.concurrent.Semaphore;
2
3public class SequenceWithSemaphores {
4    private static final int LIMIT = 15;
5    private static final int NUM_THREADS = 3;
6
7    public static void main(String[] args) {
8        Semaphore[] semaphores = new Semaphore[NUM_THREADS];
9        semaphores[0] = new Semaphore(1);  // Thread-1 starts
10        for (int i = 1; i < NUM_THREADS; i++) {
11            semaphores[i] = new Semaphore(0);  // Others blocked
12        }
13
14        for (int threadId = 0; threadId < NUM_THREADS; threadId++) {
15            final int id = threadId;
16            new Thread(() -> {
17                int num = id + 1;  // This thread prints id+1, id+4, id+7, ...
18                while (num <= LIMIT) {
19                    try {
20                        semaphores[id].acquire();  // Wait for my turn
21                    } catch (InterruptedException e) {
22                        Thread.currentThread().interrupt();
23                        return;
24                    }
25                    if (num <= LIMIT) {
26                        System.out.println("Thread-" + (id + 1) + ": " + num);
27                    }
28                    semaphores[(id + 1) % NUM_THREADS].release();  // Pass turn
29                    num += NUM_THREADS;
30                }
31            }, "Thread-" + (threadId + 1)).start();
32        }
33    }
34}

This is elegant: each thread acquires its own semaphore (blocking if no permit), does its work, then releases the next thread's semaphore. Like passing a baton in a relay race.

Step-by-Step Trace

Using the Semaphore approach, starting state: permits = [1, 0, 0]

StepThread-1Thread-2Thread-3Permits
1acquire(sem[0]) - gets permitblocked on sem[1]blocked on sem[2][0,0,0]
2prints "1"blockedblocked[0,0,0]
3release(sem[1])[0,1,0]
4blocked on sem[0]acquire(sem[1]) - gets permitblocked[0,0,0]
5blockedprints "2"blocked[0,0,0]
6blockedrelease(sem[2])[0,0,1]
7blockedblocked on sem[1]acquire(sem[2]) - gets permit[0,0,0]
8blockedblockedprints "3"[0,0,0]
9blockedblockedrelease(sem[0])[1,0,0]
10acquire(sem[0]) - gets permitblockedblocked[0,0,0]
11prints "4"blockedblocked[0,0,0]

The baton passes perfectly: 1 -> 2 -> 3 -> 1 -> 2 -> 3...

Common Mistakes

  • **Using if instead of while for the wait condition.** Spurious wakeups are real. Always re-check the condition after waking up.
  • **Using notify() instead of notifyAll() with wait/notify.** With notify(), the wrong thread might wake up, check the condition, go back to sleep, and now nobody is awake to make progress. Use notifyAll() unless you have exactly two threads.
  • Forgetting to handle the exit condition. If Thread-1 finishes and increments current past the limit, Thread-2 and Thread-3 might wait forever if nobody wakes them up.
  • Off-by-one in modular arithmetic. Double-check your mapping of thread IDs to turn numbers. A wrong modulus means one thread never gets a turn.

Interview Tip: This problem tests whether you understand thread coordination, not just mutual exclusion. The key insight is: threads must not only avoid racing, they must take turns in a specific order. Mention that Condition or Semaphore approaches are preferred because they avoid thundering-herd wakeups from notifyAll().

Try It Yourself

  1. Generalize to N threads. Make the number of threads configurable. Print 1 to 100 with 5 threads taking turns.
  2. Print Odd-Even. Two threads: one prints odd numbers, one prints even. 1,2,3,4,5,6... Use wait/notify.
  3. Print FizzBuzz with 4 threads. Thread-1 prints numbers, Thread-2 prints "Fizz", Thread-3 prints "Buzz", Thread-4 prints "FizzBuzz". Each thread only prints when it is supposed to.

Summary

  • Thread coordination requires both mutual exclusion AND a signaling mechanism.
  • wait/notify is the basic tool. Always use while loops for the condition check.
  • Condition objects let you signal specific threads instead of waking all of them.
  • Semaphores model turn-taking naturally: acquire your permit, release the next thread's permit.
Home