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">
   # Dining Philosophers
    <div class="ans">
<p>This is a classical synchronization problem proposed by Dijkstra.</p>

<p>Imagine you have five philosophers sitting on a roundtable. The philosopher's do only two kinds of activities. One: they contemplate, and two: they eat. However, they have only five forks between themselves to eat their food with. Each philosopher requires both the fork to his left and the fork to his right to eat his food.</p>
<p>The arrangement of the philosophers and the forks are shown in the diagram.</p>
<p>Design a solution where each philosopher gets a chance to eat his food without causing a deadlock.</p>
    </div>
</div>


<div class="card">
# Solution
<div class="ans">
<p>For no deadlock to occur at all and have all the philosophers be able to eat, we would need ten forks, two for each philosopher. With five forks available, at most, only two philosophers will be able to eat while letting a third hungry philosopher hold onto the fifth fork and wait for another one to become available before he can eat.</p>

<p>Think of each fork as a resource that needs to be owned by one of the philosophers sitting on either side.</p>

<p>Let's try to model the problem in code before we even attempt to find a solution. Each fork represents a resource that two of the philosophers on either side can attempt to acquire. This intuitively suggests using a semaphore with a permit value of 1 to represent a fork. Each philosopher can then be thought of as a thread that tries to acquire the forks to the left and right of it. Given this, let's see how our class would look like:</p>

```python
class DiningPhilosopherProblem:

    def __init__(self):
        self.forks = [None] * 5
        self.forks[0] = Semaphore(1)
        self.forks[1] = Semaphore(1)
        self.forks[2] = Semaphore(1)
        self.forks[3] = Semaphore(1)
        self.forks[4] = Semaphore(1)

    def life_cycle_of_a_philosopher(self, id):
        while True:
            self.contemplate()
            self.eat(id)

    def contemplate(self):
        sleep_for = random.randint(100, 500) / 1000
        time.sleep(sleep_for)

    def eat(self, id):
        pass
```

<p>That was easy enough. Now think about the eat method. When a philosopher wants to eat, he needs the fork to the left and right of him. So:</p>


<ul>
<li><p>Philosopher A(0) needs forks 4 and 0</p></li>
<li><p>Philosopher B(1) needs forks 0 and 1</p></li>
<li><p>Philosopher C(2) needs forks 1 and 2</p></li>
<li><p>Philosopher D(3) needs forks 2 and 3</p></li>
<li><p>Philosopher E(4) needs forks 3 and 4</p></li>
</ul>

<p>This means each thread (philosopher) will also need to tell us what ID it is before we can attempt to lock the appropriate forks for him. That is why you see the <code class="mthd">eat()</code> method takes in an ID parameter.</p>

<p>We can programmatically express the requirement for each philosopher to hold the right and left forks as follows:</p>

<b>
<code>
<br/>
forks[id]
<br/>
forks[(id+4) % 5]
<br/>
</code>
</b>

<p>So far we haven't discussed deadlocks and without them, the naive solution would look like the following:</p>

```python
class DiningPhilosopherProblem:

    def __init__(self):
        self.forks = [None] * 5
        self.forks[0] = Semaphore(1)
        self.forks[1] = Semaphore(1)
        self.forks[2] = Semaphore(1)
        self.forks[3] = Semaphore(1)
        self.forks[4] = Semaphore(1)

    def life_cycle_of_a_philosopher(self, id):
        while self.exit is False:
            self.contemplate()
            self.eat(id)

    def contemplate(self):
        sleep_for = random.randint(800, 1200) / 1000
        time.sleep(sleep_for)

    def eat(self, id):

        # acquire the left fork first
        self.forks[id].acquire()

        # acquire the right fork second
        self.forks[(id + 1) % 5].acquire()

        # eat to your heart's content
        print("Philosopher {0} is eating".format(id))

        # release forks for others to use
        self.forks[id].release()
        self.forks[(id + 1) % 5].release()

```

<p>If you run the above code, it'll eventually end up in a deadlock at some point. Realize if all the philosophers simultaneously grab their right fork, none would be able to eat. Below we discuss a couple of ways in which this deadlock can be avoided and reach the final solution.</p>

## Limiting philosophers about to eat

<p>A very simple fix is to allow only four philosophers at any given point in time to even try to acquire forks. Convince yourself that with five forks and four philosophers, deadlock is impossible, since at any point even if each philosopher grabs one fork, there will still be one fork left that can be acquired by one of the philosophers to eat. Implementing this solution requires us to introduce another semaphore with a permit of 4 which guards the logic for lifting/grabbing of the forks by the philosophers. The code appears below.</p>

```python
class DiningPhilosopherProblem:

    def __init__(self):
        self.forks = [None] * 5
        self.forks[0] = Semaphore(1)
        self.forks[1] = Semaphore(1)
        self.forks[2] = Semaphore(1)
        self.forks[3] = Semaphore(1)
        self.forks[4] = Semaphore(1)

        self.max_diners = Semaphore(4)

    def life_cycle_of_a_philosopher(self, id):
        while self.exit is False:
            self.contemplate()
            self.eat(id)

    def contemplate(self):
        sleep_for = random.randint(800, 1200) / 1000
        time.sleep(sleep_for)

    def eat(self, id):
        # maxDiners allows only 4 philosophers to
        # attempt picking up forks.
        self.max_diners.acquire()

        # acquire the left fork first
        self.forks[id].acquire()

        # acquire the right fork second
        self.forks[(id + 1) % 5].acquire()

        # eat to your heart's content
        print("Philosopher {0} is eating".format(id))

        # release forks for others to use
        self.forks[id].release()
        self.forks[(id + 1) % 5].release()

        self.max_diners.release()
```
<p>In the code widget below, we slightly tweak the above solution so that our simulation runs for a few seconds. Infinite looping will cause the code widget to throw a timeout exception. For the limited time the test runs, one can see all philosophers take turns to eat food without any deadlock.</p>

</div>
</div>

<div>
   # Dining Philosophers
    <div>
<p>This is a classical synchronization problem proposed by Dijkstra.</p>

<p>Imagine you have five philosophers sitting on a roundtable. The philosopher's do only two kinds of activities. One: they contemplate, and two: they eat. However, they have only five forks between themselves to eat their food with. Each philosopher requires both the fork to his left and the fork to his right to eat his food.</p>
<p>The arrangement of the philosophers and the forks are shown in the diagram.</p>
<p>Design a solution where each philosopher gets a chance to eat his food without causing a deadlock.</p>
    </div>
</div>


<div>
# Solution
<div>
<p>For no deadlock to occur at all and have all the philosophers be able to eat, we would need ten forks, two for each philosopher. With five forks available, at most, only two philosophers will be able to eat while letting a third hungry philosopher hold onto the fifth fork and wait for another one to become available before he can eat.</p>

<p>Think of each fork as a resource that needs to be owned by one of the philosophers sitting on either side.</p>

<p>Let's try to model the problem in code before we even attempt to find a solution. Each fork represents a resource that two of the philosophers on either side can attempt to acquire. This intuitively suggests using a semaphore with a permit value of 1 to represent a fork. Each philosopher can then be thought of as a thread that tries to acquire the forks to the left and right of it. Given this, let's see how our class would look like:</p>

```python
class DiningPhilosopherProblem:

    def __init__(self):
        self.forks = [None] * 5
        self.forks[0] = Semaphore(1)
        self.forks[1] = Semaphore(1)
        self.forks[2] = Semaphore(1)
        self.forks[3] = Semaphore(1)
        self.forks[4] = Semaphore(1)

    def life_cycle_of_a_philosopher(self, id):
        while True:
            self.contemplate()
            self.eat(id)

    def contemplate(self):
        sleep_for = random.randint(100, 500) / 1000
        time.sleep(sleep_for)

    def eat(self, id):
        pass
```

<p>That was easy enough. Now think about the eat method. When a philosopher wants to eat, he needs the fork to the left and right of him. So:</p>


<ul>
<li><p>Philosopher A(0) needs forks 4 and 0</p></li>
<li><p>Philosopher B(1) needs forks 0 and 1</p></li>
<li><p>Philosopher C(2) needs forks 1 and 2</p></li>
<li><p>Philosopher D(3) needs forks 2 and 3</p></li>
<li><p>Philosopher E(4) needs forks 3 and 4</p></li>
</ul>

<p>This means each thread (philosopher) will also need to tell us what ID it is before we can attempt to lock the appropriate forks for him. That is why you see the <code>eat()</code> method takes in an ID parameter.</p>

<p>We can programmatically express the requirement for each philosopher to hold the right and left forks as follows:</p>

<b>
<code>
<br/>
forks[id]
<br/>
forks[(id+4) % 5]
<br/>
</code>
</b>

<p>So far we haven't discussed deadlocks and without them, the naive solution would look like the following:</p>

```python
class DiningPhilosopherProblem:

    def __init__(self):
        self.forks = [None] * 5
        self.forks[0] = Semaphore(1)
        self.forks[1] = Semaphore(1)
        self.forks[2] = Semaphore(1)
        self.forks[3] = Semaphore(1)
        self.forks[4] = Semaphore(1)

    def life_cycle_of_a_philosopher(self, id):
        while self.exit is False:
            self.contemplate()
            self.eat(id)

    def contemplate(self):
        sleep_for = random.randint(800, 1200) / 1000
        time.sleep(sleep_for)

    def eat(self, id):

        # acquire the left fork first
        self.forks[id].acquire()

        # acquire the right fork second
        self.forks[(id + 1) % 5].acquire()

        # eat to your heart's content
        print("Philosopher {0} is eating".format(id))

        # release forks for others to use
        self.forks[id].release()
        self.forks[(id + 1) % 5].release()

```

<p>If you run the above code, it'll eventually end up in a deadlock at some point. Realize if all the philosophers simultaneously grab their right fork, none would be able to eat. Below we discuss a couple of ways in which this deadlock can be avoided and reach the final solution.</p>

## Limiting philosophers about to eat

<p>A very simple fix is to allow only four philosophers at any given point in time to even try to acquire forks. Convince yourself that with five forks and four philosophers, deadlock is impossible, since at any point even if each philosopher grabs one fork, there will still be one fork left that can be acquired by one of the philosophers to eat. Implementing this solution requires us to introduce another semaphore with a permit of 4 which guards the logic for lifting/grabbing of the forks by the philosophers. The code appears below.</p>

```python
class DiningPhilosopherProblem:

    def __init__(self):
        self.forks = [None] * 5
        self.forks[0] = Semaphore(1)
        self.forks[1] = Semaphore(1)
        self.forks[2] = Semaphore(1)
        self.forks[3] = Semaphore(1)
        self.forks[4] = Semaphore(1)

        self.max_diners = Semaphore(4)

    def life_cycle_of_a_philosopher(self, id):
        while self.exit is False:
            self.contemplate()
            self.eat(id)

    def contemplate(self):
        sleep_for = random.randint(800, 1200) / 1000
        time.sleep(sleep_for)

    def eat(self, id):
        # maxDiners allows only 4 philosophers to
        # attempt picking up forks.
        self.max_diners.acquire()

        # acquire the left fork first
        self.forks[id].acquire()

        # acquire the right fork second
        self.forks[(id + 1) % 5].acquire()

        # eat to your heart's content
        print("Philosopher {0} is eating".format(id))

        # release forks for others to use
        self.forks[id].release()
        self.forks[(id + 1) % 5].release()

        self.max_diners.release()
```
<p>In the code widget below, we slightly tweak the above solution so that our simulation runs for a few seconds. Infinite looping will cause the code widget to throw a timeout exception. For the limited time the test runs, one can see all philosophers take turns to eat food without any deadlock.</p>

</div>
</div>

This chapter discusses the famous Dijkstra's Dining Philosopher's problem. Two different solutions are explained at length.

The Basics

Threading Module

Multiprocessing

Concurrent Package

Async.io

Global Interpreter Lock

Interview Practise Problems

The End

Dining Philosophers

Dining Philosophers

Solution