{x}
blog image

Print in Order

Suppose we have a class:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

Note:

We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seem to imply the ordering. The input format you see is mainly to ensure our tests' comprehensiveness.

 

Example 1:

Input: nums = [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

Example 2:

Input: nums = [1,3,2]
Output: "firstsecondthird"
Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.

 

Constraints:

  • nums is a permutation of [1, 2, 3].

Solution Explanation for LeetCode 1114: Print in Order

This problem requires designing a mechanism to ensure three threads execute their respective functions (first, second, third) in a specific order. The solution leverages synchronization primitives to enforce this order. The most common and efficient approaches use locks or semaphores.

Approach: Using Locks (Mutexes) or Semaphores

Both locks (mutexes) and semaphores are synchronization tools that prevent race conditions and ensure ordered execution of code blocks across multiple threads. The choice between them depends slightly on the specific needs and language features available. Here's how both approaches work:

1. Locks (Mutexes):

  • Concept: A mutex (mutual exclusion) is a lock that only one thread can hold at a time. If a thread tries to acquire a lock that's already held, it blocks until the lock is released.

  • Implementation: We use two locks (l2, l3 in Python/C++ example):

    • l2 is acquired initially and released after first() execution, allowing second() to proceed.
    • l3 is acquired initially and released after second() execution, allowing third() to proceed.

  • Advantages: Simple to implement in many languages. Suitable when you need to ensure mutual exclusion on a code section.

  • Disadvantages: Can be less efficient than semaphores for more complex scenarios with multiple threads waiting for different events.

2. Semaphores:

  • Concept: A semaphore is a counter that threads can increment (release) and decrement (acquire). If a thread tries to decrement a semaphore whose count is zero, it blocks until the count becomes positive.

  • Implementation: We use three semaphores (a, b, c):

    • a starts at 1, allowing first() to begin. After first(), a is decremented, and b is incremented, allowing second().
    • b starts at 0, blocks second() until first() increments it. After second(), b is decremented, and c is incremented.
    • c starts at 0, blocks third() until second() increments it. After third(), c is decremented, and a is incremented, restarting the cycle.

  • Advantages: More flexible than locks for managing multiple threads waiting on different conditions.

  • Disadvantages: Slightly more complex to understand and implement than locks for simple ordering problems.

Code Examples and Explanation

The provided code examples demonstrate both approaches in Python, Java, and C++. Each function (first, second, third) uses the respective locking/semaphore mechanism to enforce the correct execution order.

Time Complexity: O(1) for each function call, as the lock acquisition/semaphore operations are typically constant time. The overall complexity remains O(1) even though multiple threads are involved because we're dealing with a predetermined sequence of operations.

Space Complexity: O(1), as the amount of extra space used (locks, semaphores) is constant and doesn't scale with the input size.

Choice of Approach

For this particular problem, the lock-based approach (Solution 1) is arguably simpler to implement, particularly if the language's threading primitives offer convenient lock mechanisms. The semaphore-based approach (Solution 2) is often preferred for more complex scenarios where multiple threads might need to wait on different conditions. However, for the simple task of ensuring a strict sequence of three function calls in three threads, both are perfectly valid.