Leetcode 1115: Print FooBar Alternately
You are given a class
FooBar with two methods: foo() and bar(). These methods are called concurrently by two threads. One thread calls foo() while the other calls bar(). You need to modify the program to ensure that the output alternates between ‘foo’ and ‘bar’, and ‘foobar’ is printed exactly n times. The threads should alternate their execution such that foo() is printed first, followed by bar(), and this pattern should continue for n times.Problem
Approach
Steps
Complexity
Input: The input consists of an integer `n` representing the number of times the pattern 'foobar' should be printed.
Example: Input: n = 3
Constraints:
• 1 <= n <= 1000
Output: The output should be the string 'foobar' repeated `n` times, with each 'foo' and 'bar' printed by different threads in alternating order.
Example: Output: 'foobarfoobarfoobar'
Constraints:
• The two threads should print 'foo' and 'bar' in alternating order, starting with 'foo'.
Goal: Ensure that the two threads alternate between printing 'foo' and 'bar', starting with 'foo', for `n` times.
Steps:
• Use two mutexes to control the execution order of the threads.
• Thread A prints 'foo', and thread B prints 'bar'. Thread A should print first, then thread B, and the alternation continues for `n` times.
Goal: Ensure that both threads print their respective strings in the correct order without overlap.
Steps:
• Threads A and B must alternate printing 'foo' and 'bar'.
• The total number of 'foobar' printed must be exactly `n`.
Assumptions:
• Threads are scheduled asynchronously, so thread A and thread B may not execute in any specific order without synchronization.
• Input: Input: n = 1
• Explanation: In this case, thread A calls `foo()` and thread B calls `bar()`. The expected output is 'foobar' because thread A prints 'foo' first, followed by thread B printing 'bar'.
• Input: Input: n = 2
• Explanation: Here, the expected output is 'foobarfoobar' because the pattern 'foo' followed by 'bar' should repeat twice.
Approach: The approach uses two mutexes to synchronize the threads. The first mutex ensures that 'foo' is printed first by thread A, and the second mutex controls the execution of thread B, ensuring 'bar' is printed after 'foo'.
Observations:
• We need to manage the execution order of two threads to ensure they print in the correct sequence.
• Using two mutexes allows us to control which thread prints at any given time, ensuring they alternate in the desired order.
Steps:
• Initialize two mutexes: one for `foo` and one for `bar`.
• Thread A locks the `foo` mutex and prints 'foo', then releases the `bar` mutex to allow thread B to print.
• Thread B locks the `bar` mutex, prints 'bar', and then releases the `foo` mutex for thread A to print again.
Empty Inputs:
• Since n is guaranteed to be at least 1, there will always be at least one 'foobar' printed.
Large Inputs:
• For large values of `n`, the solution should handle multiple thread executions efficiently.
Special Values:
• When `n` is 1, the output is simply 'foobar'.
Constraints:
• The solution must handle both small and large values of `n` efficiently.
int n;
mutex mtx1, mtx2;
public:
FooBar(int n) {
mtx2.lock();
this->n = n;
}
void foo(function<void()> printFoo) {
for (int i = 0; i < n; i++) {
mtx1.lock();
// printFoo() outputs "foo". Do not change or remove this line.
printFoo();
mtx2.unlock();
}
}
void bar(function<void()> printBar) {
for (int i = 0; i < n; i++) {
mtx2.lock();
// printBar() outputs "bar". Do not change or remove this line.
printBar();
mtx1.unlock();
}
}
1 : Variable Declaration
int n;
The variable `n` is declared to store the number of iterations for the tasks.
2 : Mutex Declaration
mutex mtx1, mtx2;
Two mutexes, `mtx1` and `mtx2`, are declared to synchronize the `foo` and `bar` functions and control the task execution order.
3 : Access Modifier
public:
Access modifier to define that the following functions can be accessed from outside the class.
4 : Constructor
FooBar(int n) {
The constructor `FooBar(int n)` is defined to initialize the variable `n` and lock `mtx2`.
5 : Locking Mutex
mtx2.lock();
The mutex `mtx2` is locked in the constructor to prevent `bar` from starting before `foo`.
6 : Assigning Value
this->n = n;
The constructor assigns the value of `n` to the class's `n` variable.
7 : Function Definition
void foo(function<void()> printFoo) {
The `foo` method is defined, where it will print 'foo' repeatedly for `n` times.
8 : For Loop
for (int i = 0; i < n; i++) {
A `for` loop is used to execute the task `n` times.
9 : Locking Mutex
mtx1.lock();
The mutex `mtx1` is locked to ensure that `foo` can execute before `bar`.
10 : Function Call
printFoo();
The function `printFoo()` is called to output 'foo'.
11 : Unlocking Mutex
mtx2.unlock();
The mutex `mtx2` is unlocked, allowing `bar` to execute.
12 : Function Definition
void bar(function<void()> printBar) {
The `bar` method is defined, where it will print 'bar' repeatedly for `n` times.
13 : For Loop
for (int i = 0; i < n; i++) {
A `for` loop is used to execute the task `n` times.
14 : Locking Mutex
mtx2.lock();
The mutex `mtx2` is locked to ensure that `bar` can execute after `foo`.
15 : Print Bar
// printBar() outputs "bar". Do not change or remove this line.
A comment indicating that `printBar()` will output 'bar'. It should not be changed.
16 : Function Call
printBar();
The function `printBar()` is called to output 'bar'.
17 : Unlocking Mutex
mtx1.unlock();
The mutex `mtx1` is unlocked, allowing `foo` to execute again.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) since each thread executes `n` times, and there are no nested iterations.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because only a fixed number of variables are used to control the thread synchronization.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus