coding interviews are shifting away from leetcode to practical programming, so let's practice a question together. Hey, I'm Tara, I'm a senior software engineer and I teach computer science on the internet, and I just finished a pretty intense job search and I wanted to teach a problem that is similar to the problems that I saw during my interview process. So this is building a simple rate limiter. You might get something that looks like this. This is all you get. It's a class that is the simple rate limiter and you have to implement a couple methods. What is a rate limiter anyway? Well, a rate limiter tracks requests made by each user and it ensures that they do not exceed a configured number of requests within a given time window. So when a request arrives, basically we determine whether it's allowed or denied based on whether that user is still within their limit. I'm going to walk through an example. So we have a rate limiter and we're going to allow maximum of three requests every five seconds. So which requests from Quack Overflow are allowed? Side note, Quack Overflow is my little character that is this little duck. Okay, so Quack Overflow makes a request at time equals one. Quack Overflow's never made a request before, so we will allow her request and put a little check mark here. And then I want to keep track of what this window looks like actually. So Quack Overflow has made a request at time equals one. Cool, so then Quack Overflow makes another request at time equals two seconds. Well, she hasn't made more than three requests in the last five seconds, so this is allowed. We still have a request at timestamp one, now we have a request at timestamp two. Okay, now Quack Overflow makes a request at time equals four. That is still allowed because we only have two requests in the last five seconds, not three. So we will allow this request as well, and then I will just extend the window. Okay, now here's where it gets interesting. We make a request at time equals five, but we actually already have three requests in the last five seconds. So we actually just deny this request, and we're not going to add this into our window because this request didn't go through. If we added all of the denied requests to the window, then we would never clear, we would never have like new slots available in the window. So actually the window is going to stay looking the same. Okay, so then a request comes in at time equals seven seconds. We only have two requests in the past five seconds because seven minus five is equal to two. So it's almost like the request at time one doesn't count anymore. So the window actually looks something like this before we add the request at time equals seven, so this is allowed. So this is actually what your test cases could look like. If you notice here in the starter code, I didn't give us any test cases. In my interview experience, I actually saw this go either way. Sometimes I was given a ton of test cases that I had to pass, and sometimes I was expected to write my own test cases. I'm basically just going to translate this exact scenario into Python. So I'll just make a rate limiter for us. So this, this means that we're going to have max requests three within every five seconds. And then basically we should do Quack Overflow's request. You'll notice here that we we have different tracking for different user IDs, so what should happen is we should basically allow, so I should just assert that my limiter. Whoops, my limiter.allow for Quack Overflow at timestamp one, this should be equal to True. Let's speed this up. This is allowed, so this should be True. This at time equals two should be True. This at time equals four should be True. This at time equals five should be False. And this at time equals seven should be True. That is just translating this example into code. So something interesting too, if you'll notice, what am I doing? Every time I get a request in, if I allow it, I'm adding it into this window, which is represented right now by a list. But also I'm not just only doing that, right? Because what happened in this case? So I disallowed this five seconds because my window was of size three or bigger, which is my max capacity. But then when I got the seven, I almost had to evict the calls that were before the time window that I care about. At time equals seven seconds, the window that I care about is two through seven. And so I had to kind of like evict this one. And so that's going to be an important part of how we actually implement this. Okay, this video is already getting long, so tune in for part two where we go over the code and as always, thanks for learning along with me.