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">
   # Rate Limiting Using Token Bucket Filter
    <div class="ans">
<p><i>This is an actual interview question asked at Uber and Oracle.</i></p>
<p>Imagine you have a bucket that gets filled with tokens at the rate of 1 token per second. The bucket can hold a maximum of N tokens. Implement a thread-safe class that lets threads get a token when one is available. If no token is available, then the token-requesting threads should block.</p>
<p> The class should expose an API called <code class="mthd">get_token()</code> that various threads can call to get a token.</p>
    </div>
</div>


<div class="card">
# Solution
<div class="ans">
<p>This problem is a naive form of a class of algorithms called the "token bucket" algorithms. A complimentary set of algorithms is called "leaky bucket" algorithms. One application of these algorithms is shaping network traffic flows. This particular problem is interesting because the majority of candidates incorrectly start with a multithreaded approach when taking a stab at the problem. One is tempted to create a background thread to fill the bucket with tokens at regular intervals but there is a far simpler solution devoid of threads and a lesson in making judicious use of threads. This question tests a candidate's comprehension prowess as well as concurrency knowledge.</p>

<p>The key to the problem is to find a way to track the number of available tokens when a consumer requests for a token. Note the rate at which the tokens are being generated is constant. So <span class="hi-yl">if we know when the token bucket was instantiated and when a consumer called <code class="mthd">get_token()</code> we can take the difference of the two instants and know the number of possible tokens we would have collected so far.</span> However, we'll need to tweak our solution to account for the max number of tokens the bucket can hold.
Let's start with the skeleton of our class:</p>
<b>

```python
class TokenBucketFilter:

    def __init__(self, MAX_TOKENS):
        self.MAX_TOKENS = MAX_TOKENS
        self.last_request_time = time.time()
        self.possible_tokens = 0
        self.lock = Lock()

    def get_token(self):
        pass
```
</b>

<p>Note how <code class="mthd">get_token()</code> doesn't return any token type! The fact that a thread can return from the <code class="mthd">get_token()</code> call would imply that the thread <i>has the token</i>, which is nothing more than a permission to undertake some action.</p>

<p>We can envelope the logic of the <code class="mthd">get_token()</code> with the lock we define in the <code class="mthd">__init__()</code> method. Since we'll be manipulating the token count we must ensure that only a single thread is inside the <code class="mthd">get_token()</code> method at any given time. Given the GIL restriction in Python, we may erroneously reason that we don't need to use a lock since only one thread can be active within the <code class="mthd">get_token()</code> method. However, not using a lock can wreak havoc as the thread can be context switched at any time allowing mutation of shared state in a thread unsafe manner.</p>

<p>Moving on, we need to think about the following three cases to roll out our algorithm. Let's assume that the maximum allowed tokens our bucket can hold is 5.</p>

<ul>
<li><p>The last request for token was more than 5 seconds ago: In this scenario, each elapsed second would have generated one token which may total more than five tokens since the last request was more than 5 seconds ago. We simply need to set the maximum tokens available to 5 since that is the most the bucket will hold and return one token out of those 5.</p>
 </li>

  <li><p>The last request for token was within a window of 5 seconds: In this scenario, we need to calculate the new tokens generated since the last request and add them to the unused tokens we already have. We then return 1 token from the count.</p></li>

 <li><p>The last request was within a 5-second window and all the tokens are used up: In this scenario, there's no option but to sleep for a whole second to guarantee that a token would become available and then let the thread return. While we <code class="mthd">sleep()</code>, the lock would still be held by the token-requesting thread and any new threads (processes) invoking <code class="mthd">get_token()</code> would get blocked.</p></li>
</ul>

<p>The above logic is translated into code below:</p>

<b>

```python
class TokenBucketFilter:

    def __init__(self, MAX_TOKENS):
        self.MAX_TOKENS = MAX_TOKENS
        self.last_request_time = time.time()
        self.possible_tokens = 0
        self.lock = Lock()

    def get_token(self):

        with self.lock:
            self.possible_tokens += int((time.time() - self.last_request_time))

            if self.possible_tokens > self.MAX_TOKENS:
                self.possible_tokens = self.MAX_TOKENS

            if self.possible_tokens == 0:
                time.sleep(1)
            else:
                self.possible_tokens -= 1

            self.last_request_time = time.time()

            print("Granting {0} token at {1} ".format(current_thread().getName(), int(time.time())));
```
</b>

<p>You can see the final solution comes out to be very trivial without the requirement for creating a bucket-filling thread of sorts that runs perpetually and increments a counter every second to reflect the addition of a token to the bucket. Many candidates initially get off-track by taking this approach. Though you might be able to solve this problem using the mentioned approach, the code would unnecessarily be complex and unwieldy.</p>

<p>If you execute the code below, you'll see we create a token bucket with max tokens set to 1 and have ten threads request for a token. The threads are shown being granted tokens at exactly 1-second intervals instead of all at once. The program output displays the timestamps at which each thread gets the token and we can verify the timestamps are 1 second apart.</p>

</div>
</div>

<div>
   # Rate Limiting Using Token Bucket Filter
    <div>
<p><i>This is an actual interview question asked at Uber and Oracle.</i></p>
<p>Imagine you have a bucket that gets filled with tokens at the rate of 1 token per second. The bucket can hold a maximum of N tokens. Implement a thread-safe class that lets threads get a token when one is available. If no token is available, then the token-requesting threads should block.</p>
<p> The class should expose an API called <code>get_token()</code> that various threads can call to get a token.</p>
    </div>
</div>


<div>
# Solution
<div>
<p>This problem is a naive form of a class of algorithms called the "token bucket" algorithms. A complimentary set of algorithms is called "leaky bucket" algorithms. One application of these algorithms is shaping network traffic flows. This particular problem is interesting because the majority of candidates incorrectly start with a multithreaded approach when taking a stab at the problem. One is tempted to create a background thread to fill the bucket with tokens at regular intervals but there is a far simpler solution devoid of threads and a lesson in making judicious use of threads. This question tests a candidate's comprehension prowess as well as concurrency knowledge.</p>

<p>The key to the problem is to find a way to track the number of available tokens when a consumer requests for a token. Note the rate at which the tokens are being generated is constant. So <span>if we know when the token bucket was instantiated and when a consumer called <code>get_token()</code> we can take the difference of the two instants and know the number of possible tokens we would have collected so far.</span> However, we'll need to tweak our solution to account for the max number of tokens the bucket can hold.
Let's start with the skeleton of our class:</p>
<b>

```python
class TokenBucketFilter:

    def __init__(self, MAX_TOKENS):
        self.MAX_TOKENS = MAX_TOKENS
        self.last_request_time = time.time()
        self.possible_tokens = 0
        self.lock = Lock()

    def get_token(self):
        pass
```
</b>

<p>Note how <code>get_token()</code> doesn't return any token type! The fact that a thread can return from the <code>get_token()</code> call would imply that the thread <i>has the token</i>, which is nothing more than a permission to undertake some action.</p>

<p>We can envelope the logic of the <code>get_token()</code> with the lock we define in the <code>__init__()</code> method. Since we'll be manipulating the token count we must ensure that only a single thread is inside the <code>get_token()</code> method at any given time. Given the GIL restriction in Python, we may erroneously reason that we don't need to use a lock since only one thread can be active within the <code>get_token()</code> method. However, not using a lock can wreak havoc as the thread can be context switched at any time allowing mutation of shared state in a thread unsafe manner.</p>

<p>Moving on, we need to think about the following three cases to roll out our algorithm. Let's assume that the maximum allowed tokens our bucket can hold is 5.</p>

<ul>
<li><p>The last request for token was more than 5 seconds ago: In this scenario, each elapsed second would have generated one token which may total more than five tokens since the last request was more than 5 seconds ago. We simply need to set the maximum tokens available to 5 since that is the most the bucket will hold and return one token out of those 5.</p>
 </li>

  <li><p>The last request for token was within a window of 5 seconds: In this scenario, we need to calculate the new tokens generated since the last request and add them to the unused tokens we already have. We then return 1 token from the count.</p></li>

 <li><p>The last request was within a 5-second window and all the tokens are used up: In this scenario, there's no option but to sleep for a whole second to guarantee that a token would become available and then let the thread return. While we <code>sleep()</code>, the lock would still be held by the token-requesting thread and any new threads (processes) invoking <code>get_token()</code> would get blocked.</p></li>
</ul>

<p>The above logic is translated into code below:</p>

<b>

```python
class TokenBucketFilter:

    def __init__(self, MAX_TOKENS):
        self.MAX_TOKENS = MAX_TOKENS
        self.last_request_time = time.time()
        self.possible_tokens = 0
        self.lock = Lock()

    def get_token(self):

        with self.lock:
            self.possible_tokens += int((time.time() - self.last_request_time))

            if self.possible_tokens > self.MAX_TOKENS:
                self.possible_tokens = self.MAX_TOKENS

            if self.possible_tokens == 0:
                time.sleep(1)
            else:
                self.possible_tokens -= 1

            self.last_request_time = time.time()

            print("Granting {0} token at {1} ".format(current_thread().getName(), int(time.time())));
```
</b>

<p>You can see the final solution comes out to be very trivial without the requirement for creating a bucket-filling thread of sorts that runs perpetually and increments a counter every second to reflect the addition of a token to the bucket. Many candidates initially get off-track by taking this approach. Though you might be able to solve this problem using the mentioned approach, the code would unnecessarily be complex and unwieldy.</p>

<p>If you execute the code below, you'll see we create a token bucket with max tokens set to 1 and have ten threads request for a token. The threads are shown being granted tokens at exactly 1-second intervals instead of all at once. The program output displays the timestamps at which each thread gets the token and we can verify the timestamps are 1 second apart.</p>

</div>
</div>

Implementing rate limiting using a naive token bucket filter algorithm.

The Basics

Threading Module

Multiprocessing

Concurrent Package

Async.io

Global Interpreter Lock

Interview Practise Problems

The End

Rate Limiting Using Token Bucket Filter

Rate Limiting Using Token Bucket Filter