1115. Print FooBar Alternately

MediumConcurrency
Leetcode Link

Problem Description

In this concurrency problem, we have a code snippet defining a class FooBar with two methods: foo() and bar(). These methods print the strings "foo" and "bar", respectively, in a loop up to n times. The challenge is to ensure that when these methods are called by two separate threads, the output is "foobar" repeated n times, with "foo" and "bar" alternating properly.

To achieve this, we need to implement a mechanism that enforces the order of execution, such that the foo() method must print "foo" before the bar() method prints "bar," and this pattern is repeated for the entire loop.

Intuition

Concurrency problems often require synchronization techniques to ensure that multiple threads can work together without conflicts or race conditions. In this case, we need to make sure that "foo" is always printed before "bar."

The intuition behind the solution is to use semaphores—a classic synchronization primitive—to coordinate the actions of the threads. In the context of this problem, we use two semaphores: one that controls the printing of "foo" (self.f) and one that controls the printing of "bar" (self.b).

The self.f semaphore is initially set to 1, allowing the foo() method to print immediately. After printing, it releases the self.b semaphore, which is initially set to 0, thus preventing bar() from printing until foo() is printed first. Once self.b is released by foo(), the bar() method can print "bar" and then release the self.f semaphore to allow the next "foo" to be printed. This alternating process continues until the loop completes n times.

By carefully managing the states of the semaphores and ensuring that each method changes the semaphore state only after printing, we can achieve the desired ordering of prints, resulting in the correct output "foobar" repeated n times.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following uses divide and conquer strategy?

Solution Approach

The solution utilizes the Semaphore class from Python's threading module as the primary synchronization mechanism, allowing us to enforce the strict alternation between foo and bar.

Here's a step-by-step explanation of the code implementation:

  1. Initialization: The FooBar class is initialized with an integer n, which represents the number of times "foobar" should be printed. Two Semaphore objects are created: self.f for "foo" with an initial value of 1, and self.b for "bar" with an initial value of 0. The initial values are critical: self.f is set to 1 to allow foo() to proceed immediately, and self.b is set to 0 to block bar() until foo() signals it by releasing self.b.

  2. The foo Method:

    • It contains a loop that runs n times.
    • Each iteration begins with self.f.acquire(), which blocks if the semaphore's value is 0. Since self.f is initialized to 1, foo() can start immediately on the first iteration.
    • The printFoo() function is executed, printing "foo".
    • After printing "foo", the self.b.release() is called. This increments the count of the self.b semaphore, signaling the bar() method (if it is waiting) that it can proceed to print "bar".

  3. The bar Method:

    • It's also a loop running n times.
    • Each iteration starts by calling self.b.acquire(), which waits until the self.f semaphore is released by a previous foo() call, ensuring that "foo" has been printed before "bar" can proceed.
    • Once the semaphore is acquired, printBar() is executed to print "bar".
    • After printing "bar", it invokes self.f.release() to increment the semaphore count for foo, allowing the next iteration of foo() to print again, hence ensuring the sequence starts with "foo".

This alternating semaphore pattern locks each method in a waiting state until the other method signals that it has finished its task by releasing the semaphore. Since acquire() decreases the semaphore's value by 1 and release() increases it by 1, this careful incrementing and decrementing of semaphore values guarantees that the print order is preserved and that the strings "foo" and "bar" are printed in the correct sequence to form "foobar" without getting mixed up or overwritten.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Example Walkthrough

Let's walk through a simple example with n = 2. We want our output to be "foobarfoobar" with "foo" always preceding "bar".

Here's how the synchronization using semaphores will facilitate this:

  • Initialization:

    • FooBar object is created with n = 2.
    • Semaphore self.f is set to 1 (unlocked), allowing foo() to be called immediately.
    • Semaphore self.b is set to 0 (locked), preventing bar() from being called until foo() is done.

  • First Iteration:

    1. foo() method is called by Thread 1.
      • self.f.acquire() is called, which succeeds immediately because self.f is 1 (unlocked).
      • printFoo() is executed, so "foo" is printed.
      • self.b.release() is called, incrementing self.b to 1, which unlocks bar().
    2. bar() method is called by Thread 2.
      • self.b.acquire() is called, which succeeds because self.b was released by foo().
      • printBar() is executed, printing "bar" after "foo".
      • self.f.release() is called, setting self.f back to 1 (unlocked) and allowing the next foo() to proceed.

  • Second Iteration:

    1. Again, foo() method is called by Thread 1.
      • This time, since self.f was released by the previous bar() call, self.f.acquire() succeeds again.
      • printFoo() is executed, and another "foo" is printed.
      • self.b.release() is called, incrementing self.b and allowing bar() to be called.
    2. bar() method is again called by Thread 2.
      • With self.b released, self.b.acquire() allows the thread to proceed.
      • printBar() prints "bar", following the "foo" printed by the last foo() call.
      • Finally, self.f.release() is called, although in this case, it's unnecessary because we've reached our loop condition (n times) and no further foo() calls are needed.

By the end of the two iterations, we've successfully printed "foobarfoobar". Each foo() preceded a bar() thanks to our semaphore controls, and at no point could bar() leapfrog ahead of foo(). The semaphores effectively serialized access to the printing functions, ensuring the correct order despite the concurrent execution of threads.

Solution Implementation

1from threading import Semaphore
2from typing import Callable
3
4
5class FooBar:
6    def __init__(self, n: int):
7        self.n = n  # Number of times "foo" and "bar" are to be printed.
8        # Semaphore for "foo" is initially unlocked.
9        self.sem_foo = Semaphore(1)
10        # Semaphore for "bar" is initially locked.
11        self.sem_bar = Semaphore(0)
12
13    def foo(self, print_foo: Callable[[], None]) -> None:
14        """Print "foo" n times, ensuring it alternates with "bar"."""
15        for _ in range(self.n):
16            self.sem_foo.acquire()  # Wait for semaphore to be unlocked.
17            print_foo()  # Provided print function for "foo".
18            self.sem_bar.release()  # Unlock semaphore for "bar".
19
20    def bar(self, print_bar: Callable[[], None]) -> None:
21        """Print "bar" n times, ensuring it alternates with "foo"."""
22        for _ in range(self.n):
23            self.sem_bar.acquire()  # Wait for semaphore to be unlocked.
24            print_bar()  # Provided print function for "bar".
25            self.sem_foo.release()  # Unlock semaphore for "foo".
26
1class FooBar {
2    private final int loopCount; // The number of times "foo" and "bar" should be printed.
3    private final Semaphore fooSemaphore = new Semaphore(1); // A semaphore for "foo", allowing "foo" to print first.
4    private final Semaphore barSemaphore = new Semaphore(0); // A semaphore for "bar", initially locked until "foo" is printed.
5
6    public FooBar(int n) {
7        this.loopCount = n;
8    }
9
10    // The method for printing "foo"
11    public void foo(Runnable printFoo) throws InterruptedException {
12        for (int i = 0; i < loopCount; i++) {
13            fooSemaphore.acquire(); // Acquire a permit before printing "foo", ensuring "foo" has the turn to print
14            printFoo.run();         // Output "foo"
15            barSemaphore.release(); // Release a permit for "bar" after "foo" is printed, allowing "bar" to print next
16        }
17    }
18
19    // The method for printing "bar"
20    public void bar(Runnable printBar) throws InterruptedException {
21        for (int i = 0; i < loopCount; i++) {
22            barSemaphore.acquire(); // Acquire a permit before printing "bar", ensuring "bar" has the turn to print
23            printBar.run();         // Output "bar"
24            fooSemaphore.release(); // Release a permit for "foo" after "bar" is printed, allowing "foo" to print next
25        }
26    }
27}
28
1#include <semaphore.h>
2#include <functional>
3
4class FooBar {
5private:
6    int n_;                // The number of times to print "foobar"
7    sem_t sem_foo_, sem_bar_; // Semaphores used to coordinate the printing order
8
9public:
10    // Constructor that initializes the semaphores and count
11    FooBar(int n) : n_(n) {
12        // Initialize sem_foo_ with a count of 1 to allow "foo" to print first
13        sem_init(&sem_foo_, 0, 1);
14        // Initialize sem_bar_ with a count of 0 to block "bar" until "foo" is printed
15        sem_init(&sem_bar_, 0, 0);
16    }
17
18    // Deconstructor that destroys the semaphores
19    ~FooBar() {
20        sem_destroy(&sem_foo_);
21        sem_destroy(&sem_bar_);
22    }
23
24    // Method for printing "foo"
25    void foo(std::function<void()> printFoo) {
26        for (int i = 0; i < n_; ++i) {
27            // Wait on sem_foo_ to ensure "foo" is printed first
28            sem_wait(&sem_foo_);
29            // printFoo() calls the provided lambda function to output "foo"
30            printFoo();
31            // Post (increment) sem_bar_ to allow "bar" to be printed next
32            sem_post(&sem_bar_);
33        }
34    }
35
36    // Method for printing "bar"
37    void bar(std::function<void()> printBar) {
38        for (int i = 0; i < n_; ++i) {
39            // Wait on sem_bar_ to ensure "bar" is printed after "foo"
40            sem_wait(&sem_bar_);
41            // printBar() calls the provided lambda function to output "bar"
42            printBar();
43            // Post (increment) sem_foo_ to allow the next "foo" to be printed
44            sem_post(&sem_foo_);
45        }
46    }
47};
48
1// The number of times to print "foo" and "bar"
2let n: number;
3// Promises and callbacks for signaling
4let canPrintFoo: (() => void) | null = null;
5let canPrintBar: (() => void) | null = null;
6// Deferred promise resolvers
7let fooPromiseResolver: (() => void) | null = null;
8let barPromiseResolver: (() => void) | null = null;
9
10/**
11 * Initializes the synchronization primitives.
12 * @param {number} count - The number of iterations to run the sequence.
13 */
14function initFooBar(count: number): void {
15    n = count;
16    // Start with the ability to print "foo"
17    canPrintFoo = (() => {
18        fooPromiseResolver = null;
19        if (canPrintBar) canPrintBar();
20    });
21    // Prevent "bar" from printing until "foo" is printed
22    canPrintBar = null;
23}
24
25/**
26 * Prints "foo" to the console or another output.
27 * @param {() => void} printFoo - A callback function that prints "foo".
28 */
29async function foo(printFoo: () => void): Promise<void> {
30    for (let i = 0; i < n; i++) {
31        await new Promise<void>((resolve) => {
32            fooPromiseResolver = resolve;
33            if (canPrintFoo) canPrintFoo();
34        });
35        // The provided callback prints "foo"
36        printFoo();
37        // Allow "bar" to be printed
38        canPrintBar = (() => {
39            barPromiseResolver = null;
40            if (fooPromiseResolver) fooPromiseResolver();
41        });
42        // Block until 'bar' is printed
43        canPrintFoo = null;
44    }
45}
46
47/**
48 * Prints "bar" to the console or another output.
49 * @param {() => void} printBar - A callback function that prints "bar".
50 */
51async function bar(printBar: () => void): Promise<void> {
52    for (let i = 0; i < n; i++) {
53        await new Promise<void>((resolve) => {
54            barPromiseResolver = resolve;
55            if (canPrintBar) canPrintBar();
56        });
57        // The provided callback prints "bar"
58        printBar();
59        // Allow "foo" to be printed again
60        canPrintFoo = (() => {
61            fooPromiseResolver = null;
62            if (barPromiseResolver) barPromiseResolver();
63        });
64        // Block until 'foo' is printed again
65        canPrintBar = null;
66    }
67}
68
69// Example usage:
70initFooBar(3); // Initialize printing "foo" and "bar" three times each
71foo(() => console.log('foo'));
72bar(() => console.log('bar'));
73
Not Sure What to Study? Take the 2-min Quiz：

Which technique can we use to find the middle of a linked list?

Time and Space Complexity

Time Complexity

The time complexity of the FooBar class methods foo and bar are both O(n). Each method contains a loop that iterates n times, where n is the input that represents the number of times the "foo" and "bar" functions should be called, respectively. The methods invoke acquire and release on semaphores, but the acquire/release operations are constant-time O(1) operations, assuming that there is no contention (which should not happen here given the strict alternation). The printFoo and printBar functions are also called n times each, and if we consider these functions to have O(1) time complexity, which is a reasonable assumption for a simple print operation, then this does not change the overall time complexity of the foo and bar methods.

Space Complexity

The space complexity of the FooBar class is O(1) since the space required does not grow with n. The class maintains fixed resources: two semaphores and one integer variable. No additional space is allocated that would scale with the input n, meaning that the memory usage is constant irrespective of the size of n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫