Print FooBar Alternately - Video Solutions

Problem Overview: Two threads share a class. One thread prints "foo" and the other prints "bar". Your job is to coordinate them so the output becomes foobarfoobar... exactly n times. The challenge is pure thread synchronization: both threads run concurrently but must alternate execution.

Approach 1: Using Mutex Lock or Monitor (O(n) time, O(1) space)

This approach uses a shared lock and a state variable to control which thread prints next. Both threads acquire the same mutex. The foo() thread waits while it is not its turn, prints "foo", flips the state, and notifies the other thread. The bar() thread performs the symmetric operation. Monitor primitives such as synchronized, wait(), and notify() in Java or Condition/Lock patterns in Python ensure that only one thread proceeds at a time. Each iteration performs constant work, so total runtime is O(n) and memory usage remains O(1). This technique is common when solving coordination problems in concurrency or multithreading interviews.

Approach 2: Using Semaphores (O(n) time, O(1) space)

Semaphores provide a cleaner signaling mechanism between threads. Initialize two semaphores: one allowing the foo thread to run first (value 1) and another blocking the bar thread (value 0). The foo() thread acquires its semaphore, prints "foo", then releases the bar semaphore. The bar() thread acquires its semaphore, prints "bar", then releases the foo semaphore. This creates a strict alternating schedule enforced by semaphore permits. Each acquire/release operation is constant time, so the full execution still runs in O(n) time with O(1) additional space. Semaphores are widely used for ordered execution problems in concurrency and semaphores based synchronization.

Recommended for interviews: Interviewers usually expect the semaphore solution or a monitor-based lock solution. Implementing a mutex + condition variable shows you understand thread coordination primitives. The semaphore approach is often shorter and demonstrates strong knowledge of synchronization tools used in real systems.