LeetCode Solutions Blog

Print FooBar Alternately

Number: 1187

Difficulty: Medium

Paid? No

Companies: Apple

Problem Description

Given a class with two methods, foo() and bar(), two threads will call these methods concurrently. Modify the program so that by synchronizing the two threads, the output is "foobar" repeated n times (i.e., every time foo prints "foo" it is immediately followed by bar printing "bar").

Key Insights

You must enforce the order between the two threads: always printing "foo" before "bar" in each cycle.
Use synchronization primitives (mutexes, semaphores, condition variables) to alternate the control between the threads.
The solution typically involves initializing one thread to start (printing "foo") while the other waits until "foo" is printed.

Space and Time Complexity

Time Complexity: O(n) for n iterations. Space Complexity: O(1) additional space aside from synchronization primitives.

Solution

The solution uses synchronization tools (such as semaphores or condition variables) to coordinate the printing between two threads. One thread prints "foo" and then signals the other thread to print "bar". After printing "bar", the second thread signals back to allow the next "foo" to be printed. This alternation continues n times. The key is to ensure the correct order without busy-waiting, and the synchronization primitives used ensure that threads are blocked until they are allowed to proceed.

Code Solutions

import threading

class FooBar:
    def __init__(self, n):
        self.n = n
        # Initialize semaphore for foo with 1 permit (foo goes first)
        self.foo_semaphore = threading.Semaphore(1)
        # Initialize semaphore for bar with 0 permits so bar waits
        self.bar_semaphore = threading.Semaphore(0)

    # foo method accepts a function that prints "foo"
    def foo(self, printFoo):
        for _ in range(self.n):
            # Acquire permit for foo
            self.foo_semaphore.acquire()
            printFoo()  # Print "foo"
            # Release permit for bar so bar can print
            self.bar_semaphore.release()

    # bar method accepts a function that prints "bar"
    def bar(self, printBar):
        for _ in range(self.n):
            # Wait for foo to finish
            self.bar_semaphore.acquire()
            printBar()  # Print "bar"
            # Release permit for foo for next iteration
            self.foo_semaphore.release()

# The functions printFoo and printBar can be simple print statements.
def printFoo():
    print("foo", end="")

def printBar():
    print("bar", end="")

# Example usage:
n = 2
foobar = FooBar(n)
thread1 = threading.Thread(target=foobar.foo, args=(printFoo,))
thread2 = threading.Thread(target=foobar.bar, args=(printBar,))
thread1.start()
thread2.start()
thread1.join()
thread2.join()