Code Implementation

import threading

class FooBar:
    def __init__(self, n):
        self.n = n
        self.foo_sem = threading.Semaphore(1)
        self.bar_sem = threading.Semaphore(0)

    def foo(self, printFoo):
        for _ in range(self.n):
            self.foo_sem.acquire()
            printFoo()
            self.bar_sem.release()

    def bar(self, printBar):
        for _ in range(self.n):
            self.bar_sem.acquire()
            printBar()
            self.foo_sem.release()
      

#include <functional>
#include <semaphore.h>

class FooBar {
private:
    int n;
    sem_t foo_sem, bar_sem;
public:
    FooBar(int n) {
        this->n = n;
        sem_init(&foo_sem, 0, 1);
        sem_init(&bar_sem, 0, 0);
    }

    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            sem_wait(&foo_sem);
            printFoo();
            sem_post(&bar_sem);
        }
    }

    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            sem_wait(&bar_sem);
            printBar();
            sem_post(&foo_sem);
        }
    }
};
      

import java.util.concurrent.Semaphore;

class FooBar {
    private int n;
    private Semaphore fooSem = new Semaphore(1);
    private Semaphore barSem = new Semaphore(0);

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            fooSem.acquire();
            printFoo.run();
            barSem.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            barSem.acquire();
            printBar.run();
            fooSem.release();
        }
    }
}
      

class Semaphore {
    constructor(count) {
        this.count = count;
        this.queue = [];
    }
    async acquire() {
        if (this.count > 0) {
            this.count--;
        } else {
            await new Promise(resolve => this.queue.push(resolve));
        }
    }
    release() {
        if (this.queue.length > 0) {
            this.queue.shift()();
        } else {
            this.count++;
        }
    }
}

class FooBar {
    constructor(n) {
        this.n = n;
        this.fooSem = new Semaphore(1);
        this.barSem = new Semaphore(0);
    }

    async foo(printFoo) {
        for (let i = 0; i < this.n; i++) {
            await this.fooSem.acquire();
            printFoo();
            this.barSem.release();
        }
    }

    async bar(printBar) {
        for (let i = 0; i < this.n; i++) {
            await this.barSem.acquire();
            printBar();
            this.fooSem.release();
        }
    }
}
      

Problem Description

You are given an integer n. There are two functions, foo and bar, that should be called alternately by two separate threads, exactly n times each. The goal is to print "foo" and "bar" alternately, starting with "foo", so the output is foobarfoobar... repeated n times.

Each function receives a print method (printFoo or printBar) to output their respective strings. You must ensure the two threads coordinate so that "foo" is always printed before "bar" in each pair, and this alternation is maintained for all n cycles.

• Each thread calls its function exactly n times.
• The output must be strictly alternating: "foo" then "bar", repeated.
• Synchronization is required to prevent out-of-order prints.

Thought Process

At first glance, this problem looks simple: just print "foo" and "bar" alternately. But since two separate threads are involved, we need to synchronize their actions so that "foo" is always printed before "bar" in each cycle, and neither is printed out of order or more than required.

A naive approach would be to let both threads run and hope they alternate correctly, but thread scheduling is unpredictable—so this would fail. We need a mechanism to enforce the correct sequence.

There are several synchronization tools we might use, like locks, semaphores, or condition variables. The goal is to ensure:

• The "foo" thread prints, then signals the "bar" thread to print.
• The "bar" thread prints, then signals back to the "foo" thread for the next cycle.

Solution Approach

We solve this problem using two semaphores (or similar synchronization primitives):

1. Initialization:
   • Semaphore foo_sem is initialized to 1, allowing the "foo" thread to print first.
   • Semaphore bar_sem is initialized to 0, so the "bar" thread must wait.
2. foo() function:
   • Before printing "foo", acquire foo_sem (wait if not available).
   • Print "foo".
   • Release bar_sem to signal the "bar" thread to proceed.
3. bar() function:
   • Before printing "bar", acquire bar_sem (wait if not available).
   • Print "bar".
   • Release foo_sem to signal the "foo" thread for the next cycle.
4. Repeat for n times: Each function loops n times, ensuring strict alternation.

This approach works because only one thread can proceed at a time, and they always signal each other after printing. The semaphores act as "turn tokens" passed back and forth.

Example Walkthrough

Suppose n = 2. The goal is to print foobarfoobar.

1. First iteration:
   • "foo" thread starts, foo_sem = 1 (can proceed), bar_sem = 0 (blocked).
   • "foo" prints "foo", then releases bar_sem (bar_sem = 1).
   • "bar" thread now proceeds, prints "bar", releases foo_sem (foo_sem = 1).
2. Second iteration:
   • "foo" thread acquires foo_sem, prints "foo", releases bar_sem.
   • "bar" thread acquires bar_sem, prints "bar", releases foo_sem.
3. Result: The output is foobarfoobar, as required.

At each step, only the correct thread is allowed to print, and they alternate perfectly.

Time and Space Complexity

• Time Complexity:
  • Each thread prints n times, so the total work is O(n).
  • Semaphore operations are O(1), so the synchronization adds negligible overhead.
• Space Complexity:
  • We use a constant amount of extra space for semaphores and counters, so space is O(1).
• Brute-force Approach (Incorrect):
  • If we tried to print without synchronization, the output could be jumbled due to thread scheduling, and there would be no guarantee of alternation.
  • Synchronization is essential for correctness, not efficiency alone.

Summary

The "Print FooBar Alternately" problem is a classic threading synchronization exercise. By using two semaphores (or similar primitives), we can strictly control which thread prints at each step, ensuring the required alternation. This solution is elegant because it uses simple constructs to enforce a complex ordering, and it scales cleanly with the number of repetitions. The key insight is to think of synchronization as passing a "turn token" back and forth between threads, guaranteeing the correct sequence regardless of how the operating system schedules the threads.