The only guide you’ll need on concurrency & multithreading for senior engineers. Pressure test your skills with real-world practice problems from top companies.

Concurrency in Java is one of the most complex and advanced topics brought up during senior engineering interviews. Knowledge of concurrency and multithreading can put interviewees at a considerable advantage. This course lays the foundations of advanced concurrency and multithreading and explains concepts such as Monitors and Deferred Callbacks in depth. It also builds simple and complete solutions to popular concurrency problems that can be asked about in interviews like the Reader-Writer Problem and the Dining Philosopher Problem. While prior knowledge of concurrency is not required to follow through with this course, familiarity with the very basics of concurrency would be helpful.

Java Multithreading for Senior Engineering Interviews

# Problem Statement
Design and implement a thread-safe class that allows registeration of callback methods that are executed after a user specified time interval in seconds has elapsed.

# Solution
Let us try to understand the problem without thinking about concurrency. Let's say our class exposes an API called <code class="mthd">registerCallback()</code> that'll take a parameter of type <code class="clazz">Callback</code>, which we'll define later. Anyone calling this API should be able to specify after how many seconds should our executor invoke the passed in callback.

One naive way to solve this problem is to have a busy thread that continuously loops over the list of callbacks and executes them as they become due. However, the challenge here is to design a solution which doesn't involve a busy thread.

If we restrict ourselves to use only concurrency constructs offered by Java then one possible solution is to have an execution thread that maintains a priority queue of callbacks ordered by the time remaining to execute each of the callbacks. The execution thread can sleep for the duration equal to the time duration before the earliest callback in the min-heap becomes due for execution.

Consumer threads can come and add their desired callbacks in the min-heap within a critical section. However, whenever a consumer thread requests a callback be registered, the caveat is to wake up the execution thread and recalculate the minimum duration it needs to sleep for before the earliest callback becomes due for execution. It is possible that a callback with an earlier due timestamp gets added by a consumer thread while the executor thread is current;y asleep for a duration, calculated for a callback due later than the one just added.

Consider this example: initially, the execution thread is sleeping for 30 mins before any callback in the min-heap is due. A consumer thread comes along and adds a callback to be executed after 5 minutes. The execution thread would need to wake up and reset itself to sleep for only 5 minutes instead of 30 minutes. Once we find an elegant way of capturing this logic our problem is pretty much solved.
Let's see how the skeleton of our class would look like:


# Class Skeleton

```java
public class DeferredCallbackExecutor {

 PriorityQueue<CallBack> q = new PriorityQueue<CallBack>(new Comparator<CallBack>() {

 public int compare(CallBack o1, CallBack o2) {
 return (int) (o1.executeAt - o2.executeAt);
 }
 });

 // Run by the Executor Thread
 public void start() throws InterruptedException {

 }

 // Called by Consumer Threads to register callback
 public void registerCallback(CallBack callBack) {

 }

 /**
 * Represents the class which holds the callback. For simplicity instead of 
 * executing a method, we print a message.
 */
 static class CallBack {

 long executeAt;
 String message;

 public CallBack(long executeAfter, String message) {
 this.executeAt = System.currentTimeMillis() + executeAfter * 1000;
 this.message = message;
 }
 }
}
```


We define a simple <code class="clazz">CallBack</code> class, an object of which will be passed into the <code class="mthd">registerCallback()</code> method. This method will add a new callback to our min heap. In Java the generic <code class="clazz">PriorityQueue</code> is an implementation of a heap which can be passed a comparator to either act as a min or max heap. In our case, we pass in a comparator in the constructor so that the callbacks are ordered by their execution times, the earliest callback to be executed sits at the top of the heap.

For guarding access to critical sections we'll use an object of the <code class="clazz">ReentrantLock</code> class offered by Java. It acts similar to a mutex. Also we'll introduce the use of a Condition variable. The execution thread will wait on it while the consumer threads will signal it. The condition variable allows the consumer threads to wake up the execution thread whenever a new callback is registered. Let's write out what we just discussed as code. 


```java
public class DeferredCallbackExecutor {

 PriorityQueue<CallBack> q = new PriorityQueue<CallBack>(new Comparator<CallBack>() {

 public int compare(CallBack o1, CallBack o2) {
 return (int) (o1.executeAt - o2.executeAt);
 }
 });
 // Lock to guard critical sections
 ReentrantLock lock = new ReentrantLock();

 // Condition to make execution thread wait on
 Condition newCallbackArrived = lock.newCondition();

 public void start() throws InterruptedException {

 }

 public void registerCallback(CallBack callBack) {
 lock.lock();
 q.add(callBack);
 newCallbackArrived.signal();
 lock.unlock();
 }

 static class CallBack {

 long executeAt;
 String message;

 public CallBack(long executeAfter, String message) {
 this.executeAt = System.currentTimeMillis() + executeAfter * 1000;
 this.message = message;
 }
 }
}
```


Note how in <code class="mthd">registerCallback()</code> method we lock the critical section before adding the callback to the queue. Also, we signal the condition associated with the lock. As a reminder, note the execution thread, if waiting on the condition variable, will not be able to make progress until the consumer thread gives up the lock, even though the condition has been signaled.

Now lets come to the meat of our solution which is to design the execution thread's workflow. The thread will run the <code class="mthd">start()</code> method and enter into a perpetual loop. The flow will be as follows:

<ul>
 <li>Initially the queue will be empty and the execution thread should just wait indefinitely on the condition variable to be signaled.</li>

<li>When the first callback gets registered, we note how many seconds after its arrival does it need to be executed and <code class="mthd" >await()</code> on the condition variable for that many seconds.
</li>

 <li>Now two things are possible at this point. No new callbacks arrive, in which case the executor thread completes waiting and polls the queue for tasks that should be executed and starts executing them.

Or that another callback arrives, in which case the consumer thread will signal the condition variable <code class="mthd">newCallbackArrived</code> to wake up the execution thread and have it re-evaluate the duration it can sleep for before the earliest callback becomes due.
 </li>
</ul>
This flow is caputed in the code below:

# Solution
Let us try to understand the problem without thinking about concurrency. Let's say our class exposes an API called <code>registerCallback()</code> that'll take a parameter of type <code>Callback</code>, which we'll define later. Anyone calling this API should be able to specify after how many seconds should our executor invoke the passed in callback.

One naive way to solve this problem is to have a busy thread that continuously loops over the list of callbacks and executes them as they become due. However, the challenge here is to design a solution which doesn't involve a busy thread.

If we restrict ourselves to use only concurrency constructs offered by Java then one possible solution is to have an execution thread that maintains a priority queue of callbacks ordered by the time remaining to execute each of the callbacks. The execution thread can sleep for the duration equal to the time duration before the earliest callback in the min-heap becomes due for execution.

Consumer threads can come and add their desired callbacks in the min-heap within a critical section. However, whenever a consumer thread requests a callback be registered, the caveat is to wake up the execution thread and recalculate the minimum duration it needs to sleep for before the earliest callback becomes due for execution. It is possible that a callback with an earlier due timestamp gets added by a consumer thread while the executor thread is current;y asleep for a duration, calculated for a callback due later than the one just added.

Consider this example: initially, the execution thread is sleeping for 30 mins before any callback in the min-heap is due. A consumer thread comes along and adds a callback to be executed after 5 minutes. The execution thread would need to wake up and reset itself to sleep for only 5 minutes instead of 30 minutes. Once we find an elegant way of capturing this logic our problem is pretty much solved.
Let's see how the skeleton of our class would look like:


# Class Skeleton

```java
public class DeferredCallbackExecutor {

 PriorityQueue<CallBack> q = new PriorityQueue<CallBack>(new Comparator<CallBack>() {

 public int compare(CallBack o1, CallBack o2) {
 return (int) (o1.executeAt - o2.executeAt);
 }
 });

 // Run by the Executor Thread
 public void start() throws InterruptedException {

 }

 // Called by Consumer Threads to register callback
 public void registerCallback(CallBack callBack) {

 }

 /**
 * Represents the class which holds the callback. For simplicity instead of 
 * executing a method, we print a message.
 */
 static class CallBack {

 long executeAt;
 String message;

 public CallBack(long executeAfter, String message) {
 this.executeAt = System.currentTimeMillis() + executeAfter * 1000;
 this.message = message;
 }
 }
}
```


We define a simple <code>CallBack</code> class, an object of which will be passed into the <code>registerCallback()</code> method. This method will add a new callback to our min heap. In Java the generic <code>PriorityQueue</code> is an implementation of a heap which can be passed a comparator to either act as a min or max heap. In our case, we pass in a comparator in the constructor so that the callbacks are ordered by their execution times, the earliest callback to be executed sits at the top of the heap.

For guarding access to critical sections we'll use an object of the <code>ReentrantLock</code> class offered by Java. It acts similar to a mutex. Also we'll introduce the use of a Condition variable. The execution thread will wait on it while the consumer threads will signal it. The condition variable allows the consumer threads to wake up the execution thread whenever a new callback is registered. Let's write out what we just discussed as code. 


```java
public class DeferredCallbackExecutor {

 PriorityQueue<CallBack> q = new PriorityQueue<CallBack>(new Comparator<CallBack>() {

 public int compare(CallBack o1, CallBack o2) {
 return (int) (o1.executeAt - o2.executeAt);
 }
 });
 // Lock to guard critical sections
 ReentrantLock lock = new ReentrantLock();

 // Condition to make execution thread wait on
 Condition newCallbackArrived = lock.newCondition();

 public void start() throws InterruptedException {

 }

 public void registerCallback(CallBack callBack) {
 lock.lock();
 q.add(callBack);
 newCallbackArrived.signal();
 lock.unlock();
 }

 static class CallBack {

 long executeAt;
 String message;

 public CallBack(long executeAfter, String message) {
 this.executeAt = System.currentTimeMillis() + executeAfter * 1000;
 this.message = message;
 }
 }
}
```


Note how in <code>registerCallback()</code> method we lock the critical section before adding the callback to the queue. Also, we signal the condition associated with the lock. As a reminder, note the execution thread, if waiting on the condition variable, will not be able to make progress until the consumer thread gives up the lock, even though the condition has been signaled.

Now lets come to the meat of our solution which is to design the execution thread's workflow. The thread will run the <code>start()</code> method and enter into a perpetual loop. The flow will be as follows:

<ul>
 <li>Initially the queue will be empty and the execution thread should just wait indefinitely on the condition variable to be signaled.</li>

<li>When the first callback gets registered, we note how many seconds after its arrival does it need to be executed and <code >await()</code> on the condition variable for that many seconds.
</li>

 <li>Now two things are possible at this point. No new callbacks arrive, in which case the executor thread completes waiting and polls the queue for tasks that should be executed and starts executing them.

Or that another callback arrives, in which case the consumer thread will signal the condition variable <code>newCallbackArrived</code> to wake up the execution thread and have it re-evaluate the duration it can sleep for before the earliest callback becomes due.
 </li>
</ul>
This flow is caputed in the code below:

Asynchronous programming involves being able to execute functions at a future occurrence of some event. Designing a thread-safe deferred callback class becomes a challenging interview question. 

Thread Safe Deferred Callback

Asynchronous programming involves being able to execute functions at a future occurrence of some event. Designing a thread-safe deferred callback class becomes a challenging interview question.

The Basics

Multithreading in Java

Java's Memory Model

Interview Practice Problems

Bonus Questions

Beyond the Interview

Java Concurrency Reference

Revision & Quizzes

Thread Safe Deferred Callback

Problem Statement

Solution