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. I filmed this in my hotel room lol. This video assumes that you know what a rate limiter is and we're gonna jump straight to the code. But if you don't know what a rate limiter is and you wanna see me walk through an example plus the algorithm check out my part 1 to this video. So we have our rate limiter. We have our max requests, our window seconds. We should probably store those self dot max requests equals max requests, self dot window seconds equals window seconds. And then we probably also need to store some state, right? Because I'm keeping track for each of my users, in this case quack overflow, I'm almost keeping track of like a list or some other data structure that has the window of requests that they're making. I'm going to do that with maybe something like this where I have a dictionary that's gonna map the user ID to window of requests. So when a user makes a request, we need to sort of see what their current requests are. So there might be a case where we the user has never made a request before. So if user ID not in self dot requests, then I need to add it. And by the way, when I actually interview, I do find myself commenting a lot. It just makes what I'm thinking very clear to myself and my interviewer. Self dot requests, user ID equals and I'm just gonna represent this with an empty list for now. We can talk about later and more optimal data structure for this. Cool. So then from there, I'm gonna just say user requests are equal to self dot requests, user ID, which should now be true for every user, we just added in the ones that we didn't have before. So if user requests if the length of this is greater than or equal to our max request, we're gonna deny the request outright. So we just return false. Otherwise, we need to add it into our request window. So we'll we're adding remember the timestamp that we made this request, right? We're like storing all the timestamps in our window. So we're gonna say um user requests dot append timestamp. And return true. Okay, you probably already caught my bug, maybe you did, maybe you didn't. But I just wanna run our test cases here. Okay, so this fails whenever we are going to try to allow request at time equals seven. So why is that? So whenever we get a new request, let's say at time equals seven, we're never really clearing out the old requests or maybe the expired requests that we don't care about anymore. Because at time equals seven, the window that we care about is not the window of all time, right? The window of interest is from two to seven. So at t equals seven, the window of interest is two to seven. So we kind of have to like evict or get rid of this one. We don't care about that anymore. It's expired. It's not in our window of interest. We kind of need to do something here where we evict old timestamps. So instead of having an empty list here, I actually want to use a Python deque since we're getting these requests in time order, um then they should always be sorted. And so we'll have something where we just want to be able to pop certain things off the front of the list. A queue is a really efficient data structure for that. So instead of having an empty list here, I'm actually just gonna do a deque. Okay, so let's write a nice little evict method. And so I'm gonna take in the timestamp that we wanna evict from and then also the list of user requests that we want to modify. The first thing we need to do is we need to find the target timestamp. So the target timestamp is like seven minus five, which is two. So target timestamp equals two. User requests is like one, two, four. So when user requests and user requests at zero is uh less than the target timestamp, then we need to evict. And so it's really nice. This is why we chose it a deque. But we can just say user request dot pop left. And then down here, I'm gonna do my eviction step. Okay, so this will take in the current timestamp and user requests. So this will take in the current timestamp and user requests. It should modify it on the spot. And then alright, let's see if we pass our test cases. Done. We passed all of our test cases. That's great. So there you have it. That is a basic walkthrough for building a simple rate limiter. Um in an interview, this would probably be part one and you might get a part two. And so I will make a video showing a part two and then part three might be discussing, well, what happens if you have many concurrent users, what how would we scale this to millions of users? What happens if this thing crashes in the middle? It's just represented in memory right now. And so I'm happy to also make a video talking about that more as well. So follow along if you want to learn how to solve problems like this. And as always, thank you for learning along with me.