Print in Order - Practice Coding Problems

Print in Order - Problem

Concurrency Easy

Suppose we have a class with three methods that print specific messages:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

The same instance of Foo will be passed to three different threads:

Thread A will call first()
Thread B will call second()
Thread C will call third()

Design a mechanism to ensure that second() is executed after first(), and third() is executed after second(), regardless of thread scheduling order.

Note: We do not know how the threads will be scheduled by the operating system. The input format ensures comprehensive testing of your synchronization mechanism.

Input & Output

Example 1 — Standard Execution

$ Input: n = 1

› Output: firstsecondthird

💡 Note: Thread A executes first(), signals Thread B to execute second(), which then signals Thread C to execute third(). The output is always in the correct order regardless of thread scheduling.

Example 2 — Different Thread Start Order

$ Input: n = 1

› Output: firstsecondthird

💡 Note: Even if Thread C starts first, it must wait for Thread B. Thread B must wait for Thread A. The synchronization ensures the output is always firstsecondthird.

Example 3 — Concurrent Start

$ Input: n = 1

› Output: firstsecondthird

💡 Note: All threads start simultaneously, but synchronization primitives ensure first() completes before second(), and second() before third().

Constraints

The same instance of Foo will be passed to three different threads
Thread A will call first()
Thread B will call second()
Thread C will call third()
We cannot control thread scheduling order

Visualization

Tap to expand

Understanding the Visualization

Input

Three threads A, B, C ready to execute

Synchronization

Coordination ensures proper execution order

Output

Always produces 'firstsecondthird'

Key Takeaway

🎯 Key Insight: Thread synchronization primitives ensure execution order despite unpredictable scheduling

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Meta 18

This concurrency problem requires thread synchronization to ensure methods execute in a specific order. The key insight is using semaphores or similar primitives to coordinate execution instead of inefficient busy waiting. Best approach uses semaphores for clean coordination. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Busy Waiting with Flags	O(1)	O(1)	Use boolean flags with busy waiting loops
Semaphore Synchronization	O(1)	O(1)	Use semaphores for efficient thread coordination

Busy Waiting with Flags — Algorithm Steps

Step 1: Initialize flags for first and second completion
Step 2: Each method waits in a loop until its turn
Step 3: Set completion flag after executing

Visualization

Tap to expand

Step-by-Step Walkthrough

Thread Start

All threads start but wait for their turn

Flag Checking

Threads loop checking completion flags

Sequential Execution

Methods execute in order: first→second→third

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <string.h>

typedef struct {
    int firstDone;
    int secondDone;
    char result[20];
    int pos;
} Foo;

Foo* foo;

void printFirst() {
    strcpy(foo->result + foo->pos, "first");
    foo->pos += 5;
}

void printSecond() {
    strcpy(foo->result + foo->pos, "second");
    foo->pos += 6;
}

void printThird() {
    strcpy(foo->result + foo->pos, "third");
    foo->pos += 5;
}

void* first(void* arg) {
    printFirst();
    foo->firstDone = 1;
    return NULL;
}

void* second(void* arg) {
    while (!foo->firstDone) {
        usleep(1000);
    }
    printSecond();
    foo->secondDone = 1;
    return NULL;
}

void* third(void* arg) {
    while (!foo->secondDone) {
        usleep(1000);
    }
    printThird();
    return NULL;
}

char* solution(int n) {
    foo = malloc(sizeof(Foo));
    foo->firstDone = 0;
    foo->secondDone = 0;
    foo->pos = 0;
    memset(foo->result, 0, 20);
    
    pthread_t threads[3];
    pthread_create(&threads[0], NULL, first, NULL);
    pthread_create(&threads[1], NULL, second, NULL);
    pthread_create(&threads[2], NULL, third, NULL);
    
    for (int i = 0; i < 3; i++) {
        pthread_join(threads[i], NULL);
    }
    
    return foo->result;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%s\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Each method executes once, but with potential waiting time

✓ Linear Growth

Space Complexity

O(1)

Only uses two boolean flags for synchronization

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Busy Waiting with Flags — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler