Problem Description

You have a class FooBar with two methods: foo() and bar(). Each method prints its respective string ("foo" or "bar") n times in a loop.

Two separate threads will be created:

• Thread A will call the foo() method
• Thread B will call the bar() method

Both threads will run concurrently on the same instance of FooBar. Without synchronization, the output could be in any order (like "foofoofoobarbar" or "barbarfoofoo").

Your task is to modify the program using synchronization mechanisms to ensure that the output always alternates between "foo" and "bar", producing exactly "foobar" repeated n times. For example:

• If n = 1, the output should be: "foobar"
• If n = 2, the output should be: "foobarfoobar"
• If n = 3, the output should be: "foobarfoobarfoobar"

The solution uses two semaphores to coordinate the threads:

• Semaphore f (initialized to 1) controls when "foo" can be printed
• Semaphore b (initialized to 0) controls when "bar" can be printed

The synchronization works as follows:

1. Thread A acquires semaphore f, prints "foo", then releases semaphore b
2. Thread B acquires semaphore b, prints "bar", then releases semaphore f
3. This pattern repeats n times, ensuring strict alternation

The semaphores act as signals between threads - when one thread finishes printing, it signals the other thread that it's their turn to print. This guarantees the correct "foobar" pattern regardless of thread scheduling.

Intuition

When we have two threads that need to alternate their execution in a strict pattern, we need a way for them to communicate and coordinate. Think of it like two people taking turns speaking - one person needs to signal when they're done so the other knows it's their turn.

The key insight is that we need to enforce a specific ordering: "foo" must always come before "bar", and after "bar" is printed, "foo" can print again. This is a classic producer-consumer pattern where one thread produces a signal for the other to consume.

We can achieve this coordination using semaphores, which act like permission slips. A semaphore with value 1 means "you have permission to proceed," while a value of 0 means "you must wait."

Here's the reasoning:

1. Initially, we want "foo" to print first, so we give the foo thread permission to start (semaphore f = 1) while making the bar thread wait (semaphore b = 0).

2. After "foo" prints, it needs to tell "bar" that it's now bar's turn. This is done by releasing semaphore b (changing it from 0 to 1), giving the bar thread permission to proceed.

3. Similarly, after "bar" prints, it needs to tell "foo" that foo can go again. This is done by releasing semaphore f.

4. The acquire operations ensure that each thread waits for its turn - foo waits for semaphore f to be available, and bar waits for semaphore b to be available.

This creates a ping-pong effect: foo → signals bar → bar → signals foo → foo → signals bar... continuing for n iterations. The semaphores essentially create a token-passing mechanism where only the thread holding the token can execute, and after execution, it passes the token to the other thread.

Solution Approach

The implementation uses two semaphores to control the execution order of the threads. Let's walk through how this works:

Initialization:

• Create semaphore f with initial value 1 - this allows the foo thread to execute first
• Create semaphore b with initial value 0 - this blocks the bar thread initially

The foo method execution:

for _ in range(self.n):
    self.f.acquire()  # Wait for permission to print "foo"
    printFoo()        # Print "foo"
    self.b.release()  # Give permission for "bar" to print

1. self.f.acquire() - The thread attempts to acquire semaphore f. On the first iteration, f = 1, so it proceeds immediately and decrements f to 0. On subsequent iterations, it waits until the bar thread releases f.
2. printFoo() - Once acquired, it prints "foo"
3. self.b.release() - It then releases semaphore b, incrementing it from 0 to 1, signaling the bar thread that it can now proceed

The bar method execution:

for _ in range(self.n):
    self.b.acquire()  # Wait for permission to print "bar"
    printBar()        # Print "bar"
    self.f.release()  # Give permission for "foo" to print

1. self.b.acquire() - The thread attempts to acquire semaphore b. Initially b = 0, so it blocks until the foo thread releases b. Once available, it decrements b to 0.
2. printBar() - Once acquired, it prints "bar"
3. self.f.release() - It then releases semaphore f, incrementing it from 0 to 1, allowing the foo thread to proceed with its next iteration

Execution Flow for n = 2:

1. Initial state: f = 1, b = 0
2. Thread A (iteration 1): acquires f (now f = 0), prints "foo", releases b (now b = 1)
3. Thread B (iteration 1): acquires b (now b = 0), prints "bar", releases f (now f = 1)
4. Thread A (iteration 2): acquires f (now f = 0), prints "foo", releases b (now b = 1)
5. Thread B (iteration 2): acquires b (now b = 0), prints "bar", releases f (now f = 1)
6. Output: "foobarfoobar"

The semaphores create a strict alternation pattern where each thread must wait for the other to complete before proceeding, ensuring the output is always in the correct "foobar" order repeated n times.

Example Walkthrough

Let's walk through a concrete example with n = 2 to see how the semaphores coordinate the threads.

Initial Setup:

• Semaphore f = 1 (foo can start)
• Semaphore b = 0 (bar must wait)
• Thread A runs foo() method
• Thread B runs bar() method

Step-by-Step Execution:

Key Observations:

1. Thread A always waits for semaphore f before printing "foo"
2. Thread B always waits for semaphore b before printing "bar"
3. After printing, each thread signals the other by releasing the opposite semaphore
4. The initial values (f=1, b=0) ensure "foo" prints first
5. The alternating acquire/release pattern creates a handshake mechanism that enforces strict ordering

This synchronization guarantees that regardless of how the operating system schedules these threads, the output will always be "foobarfoobar" for n=2.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the parameter passed to the constructor. This is because both the foo and bar methods execute their loops exactly n times. Each iteration performs a constant amount of work - acquiring a semaphore, calling a print function, and releasing a semaphore are all O(1) operations. Therefore, the total time complexity is O(n) * O(1) = O(n).

The space complexity is O(1). The class only uses a fixed amount of extra space regardless of the input size n. It stores:

• One integer variable self.n
• Two semaphore objects self.f and self.b

The semaphores themselves use constant space as they only maintain internal state (counter and queue) that doesn't grow with n. The loop variables in both methods also use constant space. Since the space usage doesn't scale with the input size, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Semaphore Initialization Values

One of the most common mistakes is initializing both semaphores with the same value or swapping their initial values. This can lead to deadlock or incorrect output ordering.

Incorrect Implementation:

def __init__(self, n: int) -> None:
    self.n = n
    # Wrong: Both initialized to 1
    self.foo_semaphore = Semaphore(1)
    self.bar_semaphore = Semaphore(1)  # Should be 0!

Problem: If both semaphores start at 1, both threads can execute simultaneously on their first iteration, potentially producing "barfoo" instead of "foobar".

Another Incorrect Version:

def __init__(self, n: int) -> None:
    self.n = n
    # Wrong: Swapped initial values
    self.foo_semaphore = Semaphore(0)  # Should be 1!
    self.bar_semaphore = Semaphore(1)  # Should be 0!

Problem: This causes "bar" to print first, resulting in "barfoo" pattern instead of "foobar".

2. Swapping acquire() and release() Operations

Another critical mistake is confusing which semaphore to acquire versus which to release in each method.

Incorrect Implementation:

def foo(self, printFoo: Callable[[], None]) -> None:
    for _ in range(self.n):
        self.bar_semaphore.acquire()  # Wrong semaphore!
        printFoo()
        self.foo_semaphore.release()  # Wrong semaphore!

Problem: This creates a deadlock immediately. The foo thread tries to acquire a semaphore that starts at 0, blocking forever since only the bar thread can release it, but bar is also waiting.

3. Using a Single Semaphore

Some might attempt to use just one semaphore, thinking it's simpler.

Incorrect Implementation:

def __init__(self, n: int) -> None:
    self.n = n
    self.semaphore = Semaphore(1)

def foo(self, printFoo: Callable[[], None]) -> None:
    for _ in range(self.n):
        self.semaphore.acquire()
        printFoo()
        self.semaphore.release()

def bar(self, printBar: Callable[[], None]) -> None:
    for _ in range(self.n):
        self.semaphore.acquire()
        printBar()
        self.semaphore.release()

Problem: A single semaphore only provides mutual exclusion but doesn't enforce ordering. The output could be "foofoobarbar" or "barbarfoofoo" or any other combination.

4. Missing the Loop Structure

Forgetting that each method needs to execute n times, not just once.

Incorrect Implementation:

def foo(self, printFoo: Callable[[], None]) -> None:
    # Missing loop - only executes once!
    self.foo_semaphore.acquire()
    printFoo()
    self.bar_semaphore.release()

Problem: This would only print "foobar" once regardless of the value of n.

5. Race Condition in Initialization

While less common, attempting to use other synchronization primitives incorrectly:

Incorrect Implementation Using Lock:

def __init__(self, n: int) -> None:
    self.n = n
    self.lock = threading.Lock()
    self.turn = "foo"

def foo(self, printFoo: Callable[[], None]) -> None:
    for _ in range(self.n):
        while True:
            with self.lock:
                if self.turn == "foo":
                    printFoo()
                    self.turn = "bar"
                    break
            # Busy waiting - inefficient!

def bar(self, printBar: Callable[[], None]) -> None:
    for _ in range(self.n):
        while True:
            with self.lock:
                if self.turn == "bar":
                    printBar()
                    self.turn = "foo"
                    break
            # Busy waiting - inefficient!

Problem: While this might work, it uses busy-waiting (spinning), which wastes CPU cycles. Semaphores are more efficient as they block the thread properly.

Correct Solution Reminder:

The correct approach uses two semaphores with specific initial values:

• foo_semaphore starts at 1 (allowing foo to go first)
• bar_semaphore starts at 0 (forcing bar to wait)
• Each method acquires its own semaphore and releases the other's semaphore
• This creates a ping-pong effect ensuring strict alternation