Domain 2MediumMEDIUM

Print FooBar Alternately

LeetCode problem 1115: Print FooBar Alternately (medium).

Domain: medium•Updated: 2026-09-08
#Algorithms

Problem Breakdown

We need to coordinate two asynchronous threads running on a shared instance of FooBar. Thread A executes foo() and prints “foo”, while Thread B executes bar() and prints “bar”. The critical constraint is that they must alternate strictly: every iteration consists of printing “foo” followed immediately by “bar”, resulting in the string “foobar” repeated n times.

Inputs:

  • Integer n (number of iterations).
  • Two threads calling methods on a shared object instance.

Outputs:

  • A sequence where “foo” and “bar” are printed interleaved perfectly: "foobar" x n.

Implicit Constraints & Edge Cases:

  1. Concurrency Safety: Without synchronization, both threads could print simultaneously or out of order (e.g., bar before the first foo). We must prevent race conditions on shared state if any existed (though here we only care about output ordering).
  2. Deadlock Prevention: If Thread B calls bar() and waits for a signal that never comes, it hangs. Initialization of synchronization primitives is crucial to ensure progress regardless of thread scheduling priority at startup.
  3. Zero Iterations (n=0): The loops should simply not execute; no output required.

Intuition

A brute force approach where we just print inside the loop without coordination will fail because threads run independently and asynchronously. If Thread B runs before Thread A, it might try to print “bar” immediately, violating the order constraint. Even if they are synchronized with a simple lock, checking state (e.g., turn flag) requires careful logic to avoid busy-waiting or deadlocks.

Key Insight: We can model this as a producer-consumer problem where each thread passes control (“tokens”) to the other after completing its task. Using Semaphores is more idiomatic for “hand-off” synchronization than simple locks with flags, though both work. We initialize one semaphore (for foo) to allow it to run first immediately, and another (for bar) to 0 so that Thread B must wait until signaled by the completion of a previous iteration’s foo.

Optimal Approach: Use two semaphores:

  1. Initialize foo_sem with value 1 (allows immediate execution).
  2. Initialize bar_sem with value 0 (forces waiting initially).
  3. In each method, acquire the corresponding semaphore to ensure it’s your turn, print, then release the other thread’s semaphore to signal completion and allow the next step in the sequence.

Approach

  1. Setup: Create a FooBar class with an __init__ method that initializes two semaphores (foo_sem, bar_sem). Set foo_sem = Semaphore(1) so Thread A can start, and bar_sem = Semaphore(0) to enforce waiting for the first signal.
  2. Method Logic:
    • Inside foo(): Acquire foo_sem. Print “foo”. Release bar_sem (signal that it’s Bar’s turn).
    • Inside bar(): Acquire bar_sem. Print “bar”. Release foo_sem (signal back to Foo for the next iteration).
  3. Looping: Wrap this logic in a loop running from 0 to n-1 inside each method, ensuring exactly n pairs are printed across both threads combined.

Complexity Analysis

  • Time Complexity: O(n)O(n). Each of the two methods runs exactly nn times total (distributed between threads). The synchronization overhead is constant per iteration (O(1)O(1)), so linear time relative to n.
  • Space Complexity: O(1)O(1). We use a fixed number of semaphores and variables regardless of input size.

Solution

import threading

class FooBar:
    def __init__(self, n):
        self.n = n
        # Initialize two semaphores to control turn-taking between threads.
        # foo_sem starts at 1 so the 'foo' thread can run immediately on first call.
        # bar_sem starts at 0 so the 'bar' thread must wait for a signal from 'foo'.
        self.foo_semaphore = threading.Semaphore(1) 
        self.bar_semaphore = threading.Semaphore(0)

    def foo(self):
        """Thread A calls this method to print 'foo'."""
        for _ in range(self.n):
            # Wait until it is our turn (acquire token).
            self.foo_semaphore.acquire() 
            
            print("foo")  # Print "foo" safely
            
            # Signal that we are done, allowing Thread B ('bar') to proceed.
            self.bar_semaphore.release()

    def bar(self):
        """Thread B calls this method to print 'bar'."""
        for _ in range(self.n):
            # Wait until signaled by the previous 'foo'.
            self.bar_semaphore.acquire() 
            
            print("bar")  # Print "bar" safely
            
            # Signal back that we are done, allowing Thread A ('foo') to proceed.
            self.foo_semaphore.release()