Leetcode 1114: Print in Order
You are given a class with three methods:
first(), second(), and third(). These methods are called concurrently by three threads. The goal is to ensure that second() is executed only after first() has been executed, and third() is executed only after second() has been executed. The execution of these methods is asynchronous, and you need to design a mechanism that guarantees the correct order of execution regardless of the operating system’s thread scheduling.Problem
Approach
Steps
Complexity
Input: The input is an array of integers, where the integers represent the order in which the threads call the methods: 1 for `first()`, 2 for `second()`, and 3 for `third()`.
Example: Input: nums = [1, 3, 2]
Constraints:
• nums is a permutation of [1, 2, 3].
Output: The output is the concatenation of the strings printed by each method in the correct order. For example, if `first()`, `second()`, and `third()` are printed in the correct order, the output will be 'firstsecondthird'.
Example: Output: 'firstsecondthird'
Constraints:
• The methods should be executed in the correct order, even if the threads are scheduled asynchronously.
Goal: Ensure that `second()` is executed after `first()`, and `third()` is executed after `second()`.
Steps:
• Use a mechanism to control the order of method execution, such as using mutex locks or condition variables.
• Track the current method that should be executed and allow each thread to proceed only when it is their turn to execute the corresponding method.
Goal: The input array will always be a permutation of [1, 2, 3], ensuring that each method will be called exactly once.
Steps:
• 1 <= nums.length <= 3
• nums is a permutation of [1, 2, 3].
Assumptions:
• The methods `first()`, `second()`, and `third()` are executed by three different threads.
• Thread scheduling is unpredictable, and the order of execution is determined by the input array.
• Input: Input: nums = [1, 3, 2]
• Explanation: In this case, thread A calls `first()`, thread B calls `third()`, and thread C calls `second()`. The expected output is 'firstsecondthird', as `second()` should execute after `first()`, and `third()` should execute after `second()`.
• Input: Input: nums = [2, 1, 3]
• Explanation: In this case, thread A calls `second()`, thread B calls `first()`, and thread C calls `third()`. The expected output is 'firstsecondthird', as the order must be adjusted to maintain correct execution.
Approach: The solution involves controlling the execution order using synchronization primitives like mutex locks or condition variables. By tracking the current stage of execution, we can ensure the correct order of method invocations.
Observations:
• Since the threads are running concurrently, we need to control the execution order between them.
• Using locks or condition variables is a straightforward way to enforce the desired execution order.
Steps:
• Create a shared variable to track the current execution stage (starting with 1 for `first()`).
• In each method, use a mutex lock to ensure exclusive access and check the current stage to determine if the method should execute.
• For each method, wait until the correct stage is reached, then execute the method and increment the stage to allow the next method to run.
Empty Inputs:
• The input will always contain exactly three integers representing the methods to be executed.
Large Inputs:
• Since the input array is always a permutation of [1, 2, 3], there are no large inputs to consider.
Special Values:
• The solution should handle all permutations of [1, 2, 3].
Constraints:
• Ensure that the methods are executed in the correct order, regardless of thread scheduling.
std::mutex mtx;
public:
Foo() {
curVal = 1;
}
void first(function<void()> printFirst) {
mtx.lock();
// printFirst() outputs "first". Do not change or remove this line.
printFirst();
curVal++;
mtx.unlock();
}
void second(function<void()> printSecond) {
mtx.lock();
while(curVal != 2)
{
mtx.unlock();
mtx.lock();
}
mtx.unlock();
// printSecond() outputs "second". Do not change or remove this line.
printSecond();
curVal++ ;
}
void third(function<void()> printThird) {
mtx.lock();
while(curVal != 3)
{
mtx.unlock();
mtx.lock();
}
mtx.unlock();
// printThird() outputs "third". Do not change or remove this line.
printThird();
curVal++;
1 : Mutex Declaration
std::mutex mtx;
A mutex `mtx` is declared to ensure that the tasks are executed in the correct order by preventing race conditions.
2 : Constructor
public:
Access modifier indicating that the following function is public.
3 : Constructor
Foo() {
The constructor of the class `Foo` is defined. It initializes the `curVal` variable to 1.
4 : Variable Initialization
curVal = 1;
The integer variable `curVal` is initialized to 1, which will control the order of the execution of the tasks.
5 : First Task
void first(function<void()> printFirst) {
The `first` method is defined, which will execute the first task, printing 'first' when called.
6 : Lock
mtx.lock();
The mutex `mtx` is locked to ensure that no other task is executed before this one.
7 : Function Call
printFirst();
The `printFirst()` function is called to print 'first'.
8 : Update Variable
curVal++;
The `curVal` variable is incremented to 2 to indicate that the first task is complete.
9 : Unlock
mtx.unlock();
The mutex `mtx` is unlocked, allowing the next task to be executed.
10 : Second Task
void second(function<void()> printSecond) {
The `second` method is defined, which will execute the second task, printing 'second' when called.
11 : Lock
mtx.lock();
The mutex `mtx` is locked to ensure exclusive access to the critical section.
12 : While Loop
while(curVal != 2)
A `while` loop is used to wait until `curVal` is equal to 2, indicating that the first task has been completed.
13 : Unlock and Lock
mtx.unlock();
Unlock the mutex to allow other threads to execute while the current task is waiting.
14 : Re-lock
mtx.lock();
Re-lock the mutex to check the condition again and proceed once the `curVal` reaches 2.
15 : Unlock
mtx.unlock();
Unlock the mutex to allow the next task to execute.
16 : Function Call
printSecond();
The `printSecond()` function is called to print 'second'.
17 : Update Variable
curVal++ ;
The `curVal` variable is incremented to 3 to indicate that the second task is complete.
18 : Third Task
void third(function<void()> printThird) {
The `third` method is defined, which will execute the third task, printing 'third' when called.
19 : Lock
mtx.lock();
The mutex `mtx` is locked to ensure exclusive access.
20 : While Loop
while(curVal != 3)
A `while` loop is used to wait until `curVal` is equal to 3, indicating that the second task has been completed.
21 : Unlock and Lock
mtx.unlock();
Unlock the mutex to allow other threads to execute while the current task is waiting.
22 : Re-lock
mtx.lock();
Re-lock the mutex to check the condition again and proceed once the `curVal` reaches 3.
23 : Unlock
mtx.unlock();
Unlock the mutex to allow the next task to execute.
24 : Function Call
printThird();
The `printThird()` function is called to print 'third'.
25 : Update Variable
curVal++;
The `curVal` variable is incremented, indicating that all tasks have been completed.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The time complexity is O(1) as the input size is fixed and each method is executed only once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because the solution only uses a fixed number of variables for synchronization.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus