The ultimate guide to senior engineering interviews. Strategies developed by FAANG engineers on Python concurrency, multithreading, monitors, and event loops. Prep faster for top company questions.

Concurrency in Python 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, Event Loops 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 basic Python would be helpful.

Python Concurrency for Senior Engineering Interviews

<div class="card">
   # Uber Ride Problem
    <div class="ans">
<p>Imagine at the end of a political conference, republicans and democrats are trying to leave the venue and ordering Uber rides at the same time. However, to make sure no fight breaks out in an Uber ride, the software developers at Uber come up with an algorithm whereby either an Uber ride can have all democrats or republicans or two Democrats and two Republicans. All other combinations can result in a fist-fight.</p>

<p>Your task as the Uber developer is to model the ride requestors as threads. Once an acceptable combination of riders is possible, threads are allowed to proceed to ride. Each thread invokes the method <code class="mthd">seated()</code> when selected by the system for the next ride. When all the threads are seated, any one of the four threads can invoke the method <code class="mthd">drive()</code> to inform the driver to start the ride.</p>
    </div>
</div>



<div class="card">
# Solution
<div class="ans">
<p>First let us model the problem as a class. We'll have two methods one called by a Democrat and one by a Republican to get a ride home. When either one gets a seat on the next ride it'll call the <code class="mthd">seated()</code> method.</p>

<p>To make up an allowed combination of riders, we'll need to keep a count of Democrats and  Republicans who have requested rides. We create two variables for this purpose and modify them within a lock/mutex. In this problem, we'll use an object of the <code class="clazz">Lock</code> class when manipulating counts for democrats and republicans.</p>

<p>Realize that we'll also need a barrier where all the four threads, that have been selected for the Uber ride arrive at, before riding away in the same car. This is analogous to the four riders being seated in the car and the doors being shut.</p>

<p>Once the doors are shut, one of the riders has to tell the driver to drive which we simulate with a call to the <code class="mthd">drive()</code> method. Note exactly one thread makes the shout-out to the driver to <code class="mthd">drive()</code>.</p>

<p>The initial class skeleton looks like the following:</p>
<b>

```python
    def __init__(self):
        self.democrats_count = 0
        self.republicans_count = 0
        self.lock = Lock()
        self.barrier = Barrier(4)
        self.ride_count = 0

    def drive(self):
        self.ride_count += 1
        print("Uber ride # {0} filled and on its way".format(self.ride_count))

    def seated(self, party):
        print("\n{0} {1} seated".format(party, current_thread().getName()))

    def seat_democrat(self):
        pass

    def seat_republican(self):
        pass

```
</b>

<p>Let's focus on the <code class="mthd">seat_democrat()</code> method first. For simplicity imagine the first thread is a democrat and invokes <code class="mthd">seat_democrat()</code>. Since there's no other rider available, it should be put to wait. We can use a semaphore to make this thread wait. We'll not use a barrier, because we don't know what party loyalty the threads arriving in the future would have. It might be that the next four threads are all Republican and this Democrat isn't placed on the next Uber ride. To differentiate between waiting Democrats and waiting Republicans, we'll use two different semaphores <code class="mthd">democrats_waiting</code> and <code class="mthd">republicans_waiting</code>. Our first democrat thread will <code class="mthd">acquire()</code> the 
<code class="mthd">lock</code> object, find that no other riders exist, release the  <code class="mthd">lock</code> object and go on to wait at the   <code class="mthd">democrats_waiting</code> semaphore.
</p>

<p>Now it's easy to reason about how we select the threads for a ride. A democrat thread has to check the following cases:</p>

<ul>
  <li><p>If there are already 3 waiting democrats, then we signal the <code class="mthd">democrats_waiting</code> semaphore three times so that all these four democrats can ride together in the next Uber ride.</p></li>

<li><p>If there are two or more republican threads waiting and at least two democrat threads (including the current thread) waiting, then the current democrat thread can signal the <code class="mthd">republicans_waiting</code> semaphore twice to release the two waiting republican threads and signal the <code class="mthd">democrats_waiting</code> semaphore once to release one more democrat thread. Together the four of them would make up the next ride consisting of two republicans and two democrats.</p></li>

<li><p>If the above two conditions aren't true then the current democrat thread should simply wait itself at the <code class="mthd">democrats_waiting</code> semaphore and release the lock object so that other threads can now enter the critical sections.</p></li>  
</ul>

<p>The logic we discussed so far is translated into code below:</p>
<b>

```python
    def seat_democrat(self):
        ride_leader = False

        self.lock.acquire()

        self.democrats_count += 1

        if self.democrats_count == 4:
            # release 3 democrats to ride along
            self.democrats_waiting.release()
            self.democrats_waiting.release()
            self.democrats_waiting.release()
            ride_leader = True
            self.democrats_count -= 4

        elif self.democrats_count == 2 and self.republicans_count >= 2:
            # release 1 democrat and 2 republicans
            self.democrats_waiting.release()
            self.republicans_waiting.release()
            self.republicans_waiting.release()
            ride_leader = True

            # remember to decrement the count of dems and repubs
            # selected for next ride
            self.democrats_count -= 2
            self.republicans_count -= 2

        else:
            # can't form a valid combination, keep waiting and release lock
            self.lock.release()
            self.democrats_waiting.acquire()

        self.seated("Democrat")
        self.barrier.wait()

        if ride_leader is True:
            self.drive()
            self.lock.release()

```
</b>

<p>The thread that signals other threads to come along for the ride marks itself as the <code class="mthd">ride_leader</code>. This thread is responsible for informing the driver to <code class="mthd">drive()</code>. We can come up with some other criteria to choose the rider leader but given the logic we implemented, it is easiest to make the thread that determines an acceptable ride combination as the ride leader.</p>

<p>The republicans' <code class="mthd">seat_republican()</code> method is analogous to the <code class="mthd">seat_democrat()</code> method.</p>

</div>
</div>

<div>
   # Uber Ride Problem
    <div>
<p>Imagine at the end of a political conference, republicans and democrats are trying to leave the venue and ordering Uber rides at the same time. However, to make sure no fight breaks out in an Uber ride, the software developers at Uber come up with an algorithm whereby either an Uber ride can have all democrats or republicans or two Democrats and two Republicans. All other combinations can result in a fist-fight.</p>

<p>Your task as the Uber developer is to model the ride requestors as threads. Once an acceptable combination of riders is possible, threads are allowed to proceed to ride. Each thread invokes the method <code>seated()</code> when selected by the system for the next ride. When all the threads are seated, any one of the four threads can invoke the method <code>drive()</code> to inform the driver to start the ride.</p>
    </div>
</div>



<div>
# Solution
<div>
<p>First let us model the problem as a class. We'll have two methods one called by a Democrat and one by a Republican to get a ride home. When either one gets a seat on the next ride it'll call the <code>seated()</code> method.</p>

<p>To make up an allowed combination of riders, we'll need to keep a count of Democrats and  Republicans who have requested rides. We create two variables for this purpose and modify them within a lock/mutex. In this problem, we'll use an object of the <code>Lock</code> class when manipulating counts for democrats and republicans.</p>

<p>Realize that we'll also need a barrier where all the four threads, that have been selected for the Uber ride arrive at, before riding away in the same car. This is analogous to the four riders being seated in the car and the doors being shut.</p>

<p>Once the doors are shut, one of the riders has to tell the driver to drive which we simulate with a call to the <code>drive()</code> method. Note exactly one thread makes the shout-out to the driver to <code>drive()</code>.</p>

<p>The initial class skeleton looks like the following:</p>
<b>

```python
    def __init__(self):
        self.democrats_count = 0
        self.republicans_count = 0
        self.lock = Lock()
        self.barrier = Barrier(4)
        self.ride_count = 0

    def drive(self):
        self.ride_count += 1
        print("Uber ride # {0} filled and on its way".format(self.ride_count))

    def seated(self, party):
        print("\n{0} {1} seated".format(party, current_thread().getName()))

    def seat_democrat(self):
        pass

    def seat_republican(self):
        pass

```
</b>

<p>Let's focus on the <code>seat_democrat()</code> method first. For simplicity imagine the first thread is a democrat and invokes <code>seat_democrat()</code>. Since there's no other rider available, it should be put to wait. We can use a semaphore to make this thread wait. We'll not use a barrier, because we don't know what party loyalty the threads arriving in the future would have. It might be that the next four threads are all Republican and this Democrat isn't placed on the next Uber ride. To differentiate between waiting Democrats and waiting Republicans, we'll use two different semaphores <code>democrats_waiting</code> and <code>republicans_waiting</code>. Our first democrat thread will <code>acquire()</code> the 
<code>lock</code> object, find that no other riders exist, release the  <code>lock</code> object and go on to wait at the   <code>democrats_waiting</code> semaphore.
</p>

<p>Now it's easy to reason about how we select the threads for a ride. A democrat thread has to check the following cases:</p>

<ul>
  <li><p>If there are already 3 waiting democrats, then we signal the <code>democrats_waiting</code> semaphore three times so that all these four democrats can ride together in the next Uber ride.</p></li>

<li><p>If there are two or more republican threads waiting and at least two democrat threads (including the current thread) waiting, then the current democrat thread can signal the <code>republicans_waiting</code> semaphore twice to release the two waiting republican threads and signal the <code>democrats_waiting</code> semaphore once to release one more democrat thread. Together the four of them would make up the next ride consisting of two republicans and two democrats.</p></li>

<li><p>If the above two conditions aren't true then the current democrat thread should simply wait itself at the <code>democrats_waiting</code> semaphore and release the lock object so that other threads can now enter the critical sections.</p></li>  
</ul>

<p>The logic we discussed so far is translated into code below:</p>
<b>

```python
    def seat_democrat(self):
        ride_leader = False

        self.lock.acquire()

        self.democrats_count += 1

        if self.democrats_count == 4:
            # release 3 democrats to ride along
            self.democrats_waiting.release()
            self.democrats_waiting.release()
            self.democrats_waiting.release()
            ride_leader = True
            self.democrats_count -= 4

        elif self.democrats_count == 2 and self.republicans_count >= 2:
            # release 1 democrat and 2 republicans
            self.democrats_waiting.release()
            self.republicans_waiting.release()
            self.republicans_waiting.release()
            ride_leader = True

            # remember to decrement the count of dems and repubs
            # selected for next ride
            self.democrats_count -= 2
            self.republicans_count -= 2

        else:
            # can't form a valid combination, keep waiting and release lock
            self.lock.release()
            self.democrats_waiting.acquire()

        self.seated("Democrat")
        self.barrier.wait()

        if ride_leader is True:
            self.drive()
            self.lock.release()

```
</b>

<p>The thread that signals other threads to come along for the ride marks itself as the <code>ride_leader</code>. This thread is responsible for informing the driver to <code>drive()</code>. We can come up with some other criteria to choose the rider leader but given the logic we implemented, it is easiest to make the thread that determines an acceptable ride combination as the ride leader.</p>

<p>The republicans' <code>seat_republican()</code> method is analogous to the <code>seat_democrat()</code> method.</p>

</div>
</div>

This lesson solves the constraints of an imaginary Uber ride problem where Republicans and Democrats can't be seated as a minority in a four passenger car.

The Basics

Threading Module

Multiprocessing

Concurrent Package

Async.io

Global Interpreter Lock

Interview Practise Problems

The End

Uber Ride Problem

Uber Ride Problem