Problem 41.1 · Concurrency-Aware Data StructuresEasy

Print in Order

What it teaches: Ordering threads with latches (or semaphores), whatever order they start in.

Practise it on judges as “Print in Order”.

In plain words

Three runners must pass a baton: runner 2 can't start until runner 1 hands it over, and runner 3 waits for runner 2. They may arrive at the track in any order, but the race still goes 1, 2, 3. In code, the batons are semaphores that start empty: a thread that asks for an empty one waits until the thread before it puts one in.

Return the combined output, which must always be "firstsecondthird". Example: order = [3, 1, 2] → "firstsecondthird".

The problem

Three tasks print "first", "second" and "third". They are started on three threads in the order given by order (a permutation of 1, 2, 3). Make sure the output is always "firstsecondthird", and return it.

Example 1

Input: order = [3, 1, 2]
Output: "firstsecondthird"

Constraints

order is a permutation of [1, 2, 3]

Pattern clues in the wording

→ Threads must run in a fixed sequence

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;
import java.util.concurrent.*;

class Solution {
    public String printInOrder(int[] order) throws InterruptedException {
        return "";
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	order = [1,2,3]	"firstsecondthird"
2	order = [3,1,2]	"firstsecondthird"

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Two latches · O(1)2. Semaphores with zero permits · O(1)

Two latches

Time O(1) Space O(1)

firstDone and secondDone latches; second awaits firstDone, third awaits secondDone. Start threads in the given order, join all, return the buffer.

Approach 1

import java.util.*;
import java.util.concurrent.CountDownLatch;

class Solution {
    public String printInOrder(int[] order) throws InterruptedException {
        StringBuffer out = new StringBuffer();                    // thread-safe appends
        CountDownLatch firstDone = new CountDownLatch(1), secondDone = new CountDownLatch(1);
        Runnable[] jobs = {
            () -> { out.append("first"); firstDone.countDown(); },
            () -> { await(firstDone); out.append("second"); secondDone.countDown(); },
            () -> { await(secondDone); out.append("third"); },
        };
        List<Thread> threads = new ArrayList<>();
        for (int k : order) {
            Thread t = new Thread(jobs[k - 1]);
            threads.add(t);
            t.start();
        }
        for (Thread t : threads) t.join();
        return out.toString();
    }

    private static void await(CountDownLatch latch) {
        try { latch.await(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }
}

Verdict: Latches are made for "wait until X happened".

Semaphores with zero permits

Time O(1) Space O(1)

Two semaphores starting at 0; a task releases the next one's permit after printing.

▶ Dry run: Two semaphores that start at zeroorder = [3, 1, 2] (one possible timing)

threads(map)

third: waiting on toThird

semaphores(vars)

toSecond: 0toThird: 0

out(list)

empty

Step 1/4The thread for job 3 is started first. It asks toThird for a permit, there are none, so it blocks.

Approach 2

import java.util.*;
import java.util.concurrent.Semaphore;

class Solution {
    public String printInOrder(int[] order) throws InterruptedException {
        StringBuffer out = new StringBuffer();
        Semaphore toSecond = new Semaphore(0), toThird = new Semaphore(0);
        Runnable[] jobs = {
            () -> { out.append("first"); toSecond.release(); },
            () -> { toSecond.acquireUninterruptibly(); out.append("second"); toThird.release(); },
            () -> { toThird.acquireUninterruptibly(); out.append("third"); },
        };
        List<Thread> threads = new ArrayList<>();
        for (int k : order) {
            Thread t = new Thread(jobs[k - 1]);
            threads.add(t);
            t.start();
        }
        for (Thread t : threads) t.join();
        return out.toString();
    }
}

Verdict: Same idea; semaphores can be reused, latches can't.

Before you submit

Edge cases and common mistakes

Test these inputs

Threads started in reverse order

Mistakes people make

Busy-waiting on a plain boolean (wastes CPU and may never see the update without volatile).

Interview

Follow-up questions

Why StringBuffer and not StringBuilder?