Print FooBar Alternately Problem

Problem

Suppose you are given the following code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

The same instance of FooBar will be passed to two different threads:

thread A will call foo(), while
thread B will call bar().

Modify the given program to output "foobar" n times.

Examples

Example 1:

1
2
3
4


Input: n = 1
Output: "foobar"
Explanation: There are two threads being fired asynchronously. One of them calls foo(), while the other calls bar().
"foobar" is being output 1 time.

Example 2:

1
2
3


Input: n = 2
Output: "foobarfoobar"
Explanation: "foobar" is being output 2 times.

Initial Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class FooBar {
    private int n;

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            
            // printFoo.run() outputs "foo". Do not change or remove this line.
            printFoo.run();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            
            // printBar.run() outputs "bar". Do not change or remove this line.
            printBar.run();
        }
    }
}

Solution

Overall,solution 2(lock+condition) performs better:

comparing to solution 1,solution 2 using more waiting queues to avoid unnecessary notify, reduce lock competition.
comparing to solution 3 and solution 4,solution 2 using synchronization queue to avoid unnecessary cpu execution.
Method 1-4 are using loops. We can avoid looping constructs to solve concurrency problems. Java provides many different constructs (semaphores, phasers, locks, etc.) that can avoid looping.

Method 1 - Synchronized (Monitor Wait/Notify)

Intuition

We use a shared flag and synchronized blocks to coordinate two threads so that “foo” and “bar” are printed alternately. The flag indicates whose turn it is, and threads wait for their turn using wait() and notify the other using notifyAll().

Approach

Use a shared flag variable: 0 for “foo” turn, 1 for “bar” turn.
In each thread, loop n times and use a synchronized block on the shared object.
If it’s not the thread’s turn, call wait() to release the lock and wait.
When it’s the thread’s turn, print and update the flag, then call notifyAll() to wake up the other thread.
Repeat until both threads have printed n times.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


public class FooBarSynchronized {
    private int n;
    private int flag = 0;

    public FooBarSynchronized(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            synchronized (this) {
                while (flag == 1) {
                    this.wait();
                }
                printFoo.run();
                flag = 1;
                this.notifyAll();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            synchronized (this) {
                while (flag == 0) {
                    this.wait();
                }
                printBar.run();
                flag = 0;
                this.notifyAll();
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class FooBarSynchronized(private val n: Int) {
    private var flag = 0

    @Synchronized
    fun foo(printFoo: () -> Unit) {
        repeat(n) {
            synchronized(this) {
                while (flag == 1) {
                    (this as java.lang.Object).wait()
                }
                printFoo()
                flag = 1
                (this as java.lang.Object).notifyAll()
            }
        }
    }

    @Synchronized
    fun bar(printBar: () -> Unit) {
        repeat(n) {
            synchronized(this) {
                while (flag == 0) {
                    (this as java.lang.Object).wait()
                }
                printBar()
                flag = 0
                (this as java.lang.Object).notifyAll()
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


import threading

class FooBarSynchronized:
    def __init__(self, n: int):
        self.n = n
        self.flag = 0
        self.lock = threading.Condition()

    def foo(self, printFoo):
        for _ in range(self.n):
            with self.lock:
                while self.flag == 1:
                    self.lock.wait()
                printFoo()
                self.flag = 1
                self.lock.notify_all()

    def bar(self, printBar):
        for _ in range(self.n):
            with self.lock:
                while self.flag == 0:
                    self.lock.wait()
                printBar()
                self.flag = 0
                self.lock.notify_all()

Complexity

⏰ Time complexity: O(n) — Each thread prints n times, and each print is O(1).
🧺 Space complexity: O(1) — Only a few variables are used for synchronization.

Method 2 - Lock and Condition Variables

Intuition

We use a reentrant lock and two condition variables to coordinate the threads. Each thread waits on its own condition until it’s their turn, then signals the other thread after printing. This reduces lock contention and avoids unnecessary wakeups.

Approach

Use a shared flag variable: 0 for “foo” turn, 1 for “bar” turn.
Use a ReentrantLock and two Condition objects, one for each thread.
In each thread, loop n times and acquire the lock.
If it’s not the thread’s turn, call await() on its condition.
When it’s the thread’s turn, print and update the flag, then signal the other thread’s condition and release the lock.
Repeat until both threads have printed n times.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

class FooBarLock {
    private int n;
    private int flag = 0;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition fooCond = lock.newCondition();
    private final Condition barCond = lock.newCondition();

    public FooBarLock(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            lock.lock();
            try {
                while (flag == 1) {
                    barCond.await();
                }
                printFoo.run();
                flag = 1;
                fooCond.signalAll();
            } finally {
                lock.unlock();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            lock.lock();
            try {
                while (flag == 0) {
                    fooCond.await();
                }
                printBar.run();
                flag = 0;
                barCond.signalAll();
            } finally {
                lock.unlock();
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


import java.util.concurrent.locks.ReentrantLock
import java.util.concurrent.locks.Condition

class FooBarLock(private val n: Int) {
    private var flag = 0
    private val lock = ReentrantLock()
    private val fooCond: Condition = lock.newCondition()
    private val barCond: Condition = lock.newCondition()

    fun foo(printFoo: () -> Unit) {
        repeat(n) {
            lock.lock()
            try {
                while (flag == 1) {
                    barCond.await()
                }
                printFoo()
                flag = 1
                fooCond.signalAll()
            } finally {
                lock.unlock()
            }
        }
    }

    fun bar(printBar: () -> Unit) {
        repeat(n) {
            lock.lock()
            try {
                while (flag == 0) {
                    fooCond.await()
                }
                printBar()
                flag = 0
                barCond.signalAll()
            } finally {
                lock.unlock()
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


import threading

class FooBarLock:
    def __init__(self, n: int):
        self.n = n
        self.flag = 0
        self.lock = threading.Lock()
        self.fooCond = threading.Condition(self.lock)
        self.barCond = threading.Condition(self.lock)

    def foo(self, printFoo):
        for _ in range(self.n):
            with self.lock:
                while self.flag == 1:
                    self.barCond.wait()
                printFoo()
                self.flag = 1
                self.fooCond.notify_all()

    def bar(self, printBar):
        for _ in range(self.n):
            with self.lock:
                while self.flag == 0:
                    self.fooCond.wait()
                printBar()
                self.flag = 0
                self.barCond.notify_all()

Complexity

⏰ Time complexity: O(n) — Each thread prints n times, and each print is O(1).
🧺 Space complexity: O(1) — Only a few variables and lock objects are used for synchronization.

Method 3 - Volatile Flag (Busy Waiting)

Intuition

We use a shared volatile flag to coordinate the threads. Each thread spins in a loop, checking the flag until it’s their turn, then prints and updates the flag. This approach is simple but uses busy waiting, which can waste CPU cycles.

Approach

Use a shared volatile flag variable: 0 for “foo” turn, 1 for “bar” turn.
In each thread, loop n times and use a while loop to wait until the flag matches the thread’s turn.
When it’s the thread’s turn, print and update the flag.
Use a short sleep in the loop to reduce CPU usage.
Repeat until both threads have printed n times.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


public class FooBarVolatile {
    private int n;
    private volatile int flag = 0;

    public FooBarVolatile(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while (true) {
                if (flag == 0) {
                    printFoo.run();
                    flag = 1;
                    break;
                }
                Thread.sleep(1);
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while (true) {
                if (flag == 1) {
                    printBar.run();
                    flag = 0;
                    break;
                }
                Thread.sleep(1);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class FooBarVolatile(private val n: Int) {
    @Volatile private var flag = 0

    fun foo(printFoo: () -> Unit) {
        repeat(n) {
            while (true) {
                if (flag == 0) {
                    printFoo()
                    flag = 1
                    break
                }
                Thread.sleep(1)
            }
        }
    }

    fun bar(printBar: () -> Unit) {
        repeat(n) {
            while (true) {
                if (flag == 1) {
                    printBar()
                    flag = 0
                    break
                }
                Thread.sleep(1)
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


import threading
import time

class FooBarVolatile:
    def __init__(self, n: int):
        self.n = n
        self.flag = 0
        self.lock = threading.Lock()

    def foo(self, printFoo):
        for _ in range(self.n):
            while True:
                with self.lock:
                    if self.flag == 0:
                        printFoo()
                        self.flag = 1
                        break
                time.sleep(0.001)

    def bar(self, printBar):
        for _ in range(self.n):
            while True:
                with self.lock:
                    if self.flag == 1:
                        printBar()
                        self.flag = 0
                        break
                time.sleep(0.001)

Complexity

⏰ Time complexity: O(n) — Each thread prints n times, but busy waiting can increase actual CPU usage.
🧺 Space complexity: O(1) — Only a few variables are used for synchronization.

Method 4 - CAS (Atomic Compare-And-Set)

Intuition

We use an atomic integer and CAS (compare-and-set) operations to coordinate the threads. Each thread atomically updates the flag only when it’s their turn, ensuring safe concurrent access without explicit locks.

Approach

Use an AtomicInteger flag: 0 for “foo” turn, 1 for “bar” turn.
In each thread, loop n times and use a while loop with compareAndSet to atomically update the flag when it’s the thread’s turn.
When the CAS succeeds, print and continue; otherwise, sleep briefly and retry.
Repeat until both threads have printed n times.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


import java.util.concurrent.atomic.AtomicInteger;

public class FooBarCAS {
    private int n;
    private AtomicInteger flag = new AtomicInteger(0);

    public FooBarCAS(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while (!flag.compareAndSet(0, 1)) {
                Thread.sleep(1);
            }
            printFoo.run();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while (!flag.compareAndSet(1, 0)) {
                Thread.sleep(1);
            }
            printBar.run();
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


import java.util.concurrent.atomic.AtomicInteger

class FooBarCAS(private val n: Int) {
    private val flag = AtomicInteger(0)

    fun foo(printFoo: () -> Unit) {
        repeat(n) {
            while (!flag.compareAndSet(0, 1)) {
                Thread.sleep(1)
            }
            printFoo()
        }
    }

    fun bar(printBar: () -> Unit) {
        repeat(n) {
            while (!flag.compareAndSet(1, 0)) {
                Thread.sleep(1)
            }
            printBar()
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


import threading
import time

class AtomicInt:
    def __init__(self, value: int = 0):
        self.value = value
        self.lock = threading.Lock()

    def compare_and_set(self, expect: int, update: int) -> bool:
        with self.lock:
            if self.value == expect:
                self.value = update
                return True
            return False

class FooBarCAS:
    def __init__(self, n: int):
        self.n = n
        self.flag = AtomicInt(0)

    def foo(self, printFoo):
        for _ in range(self.n):
            while not self.flag.compare_and_set(0, 1):
                time.sleep(0.001)
            printFoo()

    def bar(self, printBar):
        for _ in range(self.n):
            while not self.flag.compare_and_set(1, 0):
                time.sleep(0.001)
            printBar()

Complexity

⏰ Time complexity: O(n) — Each thread prints n times, but busy waiting can increase actual CPU usage.
🧺 Space complexity: O(1) — Only a few variables and atomic objects are used for synchronization.

Method 5 - Using Semaphore

Intuition

We use two semaphores to strictly control the order of execution between the two threads. One semaphore allows “foo” to print, then signals the other semaphore to allow “bar” to print, alternating for n cycles.

Approach

Initialize two semaphores: one for “foo” (starting with 1 permit), one for “bar” (starting with 0 permits).
In the “foo” thread, acquire its semaphore, print, then release the “bar” semaphore.
In the “bar” thread, acquire its semaphore, print, then release the “foo” semaphore.
Repeat for n cycles.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


import java.util.concurrent.Semaphore;
class FooBarSemaphore {
    private int n;
    private final Semaphore fooSem = new Semaphore(1);
    private final Semaphore barSem = new Semaphore(0);

    public FooBarSemaphore(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            fooSem.acquire();
            printFoo.run();
            barSem.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            barSem.acquire();
            printBar.run();
            fooSem.release();
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


import java.util.concurrent.Semaphore

class FooBarSemaphore(private val n: Int) {
    private val fooSem = Semaphore(1)
    private val barSem = Semaphore(0)

    fun foo(printFoo: () -> Unit) {
        repeat(n) {
            fooSem.acquire()
            printFoo()
            barSem.release()
        }
    }

    fun bar(printBar: () -> Unit) {
        repeat(n) {
            barSem.acquire()
            printBar()
            fooSem.release()
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


import threading

class FooBarSemaphore:
    def __init__(self, n: int):
        self.n = n
        self.fooSem = threading.Semaphore(1)
        self.barSem = threading.Semaphore(0)

    def foo(self, printFoo):
        for _ in range(self.n):
            self.fooSem.acquire()
            printFoo()
            self.barSem.release()

    def bar(self, printBar):
        for _ in range(self.n):
            self.barSem.acquire()
            printBar()
            self.fooSem.release()

Complexity

⏰ Time complexity: O(n) — Each thread prints n times, and each print is O(1).
🧺 Space complexity: O(1) — Only a few semaphore objects are used for synchronization.

Problem#

Examples#

Initial Code:#

Solution#

Method 1 - Synchronized (Monitor Wait/Notify)#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Lock and Condition Variables#

Intuition#

Approach#

Code#

Complexity#

Method 3 - Volatile Flag (Busy Waiting)#

Intuition#

Approach#

Code#

Complexity#

Method 4 - CAS (Atomic Compare-And-Set)#

Intuition#

Approach#

Code#

Complexity#

Method 5 - Using Semaphore#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Initial Code:

Solution

Method 1 - Synchronized (Monitor Wait/Notify)

Intuition

Approach

Code

Complexity

Method 2 - Lock and Condition Variables

Intuition

Approach

Code

Complexity

Method 3 - Volatile Flag (Busy Waiting)

Intuition

Approach

Code

Complexity

Method 4 - CAS (Atomic Compare-And-Set)

Intuition

Approach

Code

Complexity

Method 5 - Using Semaphore

Intuition

Approach

Code

Complexity