Print FooBar Alternately - Practice Coding Problems

Print FooBar Alternately - Problem

Concurrency Medium

You are given a FooBar class with two methods:

foo() - prints "foo" n times
bar() - prints "bar" n times

The same instance of FooBar will be passed to two different threads:

Thread A will call foo()
Thread B will call bar()

Your task: Modify the program so that the output is "foobar" repeated n times (alternating "foo" and "bar").

For example, if n = 3, the output should be: foobarfoobarfoobar

Input & Output

Example 1 — Basic Case

$ Input: n = 1

› Output: foobar

💡 Note: Thread A prints 'foo' once, Thread B prints 'bar' once, alternating to produce 'foobar'

Example 2 — Multiple Iterations

$ Input: n = 2

› Output: foobarfoobar

💡 Note: Pattern repeats: foo-bar-foo-bar, creating 'foobarfoobar'

Example 3 — Larger Input

$ Input: n = 3

› Output: foobarfoobarfoobar

💡 Note: Three complete alternations: foo-bar-foo-bar-foo-bar

Constraints

1 ≤ n ≤ 1000
The same instance of FooBar is passed to two different threads
Thread A calls foo(), Thread B calls bar()
Output must be exactly 'foobar' repeated n times

Visualization

Tap to expand

Understanding the Visualization

Input

n=2 (repeat foobar 2 times)

Process

Thread A prints foo, Thread B prints bar, alternating

Output

foobarfoobar (perfect alternation)

Key Takeaway

🎯 Key Insight: Thread synchronization is essential to prevent race conditions and ensure correct alternating output

Asked in

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

The key insight is that two threads need synchronized turn-taking to produce alternating output. The semaphore approach is optimal as it avoids CPU waste from busy waiting. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Semaphore Synchronization	O(n)	O(1)	Use two semaphores to signal when each thread can proceed
Busy Waiting with Volatile Flag	O(n)	O(1)	Use a volatile boolean flag with busy waiting to coordinate turns

Semaphore Synchronization — Algorithm Steps

Step 1: Initialize fooSema=1, barSema=0
Step 2: foo() acquires fooSema, prints, releases barSema
Step 3: bar() acquires barSema, prints, releases fooSema

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

fooSema=1, barSema=0

Signal

foo acquires, prints, signals bar

Alternate

bar acquires, prints, signals foo

Code -

solution.c — C

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

typedef struct {
    int n;
    sem_t fooSema;
    sem_t barSema;
    char* result;
    int pos;
    pthread_mutex_t mutex;
} FooBar;

typedef struct {
    FooBar* foobar;
    int isFoo;
} ThreadData;

void* fooThread(void* arg) {
    ThreadData* data = (ThreadData*)arg;
    FooBar* fb = data->foobar;
    
    for (int i = 0; i < fb->n; i++) {
        sem_wait(&fb->fooSema);
        pthread_mutex_lock(&fb->mutex);
        strcat(fb->result + fb->pos, "foo");
        fb->pos += 3;
        pthread_mutex_unlock(&fb->mutex);
        sem_post(&fb->barSema);
    }
    return NULL;
}

void* barThread(void* arg) {
    ThreadData* data = (ThreadData*)arg;
    FooBar* fb = data->foobar;
    
    for (int i = 0; i < fb->n; i++) {
        sem_wait(&fb->barSema);
        pthread_mutex_lock(&fb->mutex);
        strcat(fb->result + fb->pos, "bar");
        fb->pos += 3;
        pthread_mutex_unlock(&fb->mutex);
        sem_post(&fb->fooSema);
    }
    return NULL;
}

char* solution(int n) {
    FooBar* foobar = malloc(sizeof(FooBar));
    foobar->n = n;
    foobar->result = calloc(6 * n + 1, sizeof(char));
    foobar->pos = 0;
    
    sem_init(&foobar->fooSema, 0, 1);
    sem_init(&foobar->barSema, 0, 0);
    pthread_mutex_init(&foobar->mutex, NULL);
    
    ThreadData data1 = {foobar, 1};
    ThreadData data2 = {foobar, 0};
    
    pthread_t t1, t2;
    pthread_create(&t1, NULL, fooThread, &data1);
    pthread_create(&t2, NULL, barThread, &data2);
    
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    
    char* result = strdup(foobar->result);
    
    sem_destroy(&foobar->fooSema);
    sem_destroy(&foobar->barSema);
    pthread_mutex_destroy(&foobar->mutex);
    free(foobar->result);
    free(foobar);
    
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each thread prints n times with O(1) semaphore operations

✓ Linear Growth

Space Complexity

O(1)

Only uses two semaphore objects

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 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

Semaphore Synchronization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler