LeetCode 1115 - Print FooBar Alternately

This problem is a classic concurrency synchronization task. We are given a class FooBar with two methods, foo() and bar().

leetcodemediumconcurrency

LeetCode Problem 1115

Difficulty: 🟡 Medium
Topics: Concurrency

Solution

Problem Understanding

This problem is a classic concurrency synchronization task. We are given a class FooBar with two methods, foo() and bar(). Each method is executed by a separate thread:

  • Thread A repeatedly calls foo()
  • Thread B repeatedly calls bar()

The goal is to ensure the output sequence becomes:

foobarfoobarfoobar...

exactly n times.

The challenge is that threads execute asynchronously. Without synchronization, the operating system scheduler may run one thread much faster than the other. For example, the foo() thread might print all "foo" values before the bar() thread runs at all, producing incorrect output like:

foofoofoobarbarbar

instead of:

foobarfoobarfoobar

The problem is therefore not about computation or data processing, but about coordinating execution order between threads.

The input consists of a single integer n, which specifies how many times the combined sequence "foobar" must appear. The expected output is an alternating pattern where every "foo" is immediately followed by "bar".

The constraints are small:

1 <= n <= 1000

This tells us performance is not the difficult part. The important challenge is correctness under concurrent execution. Even though n is small, thread synchronization bugs can still occur if the implementation is not carefully designed.

A few important observations emerge immediately:

  • The foo() method must always execute before the corresponding bar() call in each iteration.
  • The two threads must coordinate repeatedly, not just once.
  • The solution must avoid race conditions.
  • The solution must not deadlock, meaning both threads waiting forever.
  • The output order must remain deterministic despite nondeterministic thread scheduling.

Edge cases mainly involve synchronization behavior:

  • n = 1, the smallest valid input, still requires strict ordering.
  • Fast execution by one thread should not break ordering.
  • Repeated alternation across many iterations must remain correct.

Approaches

Brute Force Approach

A brute force idea would be to let both threads run independently and attempt to rely on timing or busy waiting to preserve ordering.

For example, one could repeatedly check a shared variable in a loop:

while turn != "foo":
    pass

and similarly for "bar".

This technically works if implemented carefully, because each thread waits until it is its turn before printing. However, this approach wastes CPU cycles because the thread continuously spins while waiting. This is known as busy waiting or spin locking.

Busy waiting is inefficient because the processor repeatedly checks a condition instead of sleeping until notified. In real systems, this can severely degrade performance.

Another poor brute force strategy would be inserting artificial delays using sleep(). This is unreliable because thread scheduling timing is nondeterministic and depends on the operating system.

Optimal Approach

The correct solution uses synchronization primitives designed specifically for thread coordination.

A semaphore is an ideal choice here. A semaphore maintains an internal counter:

  • If the counter is positive, a thread may proceed.
  • If the counter is zero, the thread blocks until another thread releases the semaphore.

We use two semaphores:

  • One controls when foo() may execute.
  • One controls when bar() may execute.

Initially:

  • fooSemaphore = 1
  • barSemaphore = 0

This means:

  • foo() is allowed to run first.
  • bar() is blocked initially.

After foo() prints "foo", it signals bar() by releasing the second semaphore.

After bar() prints "bar", it signals foo() by releasing the first semaphore.

This creates a strict alternating execution pattern.

The major insight is that synchronization primitives allow threads to sleep efficiently while waiting, rather than continuously consuming CPU time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Uses busy waiting or timing hacks, inefficient and unreliable
Optimal O(n) O(1) Uses semaphores for precise thread synchronization

Algorithm Walkthrough

  1. Create two synchronization primitives, one for the foo() thread and one for the bar() thread.
  2. Initialize the semaphore controlling foo() with value 1. This allows the foo() thread to execute immediately.
  3. Initialize the semaphore controlling bar() with value 0. This forces the bar() thread to wait initially.
  4. Inside foo():
  • Before printing, acquire the foo semaphore.
  • If the semaphore is unavailable, the thread blocks automatically.
  • Print "foo".
  • Release the bar semaphore so the bar() thread may proceed.
  1. Inside bar():
  • Acquire the bar semaphore.
  • This guarantees "foo" has already been printed for the current iteration.
  • Print "bar".
  • Release the foo semaphore so the next "foo" may execute.
  1. Repeat this process exactly n times in both threads.

The semaphores enforce a strict alternating execution order:

foo -> bar -> foo -> bar

regardless of thread scheduling order.

Why it works

The key invariant is:

Only one thread is allowed to proceed at a time.

Initially, only foo() may run because its semaphore count is positive. After printing, foo() transfers execution permission to bar() by releasing the second semaphore.

Similarly, bar() transfers permission back to foo() after printing.

Because execution permission alternates after every print operation, the output must always follow the exact sequence:

foobarfoobar...

No race condition can violate this ordering because the semaphores serialize execution.

Python Solution

from threading import Semaphore
from typing import Callable

class FooBar:
    def __init__(self, n: int):
        self.n = n
        self.foo_semaphore = Semaphore(1)
        self.bar_semaphore = Semaphore(0)

    def foo(self, printFoo: 'Callable[[], None]') -> None:

        for _ in range(self.n):
            self.foo_semaphore.acquire()

            # printFoo() outputs "foo". Do not change or remove this line.
            printFoo()

            self.bar_semaphore.release()

    def bar(self, printBar: 'Callable[[], None]') -> None:

        for _ in range(self.n):
            self.bar_semaphore.acquire()

            # printBar() outputs "bar". Do not change or remove this line.
            printBar()

            self.foo_semaphore.release()

The constructor initializes two semaphores.

self.foo_semaphore = Semaphore(1)

allows the foo() thread to start immediately.

self.bar_semaphore = Semaphore(0)

forces the bar() thread to wait until "foo" has been printed.

Inside foo(), the thread first acquires its semaphore. Once permitted, it prints "foo" and then releases the bar semaphore. This wakes the bar() thread.

Inside bar(), the reverse process occurs. The thread waits until foo() signals it, prints "bar", and then releases the foo semaphore for the next iteration.

The implementation directly mirrors the synchronization strategy described in the algorithm walkthrough.

Go Solution

package main

import "sync"

type FooBar struct {
	n       int
	fooChan chan struct{}
	barChan chan struct{}
}

func NewFooBar(n int) *FooBar {
	fb := &FooBar{
		n:       n,
		fooChan: make(chan struct{}, 1),
		barChan: make(chan struct{}, 1),
	}

	fb.fooChan <- struct{}{}

	return fb
}

func (fb *FooBar) Foo(printFoo func()) {
	for i := 0; i < fb.n; i++ {
		<-fb.fooChan

		// printFoo() outputs "foo". Do not change or remove this line.
		printFoo()

		fb.barChan <- struct{}{}
	}
}

func (fb *FooBar) Bar(printBar func()) {
	for i := 0; i < fb.n; i++ {
		<-fb.barChan

		// printBar() outputs "bar". Do not change or remove this line.
		printBar()

		fb.fooChan <- struct{}{}
	}
}

Go does not have built in semaphores in the standard library, so buffered channels are commonly used for synchronization.

The channels behave similarly to semaphores:

  • Receiving from a channel blocks until a value is available.
  • Sending to a full buffered channel blocks until space exists.

The fooChan channel starts with one token, allowing Foo() to execute first. The barChan starts empty, forcing Bar() to wait.

After each print operation, execution permission is transferred by sending a token to the other channel.

Unlike Python, Go uses channels as a first class concurrency primitive, which makes the implementation concise and idiomatic.

Worked Examples

Example 1

Input:

n = 1

Initial semaphore state:

Semaphore Value
foo 1
bar 0

Execution trace:

Step Thread Action foo Semaphore bar Semaphore Output
1 foo acquire foo 0 0 ""
2 foo print "foo" 0 0 "foo"
3 foo release bar 0 1 "foo"
4 bar acquire bar 0 0 "foo"
5 bar print "bar" 0 0 "foobar"
6 bar release foo 1 0 "foobar"

Final output:

foobar

Example 2

Input:

n = 2

Execution trace:

Iteration Thread Output After Step
1 foo "foo"
1 bar "foobar"
2 foo "foobarfoo"
2 bar "foobarfoobar"

Final output:

foobarfoobar

The semaphores continue alternating correctly across multiple iterations.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each thread performs exactly n synchronization and print operations
Space O(1) Only a constant number of synchronization primitives are stored

The time complexity is linear because each iteration performs a fixed amount of work. Semaphore operations are constant time.

The space complexity remains constant because the algorithm only stores two synchronization objects regardless of n.

Test Cases

import threading

def run_test(n):
    output = []

    def printFoo():
        output.append("foo")

    def printBar():
        output.append("bar")

    fb = FooBar(n)

    thread1 = threading.Thread(target=fb.foo, args=(printFoo,))
    thread2 = threading.Thread(target=fb.bar, args=(printBar,))

    thread1.start()
    thread2.start()

    thread1.join()
    thread2.join()

    return "".join(output)

assert run_test(1) == "foobar"  # minimum valid input
assert run_test(2) == "foobarfoobar"  # basic alternating behavior
assert run_test(3) == "foobarfoobarfoobar"  # multiple alternations
assert run_test(5) == "foobar" * 5  # repeated synchronization
assert run_test(10) == "foobar" * 10  # larger iteration count
assert len(run_test(100)) == 600  # stress test for repeated execution
assert run_test(100).startswith("foobar")  # ordering preserved at start
assert run_test(100).endswith("foobar")  # ordering preserved at end
Test Why
n = 1 Validates smallest input
n = 2 Verifies basic alternation
n = 3 Ensures repeated synchronization works
n = 5 Tests multiple thread handoffs
n = 10 Checks stability over more iterations
n = 100 length check Stress tests concurrency coordination
startswith("foobar") Verifies correct initial ordering
endswith("foobar") Verifies correct final ordering

Edge Cases

One important edge case is the smallest possible input:

n = 1

Even with only one iteration, synchronization is still required. Without proper coordination, the bar() thread could theoretically attempt to print first. The semaphore initialization guarantees that foo() always executes before bar().

Another important edge case occurs when one thread runs significantly faster than the other. For example, the foo() thread might repeatedly attempt to execute before bar() has completed. Without synchronization, this could produce outputs like:

foofoofoo...

The semaphore blocks the fast thread until the slower thread finishes its turn, ensuring correct alternation regardless of scheduling speed.

A third important edge case involves many iterations, such as:

n = 1000

Repeated synchronization can expose deadlock bugs if semaphore releases are forgotten or misplaced. The implementation carefully releases the opposite semaphore after every successful print operation, guaranteeing progress throughout all iterations.