Leetcode 1115. Print FooBar Alternately

Problem Explanation

The problem is to control the execution order of the threads in such a way that it prints "foobar" n times. We have two functions foo() and bar(), which are called by Thread A and Thread B respectively. The tricky part is that we need to make sure that foo() finishes before bar() for each iteration.

For instance, if n is 2, we want our output to be "foobarfoobar", not "foofoo" or "barbar" or some other combination. The execution of foo() and bar() need to be interleaved to achieve "foobar" n times.

Approach of the Solution

The solution uses Semaphores to solve this problem. In simple terms, a semaphore is a variable that is used to control access to a common resource by multiple processes in a concurrent system. It is a way of synchronising between threads. A counting semaphore has a certain number of resources available, and each sem_wait() decrements that count, and each sem_post() increments it.

In this program, we initialise two semaphores: one for foo (fooSemaphore) and one for bar (barSemaphore). At first, the fooSemaphore is open (initialised to 1) and the barSemaphore is closed (initialised to 0).

In the foo() function, foo waits for fooSemaphore. Once it gets the resource, it prints "foo" and then posts (releases) the barSemaphore. Similarly, the bar() function waits for its semaphore, prints "bar", and then releases fooSemaphore. This ensures that "foo" is always printed before "bar". This process repeats n times to get the desired output "foobar" n times.

Python Solution

1
2python
3import threading
4
5class FooBar:
6    def __init__(self, n):
7        self.n = n
8        self.foo_lock = threading.Lock()
9        self.bar_lock = threading.Lock()
10      
11        # Initially lock bar_lock
12        self.bar_lock.acquire()
13
14    def foo(self, printFoo: 'Callable[[], None]') -> None:
15        for i in range(self.n):
16            # Wait if lock is acquired
17            self.foo_lock.acquire()
18            # printFoo() outputs "foo". Do not change or remove this line.
19            printFoo()
20            # Release bar lock
21            self.bar_lock.release()
22
23    def bar(self, printBar: 'Callable[[], None]') -> None:
24        for i in range(self.n):
25            # Wait if lock is acquired
26            self.bar_lock.acquire()
27            # printBar() outputs "bar". Do not change or remove this line.
28            printBar()
29            # Release foo lock
30            self.foo_lock.release()

Java Solution

1
2java
3import java.util.concurrent.Semaphore;
4
5public class FooBar {
6    private int n;
7    private Semaphore fooSemaphore = new Semaphore(1);
8    private Semaphore barSemaphore = new Semaphore(0);
9
10    public FooBar(int n) {
11        this.n = n;
12    }
13
14    public void foo(Runnable printFoo) throws InterruptedException {
15        for (int i = 0; i < n; i++) {
16            fooSemaphore.acquire();
17            printFoo.run();
18            barSemaphore.release();
19        }
20    }
21
22    public void bar(Runnable printBar) throws InterruptedException {
23        for (int i = 0; i < n; i++) {
24            barSemaphore.acquire();
25            printBar.run();
26            fooSemaphore.release();
27        }
28    }
29}

JavaScript Solution

1
2javascript
3const Semaphore = require('async-mutex').Semaphore;
4
5class FooBar {
6    constructor(n) {
7        this.n = n;
8        this.fooSemaphore = new Semaphore(1);
9        this.barSemaphore = new Semaphore(0);
10    }
11
12    foo(printFoo) {
13        for (let i = 0; i < this.n; i++) {
14            this.fooSemaphore.acquire().then(() => {
15                printFoo();
16                this.barSemaphore.release();
17            });
18        }
19    }
20
21    bar(printBar) {
22        for (let i = 0; i < this.n; i++) {
23            this.barSemaphore.acquire().then(() => {
24                printBar();
25                this.fooSemaphore.release();
26            });
27        }
28    }
29}

C# Solution

1
2csharp
3using System.Threading;
4
5public class FooBar
6{
7    private int n;
8    private SemaphoreSlim fooSemaphore = new SemaphoreSlim(1, 1);
9    private SemaphoreSlim barSemaphore = new SemaphoreSlim(0, 1);
10
11    public FooBar(int n)
12    {
13        this.n = n;
14    }
15
16    public void Foo(Action printFoo)
17    {
18        for (int i = 0; i < n; i++) {
19            fooSemaphore.Wait();
20            printFoo.Invoke();
21            barSemaphore.Release();
22        }
23    }
24
25    public void Bar(Action printBar)
26    {
27        for (int i = 0; i < n; i++) {
28            barSemaphore.Wait();
29            printBar.Invoke();
30            fooSemaphore.Release();
31        }
32    }
33}

Please note: The JavaScript solution refers to the a third-party library "async-mutex", which provides the Semaphore functionality as JavaScript does not natively support Semaphores.## Conclusion

In conclusion, this problem allows us to understand how to control the execution order of threads. It demonstrates how to employ semaphores to manage access to common resources in a concurrent computing environment effectively. Semaphores also provide a comfortable way for threads to communicate with each other by sending signals indicating when a certain action has been completed or a condition has been met.

In Python, Java, JavaScript and C#, we have successfully implemented the problem solution which ensures the correct order of the execution of functions from different threads and controls the quantity of "foobar" printed.

Understanding these patterns of synchronization is key to developing effective multithreaded applications.

Remember to always release the semaphores in appropriate places in your code to prevent issues related to multi-threading such as deadlocks from occurring.