I was able to come up with a graph traversal solution but couldn't get all the test cases.
Question:
There are service_nodes of different micro-services in a system with bidirectional connections in the form of a tree (acyclic graph), where the ith edge connects the micro-services service_from[i] and service_to[i]. Each micro-service is configured with a maximum number of live threads that can be present in its lifecycle, where the ith micro-service can have a maximum of threads[i] threads. The micro-services adjacent to each other must have maximum threads differing by exactly 1.
Some configurations were lost, and only k of the micro-services are known. This information is given as a 2D array, currentValues, of size k x 2 denoting [micro-service index, maximum threads], or, [i, threads[i]]
Find the maximum number of live threads that each micro-service can have such that the total number of live threads in the system is the minimum possible. Return an array of length service nodes where the element denotes the maximum number of live threads for the micro-service.
Note: It is guaranteed that the solution always exists.
Constraints 1 <= node_count <= 105 number of given values for nodes <= node_count 1 <= value of a node <= 105
Example
given graph => (1:3)-(2:x)-(3:x)-(4:x)-(5:3) node 1 to 5 (given) for nodes 1 and 5, we have been given the max thread value as 3 and 3, respectively we need to find all x values such that max sum is minimum and adjacent nodes differ by 1 solution for the above graph => (1:3)-(2:2)-(3:1)-(4:2)-(5:3) so we return [3,2,1,2,3]
Why has the concept of multi threading starting to become so ubiquitous and important in interviews? How does one prepare for them ? I have no idea about it being a non CS graduate!
Videos
Okay, I have read/watched jevkov's videos and blogs. But how can i prepare for FAANG interviews? Last time, this interviewer from Goldman had me trippin' answering questions regarding why use singleton pattern, and what occasion I should use multi-threading. But at my job, I did notice there were tests that implements Runnable interface that is multithreaded, and threadcontext on the controller level. So Im not really exposed to multithreading.
Could someone please share some concise resources that gives insights into must know fundamentals of Java Multithreading/concurrency to prepare for FAANG interviews? Thanks
A much easier way would be to just use Semaphore with run, acquire, release methods:
class Foo {
Semaphore runSecond;
Semaphore runThird;
public Foo() {
runSecond = new Semaphore(0);
runThird = new Semaphore(0);
}
public void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
runSecond.release();
}
public void second(Runnable printSecond) throws InterruptedException {
runSecond.acquire();
printSecond.run();
runThird.release();
}
public void third(Runnable printThird) throws InterruptedException {
runThird.acquire();
printThird.run();
}
}
Leetcode is for code challenges, so we should not give complete solutions, because that wouldn't then be a challenge for you.
So here's a hint: Use two CountDownLatch objects, one to inform method second() that method first() is done, the other to inform method third() that method second() is done. Read the documentation to learn how to use it.
While you are reading through the documentation, I recommend you read the package documentation, to learn more about what features are available for handling multi-threaded code.
UPDATE
To better understand the challenge, assume that Leetcode is using a class like this to test the Foo class.
public class Test {
public static void main(String[] args) throws Exception {
Foo foo = new Foo();
Thread t1 = new Thread(() -> call(foo::first, "first,"));
Thread t2 = new Thread(() -> call(foo::second, "second,"));
Thread t3 = new Thread(() -> call(foo::third, "third."));
// Start threads out of order, with delay between them, giving each thread
// enough time to complete, if not adequately coded to ensure execution order.
t2.start();
Thread.sleep(500);
t3.start();
Thread.sleep(500);
t1.start();
// Wait for threads to complete
t2.join();
t3.join();
t1.join();
// At this point, the program output should be "first,second,third."
}
interface FooMethod {
public void call(Runnable printFirst) throws InterruptedException;
}
private static void call(FooMethod method, String text) {
try {
method.call(() -> System.out.print(text));
} catch (InterruptedException e) {
System.out.println(e);
}
}
}
You cannot modify this code, as it is hidden from you. You have to somehow add code to the Foo class to ensure the 3 Runnable objects are called in the correct order.
Simply adding Thread.sleep() calls to the 3 methods is not the right solution, since this should run regardless of how long of a delay might be added between thread starts by this test below.
You have to use some kind of thread synchronization feature, e.g. monitors, Locks, or Synchronizers.