The ultimate guide to Ruby concurrency interviews. Developed by FAANG engineers, this course covers Monitors, Deferred Callbacks and problem-solving strategies for Reader-Writer and Dining Philosopher Problems.

Concurrency in Ruby 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 basics of Ruby would be helpful.

Ruby Concurrency for Senior Engineering Interviews

<div class="card">
   # Thread Safe Deferred Callback
    <div class="ans">
<p>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.</p>
    </div>
</div>

<div class="card">

# Solution
<div class="ans">
<p>Let us try to understand the problem without thinking about concurrency. Let's say our class exposes an API called <code class="mthd">registerAction()</code> that'll take a parameter <code class="mthd">action</code>, which will get executed after user specified seconds. Anyone calling this API should be able to specify after how many seconds should our class invoke the passed-in action.</p>

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

<p></p>
<p>One possible solution is to have an execution thread that maintains a priority queue (min-heap) of actions ordered by the time remaining to execute each of the actions. The execution thread can sleep for the duration equal to the time duration before the earliest action in the min-heap becomes due for execution.</p>

<p>Consumer threads can come and add their desired actions in the min-heap within the critical section. The caveat here is that <span class="hi-yl">the execution thread will need to be woken up to recalculate the minimum duration it would sleep for before an action is due for execution</span>. An action with an earlier due timestamp might have been added while the executor thread was sleeping on a duration calculated for an action due later than the one just added.</p> 

<p>Consider this example: initially, the execution thread is sleeping for 30 mins before any action in the min-heap is due. A consumer thread comes along and adds an action 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 achieving this, our problem is pretty much solved.</p>

<p>Let's see what the skeleton of our class would look like:</p>

```ruby
class DeferredCallbackExecutor

  def initialize
    # Priority queue sorted by the earliest execution time
    @actions = PQueue.new {|a,b| b.executeAt > a.executeAt}
    @lock = Mutex.new
    @newCallbackArrived = ConditionVariable.new
  end

  # the method that is signaled and executes the due callbacks
  def start
    while true
    end
  end

  def registerAction(action)
  end
```

<p>Note that we'll not focus on writing our own version of priority queue; instead, we borrow an existing <a href="https://github.com/rubyworks/pqueue/blob/master/lib/pqueue.rb" target="_blank">implementation</a>. When defining our priority queue <code class="mthd">actions</code>, we also pass in the comparator that is used to sort actions based on when they will get executed. Each action has a instance field <code class="mthd">executeAt</code> which helps us compare two actions:</p>

```ruby
@actions = PQueue.new { |a, b| b.executeAt > a.executeAt }
```

<p>For any two actions a and b, the action with an earlier (numerically smaller) value for the <code class="mthd">executeAt</code> field is ranked higher in the min-heap.</p>

<p>We also define a simple <code class="clazz">DeferredAction</code> class, an object of which will be passed into the <code class="mthd">registerAction()</code> method.</p>

<p>For guarding access to critical sections, we'll use an object of class <code class="clazz">Mutex</code>. For coordination among threads, we'll use an object of class <code class="clazz">ConditionVariable</code> which consumer threads can <code class="mthd">signal()</code> to let the executor thread know that a new action has been added. Without the use of a condition variable, the execution thread would busy wait. The execution thread will <code class="mthd">wait()</code> on the condition variable while the consumer threads will <code class="mthd">signal()</code> it. Let's write out what we just discussed as code.</p>

```ruby
class DeferredCallbackExecutor

  def initialize
    # our array that acts as a priority queue
    @actions = PQueue.new {|a,b| b.executeAt) > a.executeAt) }
    @lock = Mutex.new
    @newCallbackArrived = ConditionVariable.new
  end

  # the method that is signaled and executes the due callbacks
  def start
    while true
    end
  end

  # register callback by pushing in the priority queue
  def registerAction(action)
    @lock.synchronize do
      @actions.push(action)
      @newCallbackArrived.signal()
    end
  end

end

class DeferredAction

  def initialize(executeAfter, message)
    @executeAt = DateTime.now.strftime("%s").to_i + executeAfter.to_i
    @message = message
  end

  attr_reader :executeAt
  attr_reader :message
end
```

<p>Note in <code class="mthd">registerAction()</code> method we acquire the mutex lock to protect the critical section which adds an action to the queue. Remember each condition variable has an associated lock and in order to <code class="mthd">signal()</code> the condition variable <code class="mthd">newCallbackArrived</code> we must acquire the <code class="mthd">lock</code> mutex object, which we correctly do. Note the execution thread won't wake up from the <code class="mthd">wait()</code> call until the consumer thread gives up the mutex associated with the condition variable, even though the condition variable has been signaled/notified.</p>

<p>Now let's 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 should be as follows:</p>

<ul>

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

  <li><p>When the first callback arrives, we note how many seconds after its arrival does it need to be invoked and <code class="mthd">wait()</code> on the condition variable for that many seconds. This time we use a variant of the wait method that takes in the numbers of seconds to wait.</p></li>

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

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

```ruby
  def start
    # sleepFor is re-calculated everytime a new action is registered
    @sleepFor = 0
    while true
      @lock.synchronize do

        # if the queue is empty, wait for items to be populated
        while (@actions.size == 0)
          @newCallbackArrived.wait(@lock)
        end

        # if the queue is not empty, execute the earliest due action
        while (@actions.size != 0)
          nextAction = @actions.top

          # calculate sleepFor by deducting the current time from the initialized
          # executeAt time of the action
          @sleepFor = (nextAction.executeAt).to_i - DateTime.now.strftime("%s").to_i

          if (@sleepFor <= 0)
            break
          end

          # wait until either a new action registers or the sleeping duration completes
          @newCallbackArrived.wait(@lock, @sleepFor)
        end

        # remove the action executed
        actionToExecute = @actions.pop
        p "Action required to be execute at #{actionToExecute.executeAt} and executed at #{DateTime.now.strftime("%s").to_i} with message: #{actionToExecute.message}"
      end
    end
  end
```
<p>Pay attention to how we are using <code class="clazz">while</code> loop to wrap the <code class="mthd">wait()</code> method invocation on the condition variables! The idiomatic pattern to <code class="mthd">wait()</code> on a condition variable requires us to check for the associated predicate in a while loop. Note that even in the case of a spurious wakeup the executor thread will either go back to waiting (first while loop) or recalculate a non-zero  time to sleep before an action is due for execution and go back to waiting on the condition variable for that long.</p>

<p>The working of the above snippet is explained below:</p>
<ul>

<li><p>Initially, the queue (actions) is empty and the executor thread will simply <code class="mthd">wait()</code> indefinitely on the condition variable to be notified. We correctly wrap the waiting in a while loop to conform to the idiomatic usage of condition variables.</p></li>

<li><p>If the queue is not empty, say if the executor thread is created later than the consumer threads, then the executor thread will fall into the second while loop. If it's already time to execute an action, it'll immediately break-out of the loop or else sleep for time duration before the first action becomes due.</p></li>

<li><p>For all other happy path cases, adding an action to the queue would always notify the awaiting executor thread to wake up and start processing the queue.</p></li>

</ul>

<p>The complete code appears below in the code widget:</p>
</div>
</div>

</div>
</div>

<div>
   # Thread Safe Deferred Callback
    <div>
<p>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.</p>
    </div>
</div>

<div>

# Solution
<div>
<p>Let us try to understand the problem without thinking about concurrency. Let's say our class exposes an API called <code>registerAction()</code> that'll take a parameter <code>action</code>, which will get executed after user specified seconds. Anyone calling this API should be able to specify after how many seconds should our class invoke the passed-in action.</p>

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

<p></p>
<p>One possible solution is to have an execution thread that maintains a priority queue (min-heap) of actions ordered by the time remaining to execute each of the actions. The execution thread can sleep for the duration equal to the time duration before the earliest action in the min-heap becomes due for execution.</p>

<p>Consumer threads can come and add their desired actions in the min-heap within the critical section. The caveat here is that <span>the execution thread will need to be woken up to recalculate the minimum duration it would sleep for before an action is due for execution</span>. An action with an earlier due timestamp might have been added while the executor thread was sleeping on a duration calculated for an action due later than the one just added.</p> 

<p>Consider this example: initially, the execution thread is sleeping for 30 mins before any action in the min-heap is due. A consumer thread comes along and adds an action 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 achieving this, our problem is pretty much solved.</p>

<p>Let's see what the skeleton of our class would look like:</p>

```ruby
class DeferredCallbackExecutor

  def initialize
    # Priority queue sorted by the earliest execution time
    @actions = PQueue.new {|a,b| b.executeAt > a.executeAt}
    @lock = Mutex.new
    @newCallbackArrived = ConditionVariable.new
  end

  # the method that is signaled and executes the due callbacks
  def start
    while true
    end
  end

  def registerAction(action)
  end
```

<p>Note that we'll not focus on writing our own version of priority queue; instead, we borrow an existing <a href="https://github.com/rubyworks/pqueue/blob/master/lib/pqueue.rb" target="_blank">implementation</a>. When defining our priority queue <code>actions</code>, we also pass in the comparator that is used to sort actions based on when they will get executed. Each action has a instance field <code>executeAt</code> which helps us compare two actions:</p>

```ruby
@actions = PQueue.new { |a, b| b.executeAt > a.executeAt }
```

<p>For any two actions a and b, the action with an earlier (numerically smaller) value for the <code>executeAt</code> field is ranked higher in the min-heap.</p>

<p>We also define a simple <code>DeferredAction</code> class, an object of which will be passed into the <code>registerAction()</code> method.</p>

<p>For guarding access to critical sections, we'll use an object of class <code>Mutex</code>. For coordination among threads, we'll use an object of class <code>ConditionVariable</code> which consumer threads can <code>signal()</code> to let the executor thread know that a new action has been added. Without the use of a condition variable, the execution thread would busy wait. The execution thread will <code>wait()</code> on the condition variable while the consumer threads will <code>signal()</code> it. Let's write out what we just discussed as code.</p>

```ruby
class DeferredCallbackExecutor

  def initialize
    # our array that acts as a priority queue
    @actions = PQueue.new {|a,b| b.executeAt) > a.executeAt) }
    @lock = Mutex.new
    @newCallbackArrived = ConditionVariable.new
  end

  # the method that is signaled and executes the due callbacks
  def start
    while true
    end
  end

  # register callback by pushing in the priority queue
  def registerAction(action)
    @lock.synchronize do
      @actions.push(action)
      @newCallbackArrived.signal()
    end
  end

end

class DeferredAction

  def initialize(executeAfter, message)
    @executeAt = DateTime.now.strftime("%s").to_i + executeAfter.to_i
    @message = message
  end

  attr_reader :executeAt
  attr_reader :message
end
```

<p>Note in <code>registerAction()</code> method we acquire the mutex lock to protect the critical section which adds an action to the queue. Remember each condition variable has an associated lock and in order to <code>signal()</code> the condition variable <code>newCallbackArrived</code> we must acquire the <code>lock</code> mutex object, which we correctly do. Note the execution thread won't wake up from the <code>wait()</code> call until the consumer thread gives up the mutex associated with the condition variable, even though the condition variable has been signaled/notified.</p>

<p>Now let's 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 should be as follows:</p>

<ul>

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

  <li><p>When the first callback arrives, we note how many seconds after its arrival does it need to be invoked and <code>wait()</code> on the condition variable for that many seconds. This time we use a variant of the wait method that takes in the numbers of seconds to wait.</p></li>

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

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

```ruby
  def start
    # sleepFor is re-calculated everytime a new action is registered
    @sleepFor = 0
    while true
      @lock.synchronize do

        # if the queue is empty, wait for items to be populated
        while (@actions.size == 0)
          @newCallbackArrived.wait(@lock)
        end

        # if the queue is not empty, execute the earliest due action
        while (@actions.size != 0)
          nextAction = @actions.top

          # calculate sleepFor by deducting the current time from the initialized
          # executeAt time of the action
          @sleepFor = (nextAction.executeAt).to_i - DateTime.now.strftime("%s").to_i

          if (@sleepFor <= 0)
            break
          end

          # wait until either a new action registers or the sleeping duration completes
          @newCallbackArrived.wait(@lock, @sleepFor)
        end

        # remove the action executed
        actionToExecute = @actions.pop
        p "Action required to be execute at #{actionToExecute.executeAt} and executed at #{DateTime.now.strftime("%s").to_i} with message: #{actionToExecute.message}"
      end
    end
  end
```
<p>Pay attention to how we are using <code>while</code> loop to wrap the <code>wait()</code> method invocation on the condition variables! The idiomatic pattern to <code>wait()</code> on a condition variable requires us to check for the associated predicate in a while loop. Note that even in the case of a spurious wakeup the executor thread will either go back to waiting (first while loop) or recalculate a non-zero  time to sleep before an action is due for execution and go back to waiting on the condition variable for that long.</p>

<p>The working of the above snippet is explained below:</p>
<ul>

<li><p>Initially, the queue (actions) is empty and the executor thread will simply <code>wait()</code> indefinitely on the condition variable to be notified. We correctly wrap the waiting in a while loop to conform to the idiomatic usage of condition variables.</p></li>

<li><p>If the queue is not empty, say if the executor thread is created later than the consumer threads, then the executor thread will fall into the second while loop. If it's already time to execute an action, it'll immediately break-out of the loop or else sleep for time duration before the first action becomes due.</p></li>

<li><p>For all other happy path cases, adding an action to the queue would always notify the awaiting executor thread to wake up and start processing the queue.</p></li>

</ul>

<p>The complete code appears below in the code widget:</p>
</div>
</div>

</div>
</div>

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 ​and we will learn about it in this
lesson​ .

The Basics

API Overview

Brief Intro to Asynchronous Programming

Interview Practice Problems

Bonus Questions

Epilogue

Thread Safe Deferred Callback

Thread Safe Deferred Callback

Solution