1114. Print in Order
Problem Description
In this problem, we are given a class Foo
with three methods: first()
, second()
, and third()
. These methods are intended to be called by three different threads, let's call them Thread A, Thread B, and Thread C respectively. The challenge is to ensure that these methods are called in the strict sequence where first()
is called before second()
and second()
is called before third()
, regardless of how the threads are scheduled by the operating system.
This means that if Thread B tries to call second()
before Thread A calls first()
, Thread B should wait until first()
has been called. Similarly, Thread C must wait for second()
to complete before calling third()
.
Intuition
The solution to this problem involves synchronization mechanisms that allow threads to communicate with each other about the state of the execution. One common synchronization mechanism provided by many programming languages, including Python, is the Semaphore.
A semaphore manages an internal counter which is decremented by each acquire()
call and incremented by each release()
call. The counter can never go below zero; when acquire()
finds that it is zero, it blocks, waiting until some other thread calls release()
.
In the given solution:
- We have three semaphores:
self.a
,self.b
, andself.c
. self.a
is initialized with a count of 1 to allow thefirst()
operation to proceed immediately.self.b
andself.c
are initialized with a count of 0 to block thesecond()
andthird()
operations respectively until they are explicitly released.
The first()
method:
- Acquires
self.a
, ensuring no other operation is currently in progress. - Once the
first()
operation is complete, it releasesself.b
to allowsecond()
to proceed.
The second()
method:
- Acquires
self.b
, which will only be available onceself.a
has been released by thefirst()
method. - After completing its operation, it releases
self.c
to allowthird()
method execution.
The third()
method:
- Acquires
self.c
, which will only be available afterself.b
is released by thesecond()
method. - After completing its operation, it releases
self.a
. This is optional in the context where only one cycle of operations (first()
,second()
,third()
) is being performed but might be included for scenarios where the sequence may restart.
Using these semaphores, the solution effectively enforces a strict order of execution as required by the problem statement, even though the threads might be scheduled in any order by the operating system.
Solution Approach
The solution approach effectively utilizes semaphores, which are synchronization primitives that control access to a common resource by multiple threads in a concurrent system. Here's a step-by-step breakdown of how the solution is implemented:
-
Class Initialization:
- Inside the
Foo
class constructor, three semaphores are initialized. Semaphoresself.b
andself.c
are initialized with a count of 0 to ensure thatsecond()
andthird()
methods are blocked initially. Semaphoreself.a
is initialized with a count of 1 to allowfirst()
to proceed without blocking.
- Inside the
-
Executing
first()
:- The
first
method starts by callingself.a.acquire()
. Sinceself.a
was initialized to 1,first()
is allowed to proceed asacquire()
will decrement the counter to 0, and no blocking occurs. - The method performs its intended operation
printFirst()
. - After completion, it calls
self.b.release()
. This increments the counter of semaphoreself.b
from 0 to 1, thereby allowing a blockedsecond()
operation to proceed.
- The
-
Executing
second()
:- The
second
method callsself.b.acquire()
. Iffirst()
has already completed and calledself.b.release()
, the semaphoreself.b
counter would be 1, andsecond()
can proceed (the acquire operation decrements it back to 0). Iffirst()
has not completed,second()
will be blocked. - It then executes
printSecond()
. - Upon successful completion, it calls
self.c.release()
, increasing the counter of the semaphoreself.c
from 0 to 1, and thus unblocking thethird()
method.
- The
-
Executing
third()
:- The
third
method begins withself.c.acquire()
. Up untilsecond()
callsself.c.release()
,third()
will be blocked. Onceself.c
counter is 1,third()
can proceed (the acquire operation decrements it to 0). - It executes
printThird()
. - Optionally, it can call
self.a.release()
which is omitted in the given code snippet because it's not necessary unless the sequence of operations is intended to repeat.
- The
Each semaphore acts as a turnstile, controlling the flow of operations. The use of semaphores ensures that no matter the order in which threads arrive, they will be forced to execute in the necessary order: first()
then second()
then third()
.
This implementation exemplifies a classic synchronization pattern where the completion of one action triggers the availability of the next action in a sequence. The semaphores act like gates that open once the previous operation has signaled that it's safe for the next operation to start.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Imagine we have three simple functions that need to be executed in order: printFirst()
, printSecond()
, and printThird()
. They simply print "first", "second", and "third" respectively to the console. Now, let's see how the solution approach described earlier ensures these functions are called in the strict sequence required.
Let's assume the three threads are started almost simultaneously by the operating system, but due to some randomness in thread scheduling, the actual order of invocation is Thread B (second), Thread C (third), and finally, Thread A (first).
-
Thread B (second) arrives first:
- Calls
second()
method and tries to acquire semaphoreself.b
with anacquire()
call. - Since
self.b
was initialized with 0, it is blocked as the counter is already at 0, andacquire()
cannot decrement it further. Thread B will now wait forself.b
to be released by another operation (specifically, thefirst()
operation).
- Calls
-
Thread C (third) arrives next:
- It calls the
third()
method which tries to acquire semaphoreself.c
withacquire()
. - As with
self.b
,self.c
was initialized with 0, so Thread C is blocked because the semaphore's counter is not greater than 0. It must wait forself.c
to be released by thesecond()
operation.
- It calls the
-
Thread A (first) arrives last:
- It proceeds to call the
first()
method which attempts to acquire semaphoreself.a
with anacquire()
call. - Since
self.a
was initialized with 1, theacquire()
will succeed, the counter will decrement to 0, and thefirst()
method will proceed. - The
printFirst()
function is executed, outputting "first". - Upon completion, the
first()
method callsself.b.release()
, which increments semaphoreself.b
's counter to 1.
- It proceeds to call the
-
Thread B (second) resumes:
- With
self.b
's counter now at 1, Thread B can proceed asacquire()
successfully decrements it back to 0. - The
printSecond()
function is called, printing "second" to the console. - Upon finishing its operation, Thread B calls
self.c.release()
, incrementingself.c
's counter to 1, allowing the third operation to proceed.
- With
-
Thread C (third) resumes:
- Similar to the previous steps, with the
self.c
counter now at 1, thethird()
method proceeds asacquire()
brings the counter down to 0. printThird()
is executed, and "third" is printed to the console.
- Similar to the previous steps, with the
In this example, even though the threads arrived out of order, the use of semaphores forced them to wait for their turn, ensuring the desired sequence of "first", "second", "third" in the console output.
Solution Implementation
1from threading import Semaphore
2from typing import Callable
3
4class Foo:
5 def __init__(self):
6 # Initialize semaphores to control the order of execution.
7 # Semaphore 'first_done' allows 'first' method to run immediately.
8 self.first_done = Semaphore(1)
9 # Semaphore 'second_done' starts locked, preventing 'second' method from running.
10 self.second_done = Semaphore(0)
11 # Semaphore 'third_done' starts locked, preventing 'third' method from running.
12 self.third_done = Semaphore(0)
13
14 def first(self, print_first: Callable[[], None]) -> None:
15 # Acquire semaphore to enter 'first' method.
16 self.first_done.acquire()
17 # Execute the print_first function to output "first".
18 print_first()
19 # Release semaphore to allow 'second' method to run.
20 self.second_done.release()
21
22 def second(self, print_second: Callable[[], None]) -> None:
23 # Wait for the completion of 'first' method.
24 self.second_done.acquire()
25 # Execute the print_second function to output "second".
26 print_second()
27 # Release semaphore to allow 'third' method to run.
28 self.third_done.release()
29
30 def third(self, print_third: Callable[[], None]) -> None:
31 # Wait for the completion of 'second' method.
32 self.third_done.acquire()
33 # Execute the print_third function to output "third".
34 print_third()
35 # This line could re-enable the flow for 'first', in case of repeated calls.
36 self.first_done.release()
37
1import java.util.concurrent.Semaphore;
2
3public class Foo {
4 private Semaphore firstJobDone = new Semaphore(1); // Semaphore for first job, initially available
5 private Semaphore secondJobDone = new Semaphore(0); // Semaphore for second job, initially unavailable
6 private Semaphore thirdJobDone = new Semaphore(0); // Semaphore for third job, initially unavailable
7
8 public Foo() {
9 // Constructor
10 }
11
12 // Method for the first job; prints "first"
13 public void first(Runnable printFirst) throws InterruptedException {
14 firstJobDone.acquire(); // Wait for the first job's semaphore to be available
15 printFirst.run(); // Run the printFirst task; this should print "first"
16 secondJobDone.release(); // Release the second job semaphore, allowing the second job to run
17 }
18
19 // Method for the second job; prints "second"
20 public void second(Runnable printSecond) throws InterruptedException {
21 secondJobDone.acquire(); // Wait for the second job's semaphore to be available
22 printSecond.run(); // Run the printSecond task; this should print "second"
23 thirdJobDone.release(); // Release the third job semaphore, allowing the third job to run
24 }
25
26 // Method for the third job; prints "third"
27 public void third(Runnable printThird) throws InterruptedException {
28 thirdJobDone.acquire(); // Wait for the third job's semaphore to be available
29 printThird.run(); // Run the printThird task; this should print "third"
30 firstJobDone.release(); // Release the first job semaphore, allowing the cycle of jobs to be restarted (if necessary)
31 }
32}
33
1#include <mutex>
2#include <condition_variable>
3#include <functional>
4
5class Foo {
6private:
7 std::mutex mtx; // Mutex to protect condition variable
8 std::condition_variable cv; // Condition variable for synchronization
9 int count; // Counter to keep track of the order
10
11public:
12 Foo() {
13 count = 1; // Initialize count to 1 to ensure first is executed first
14 }
15
16 void first(std::function<void()> printFirst) {
17 std::unique_lock<std::mutex> lock(mtx); // Acquire the lock
18 // printFirst() outputs "first". Do not change or remove this line.
19 printFirst();
20 count = 2; // Update the count to allow second to run
21 cv.notify_all(); // Notify all waiting threads
22 }
23
24 void second(std::function<void()> printSecond) {
25 std::unique_lock<std::mutex> lock(mtx); // Acquire the lock
26 cv.wait(lock, [this] { return count == 2; }); // Wait until first is done
27 // printSecond() outputs "second". Do not change or remove this line.
28 printSecond();
29 count = 3; // Update the count to allow third to run
30 cv.notify_all(); // Notify all waiting threads
31 }
32
33 void third(std::function<void()> printThird) {
34 std::unique_lock<std::mutex> lock(mtx); // Acquire the lock
35 cv.wait(lock, [this] { return count == 3; }); // Wait until second is done
36 // printThird() outputs "third". Do not change or remove this line.
37 printThird();
38 // No need to update count or notify, as no further actions are dependent on third
39 }
40};
41
1// Counter to keep track of the order
2let count = 1;
3// Promises to control the execution order
4let firstSecondControl: (value: void | PromiseLike<void>) => void;
5let secondThirdControl: (value: void | PromiseLike<void>) => void;
6
7// Promise that will resolve when it's okay to run `second`
8const canRunSecond = new Promise<void>((resolve) => {
9 firstSecondControl = resolve;
10});
11
12// Promise that will resolve when it's okay to run `third`
13const canRunThird = new Promise<void>((resolve) => {
14 secondThirdControl = resolve;
15});
16
17async function first(printFirst: () => void): Promise<void> {
18 // printFirst() outputs "first".
19 printFirst();
20 // Update the count to allow second to run
21 count = 2;
22 // Resolve the promise to unblock the second function
23 firstSecondControl();
24}
25
26async function second(printSecond: () => void): Promise<void> {
27 // Wait until the first function has completed
28 if (count !== 2) {
29 await canRunSecond;
30 }
31 // printSecond() outputs "second".
32 printSecond();
33 // Update the count to allow third to run
34 count = 3;
35 // Resolve the promise to unblock the third function
36 secondThirdControl();
37}
38
39async function third(printThird: () => void): Promise<void> {
40 // Wait until the second function has completed
41 if (count !== 3) {
42 await canRunThird;
43 }
44 // printThird() outputs "third".
45 printThird();
46 // After third, there are no more actions, so nothing more to do
47}
48
Time and Space Complexity
The time complexity of the Foo
class methods first
, second
, and third
is O(1)
for each call. This is because each method performs a constant amount of work: acquiring and releasing a semaphore. The use of semaphores is to control the order of execution but does not add any significant computational overhead.
The space complexity of the Foo
class is O(1)
as well. The class has three semaphores as its member variables, and the number of semaphores does not increase with the input size. Hence, the memory used by an instance of the class is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.