How do you solve Print FooBar Alternately on LeetCode?

Print FooBar Alternately (LeetCode #1115) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding thread synchronization is crucial for concurrent programming.

What is the time complexity of Print FooBar Alternately?

The optimal solution for Print FooBar Alternately runs in O(n) time and uses O(1) space. The complexity is O(n) because each thread runs in a loop n times and they alternate without unnecessary waiting.

What is the brute force solution for Print FooBar Alternately?

The brute force approach for Print FooBar Alternately is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we can use two threads that simply print 'foo' and 'bar' in a loop. However, without proper synchronization, we cannot guarantee that 'foo' and 'bar' will alternate correctly. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Print FooBar Alternately?

Print FooBar Alternately uses the following concepts: Concurrency. The recommended patterns to study are: Concurrency, Thread Synchronization.

What are the interview tips for Print FooBar Alternately?

Explain your thought process clearly when discussing concurrency. Be prepared to discuss potential race conditions and how to avoid them. Practice coding thread synchronization problems before the interview.

What are common mistakes when solving Print FooBar Alternately?

Not using synchronization mechanisms, leading to race conditions. Failing to handle thread waiting and notification properly.

#1115

Print FooBar Alternately

Medium

ConcurrencyConcurrencyThread Synchronization

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses synchronization mechanisms to ensure that 'foo' and 'bar' are printed in the correct order without unnecessary waiting. This is achieved through mutex locks and condition variables.

⚙️

Algorithm

4 steps

1Step 1: Initialize a mutex and a condition variable to control access.
2Step 2: Use a boolean flag to track whose turn it is.
3Step 3: In the foo() method, print 'foo' and notify the bar() method.
4Step 4: In the bar() method, wait for the signal from foo() before printing 'bar'.

solution.py26 lines

1import threading
2
3class FooBar:
4    def __init__(self, n):
5        self.n = n
6        self.lock = threading.Lock()
7        self.condition = threading.Condition()
8        self.foo_turn = True
9
10    def foo(self):
11        for _ in range(self.n):
12            with self.condition:
13                while not self.foo_turn:
14                    self.condition.wait()
15                print('foo', end='')
16                self.foo_turn = False
17                self.condition.notify_all()
18
19    def bar(self):
20        for _ in range(self.n):
21            with self.condition:
22                while self.foo_turn:
23                    self.condition.wait()
24                print('bar', end='')
25                self.foo_turn = True
26                self.condition.notify_all()

ℹ

Complexity note: The complexity is O(n) because each thread runs in a loop n times and they alternate without unnecessary waiting.

1Understanding thread synchronization is crucial for concurrent programming.
2Using condition variables can greatly simplify the control flow between threads.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.