We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free

Please read our definitive guide on Google's hiring process and questions

Rust Interview with a Google engineer

Watch someone solve the rate limiter problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Rate Limiter

Interview question

Whenever you expose a web service / api endpoint, you need to implement a rate limiter to prevent abuse of the service (DOS attacks). Implement a RateLimiter Class with an isAllowed() method. Every request comes in with a unique clientID. Deny a request if that client has made more than N requests in the past T milliseconds.

Interview Feedback

Feedback about Professor Squirrel (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Strengths: + Did extremely well on both problem solving and coding. Clearly laid out their idea in terms of high level APIs upfront. Nice touch of considering amortization in complexity. + Nice handling of test cases, multithreading, exponential backoff on the client side. + Great code hygiene with comments and variable names. Weakness: - (Nit): Starting with a test case can help guide your code better and you won't have to correct it later. Overall: Strong Hire. I couldn't find anything particular to look out for.

Feedback about Doctor Squab (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

That was a lot of fun, and felt very helpful -- especially the actionable feedback on writing test cases first. Also great to know about the different types of interviews. Thanks again!

Interview Transcript

Doctor Squab: Cool. Yeah, let's do the quick intro. Is this your first time on interview IO?

Professor Squirrel: No, I've done a ton of these in the past.

Doctor Squab: Okay, cool, cool, cool. Okay, so a quick intro. I am l six at Google. I have been doing these interviews in Google forever. Today we are doing a coding exercise. Right. I wanted to see, like, what kind of rules are you applied for?

Professor Squirrel: I guess like maybe l four programming? Yeah.

Doctor Squab: Okay, sound good? Okay, so, Alpha, they will heavily focus on living on coding more than system design, so you have to pretty much do kick ass job at programming. Okay, so let's get started, I guess these are typically 45 minutes interviews, and people do these with like 40 minutes for the main interview and then five minutes for, you know, present, raise, question answering, stuff like that. So. So what we can do is that we can look at the clock and we can cap it at. Right now it's like three minutes. So we can. We can go based on that when clock, it's 43 or 44 minutes.

Professor Squirrel: Sounds good.

Doctor Squab: Cool.

Professor Squirrel: Okay.

Doctor Squab: I think you need to change the language. Which language do you want?

Professor Squirrel: I'd like to use rust.

Doctor Squab: Rust. There you go.

Professor Squirrel: Okay. Do you want me to read the question?

Doctor Squab: Yeah, go ahead, please.

Professor Squirrel: Sure. Okay. Okay, let's see here. So, expose a web service or API endpoints. I don't have any experience with web development, but I'll sort of fill in the gaps as I need. Sure, sounds good, sounds good. I need to implement a rate limiter to prevent abuse of the service. Okay, implement a rate limiter class with an isallowed method, which presumably returns a boolean. Every request comes in with a unique client id, and we want to deny a request if that client has made more than n requests in the past t milliseconds. Whoa, cool. Yeah, let me start sort of like sketching out my thoughts and asking some questions. So it sounds like sort of inputs are the values of n and t. I'm imagining there would be like, kind of a constructor function that has like the sort of like, limit on the number of requests and the timing of the number of milliseconds, something like that. Am I correct in those assumptions or should these be like sort of compile time constants that are actually fixed no matter what?

Doctor Squab: No, this is good. This is good. Yes.

Professor Squirrel: Okay, great. Limiter. And I'll fill in the body create limiters and we'll get to that in a sec. Okay, so right now we have this is allowed and it'll return a boolean and is allowed as checking requests. Client a unique client id. Can I assume that these are integers? The client id is unique.

Doctor Squab: Yeah, sure.

Professor Squirrel: So, okay, so this is kind of what I'm thinking about in terms of the API surface of this rate limiter class.

Doctor Squab: Okay.

Professor Squirrel: Let me actually think about how to implement it because I, yeah, I'm not sure how to do that. So let's think. So I guess since the requests come in for a given client and this sort of criteria to ban or to deny is specific to a specific client, it seems like we really want to focus on solving the problem individually as like, how would you solve it if there was only one client? And then it probably is fairly simple to just do the same thing per client id. So I'll restrict my attention now to ignore the fact that there's multiple clients. We want to deny a request if that client has made more than n requests. Okay, so there's a number of requests and that's a limit. And then t milliseconds. Okay. So probably we'll have some way to get the current time in milliseconds and more than n requests. More than n. Okay. There's details of like off by ones and stuff, but basically. So I want to be able to know how many requests the client's made last in this case. So I guess, yeah, I won't think about trying to do sort of approximations and fuzziness, because I think that'll add too much complexity for me to manage. But I'll assume we're trying to do something very exact, if that's all right with you. And the goal is to be able to answer the question of how many requests have happened in the past two milliseconds. So probably what that could look like is, I'll have a queue. Are you still there? It says you're disconnected.

Doctor Squab: No, I'm here.

Professor Squirrel: Okay. Okay, sure. So I'm thinking probably there will be a queue. Probably should write this down, queue requests. And it'll be like tagged each as a timestamp. And then to sort of, how do I say this? To check how many recent requests there are. I'll clean up the queue by popping until there's no stale requests. And then I'll check its length. Do you have a question?

Doctor Squab: Yeah, I don't know. It's kind of showing me. Okay, now it's showing me. No, I saw that you're typing, but I couldn't see it. Okay, now see it. Okay. It showed up pretty late.

Professor Squirrel: Yeah, yeah, yeah.

Doctor Squab: Okay.

Professor Squirrel: Hopefully we don't have any more problems, but definitely let me know. Yeah. Gotcha. Gotcha. Okay, so, yeah, this is kind of what I'm thinking. I feel pressured for time to get it all down in code. But before I jump into writing code, do you have questions for me?

Doctor Squab: No. So if I understood correctly. So you're keeping a queue for each of the requests and then. Yeah. And then you're clearly. This sounds good. And then. How are you going to do this? Extend this idea for multiple clients?

Professor Squirrel: Yeah, I think one could just have a hash table of many queues.

Doctor Squab: Okay, sounds good. Okay, and what's the time complexity and space complexity for this?

Professor Squirrel: That's a great question. So those sound like hard questions to answer because they're maybe amortized isn't the right word, but that's the one that's coming to mind. It feels like, feels like. It's a subtle thing, but let me think about it. So we construct one of these rate limiter objects, and then it kind of feels like the worst case is maybe just one client. But anyway, so assuming there's one client. Wow. Let me think about this. I mean, the sort of space complexity is it grows with the number of requests, but it's capped by the number of requests in a short interval. So I don't know how to, like, quite describe that. But a worst, worst case would be like o of n space complexity. If we're being very broad as far as time complexity, I want to say it's kind of like amortized o of one, because every request involves pushing to the queue. And when you pop from the queue, you might do many during one operation. Many pops, that is. But the total number of pops overall is bounded by the number of requests that have come in. So you're not actually doing more than linear work once you've averaged everything out, if that makes sense.

Doctor Squab: Yes. Sounds good. Yep, I think looks good. You can go ahead and start a new.

Professor Squirrel: Sure. Yeah, let's give it a try. So I said I would have a hash map from client id to a queue of requests, which are timestamps. I'm not really sure what type of timestamp will be, but I'll make it up and I'll say it's a 64 bit integer and that's the, let's see, recent requests. I'll call it keyed client. Okay. Yeah. Okay. So that's the thing. I also guess want to keep these numbers around, so I'm going to call them n and t. Actually I think that'll make it a little easier to write code, but in real life I think I would use longer names, but I'm just sort of trying to save typing, if that makes sense. Okay, so there's n and t and maybe that's all I need. So constructor here would be pretty simple. It'd basically just be like you pass in n requests. Cool. And so then the idea here, oh yeah, right. We got to construct one of these request new. Cool, right. I guess the red squiggly isn't telling you I need to import a bunch of stuff. I don't know how much you care about this actually compiling, but I guess that's what we would do if we cared. Okay, so I have a client id. It's coming in. Yes. I want to get the specific queue of recent requests, get get mute client id or default, which would be an empty queue. Or maybe it's really one entry or default. That's the syntax. So then I have the queue of requests and that's a good start. I want to, oh actually, sorry. So I want to clarify, like there's an isalloud method. Every request comes into the client do deny request. So yeah, just to try to understand this, like is this is allowed method being called exactly once per request? Can I treat the call as like an indication that there is a request? Does that make sense?

Doctor Squab: Yeah, this is a good question. Yeah, it is called once per request. And based on the, think of this as a server, a service is running, a request comes, service has this in memory instance of rate limiter, and for each request it calls ratelimiter is allowed with the request id. And if it returns, if says yes, then it allows that request to go ahead and access the resource or whatever. And if not, then it just returns.

Professor Squirrel: Great. Yeah, it sounds great to me. Sounds good. Thanks. Okay, so trying to write the code here. So is allowed client id. I have the queue I wanted to first, like so called clean up the queue, I guess. Or maybe before that I'm supposed to, let's think about the order here. So things I want to do is push to the queue, clean up the queue limit to n. Well, not to enter t. Yeah, okay. Actually that's not such a huge problem. Yeah, okay. Wow. Boy. So let me think about what order to do this in. So if I have like five requests that I've gotten and the limit is five more than n requesting clients more than n request in the best milliseconds, I mean, I guess, how do I say time is kind of continuous? So I feel like the off by ones are almost like not important with respect to time in more than n requests in less two milliseconds. I mean, maybe I'll just write something down and then I'll look at it and I'll see if it looks reasonable. But the idea would be append the current timestamp. So let, and then we'd have some API call to get the current time. I kind of mock it out if that's oktime or something. Get time produces agency for. So that would be the thing. And then I'd push current to the back of the queue. And then I would say sort of like, wow, okay, 1 second. How to write this? So q peak front, I guess front. Yeah, I'm not sure how to write this, but I'll write it like this. So file that's timestamp equals q out front if timestamp less than per time, sort of saturating sub self time limit. Okay, wait, so this is the case where, so if I have current time minus this interval, which gives me the time in the past, if the timestamp is outside of that time, then yes, I'm continuing. Otherwise I want to actually put it back. Yes. And break. This is really wonky looking code probably, but this feels like it has the correct logic. So maybe I'll come back and clean it up if I have time at the end. So that's the basic idea there. And then the idea would be to say if there's more than n requests. So this is like Qn let deny equals qlen greater than n. Well, we can just invert this, obviously. If I guess cast one of these two sides and then we'll be fine. So yes, this is the general idea I have. Yeah, I mean this is the basic sort of sketch of it. Is there anything in particular that you want to see from me? Like should I sort of do a run on a sample input to try to check for edge cases and bugs?

Doctor Squab: Yeah, let's, let's write a test case for this. I'll start typing the test case.

Professor Squirrel: Sure.

Doctor Squab: And in the bottom of typing. Okay.

Professor Squirrel: Yeah, sure.

Doctor Squab: Let's see. Okay, let's say, and let's say the at 100 times n is two and. Okay. Yeah, here's your test case. You can design it whichever way.

Professor Squirrel: Sure. Okay, let me take a look. I guess I'll first try to decide what I think the answer should be for all this.

Doctor Squab: Yeah, yeah, maybe you could type it up next to it. Next to the live.

Professor Squirrel: Sure, that sounds great. So n equals two, which is. Remind me. N is the number. Okay. The number of requests. And you have to make. You can't surpass that in an interval of t milliseconds. Okay. And t is 100. Okay. There's definitely gonna be some subtle off by ones, but let's see. So 100 milliseconds in the past. 100 milliseconds. Milliseconds. This is kind of a meta question, but, like, how much do you care about off by ones in terms of timestamps? Like, a number of milliseconds? Like, is that important?

Doctor Squab: Yeah, no, it's just not. I mean, it's a number of milliseconds. I mean, just the absolute times and off by one. I don't care. Greater than equal, I guess you are trying to say. Is that what you're referring to?

Professor Squirrel: Yeah, and I'm talking about timestamps, not number of requests. But, like, that's basically my question is, like, if there is, like, a difference of plus minus one in the number of milliseconds, that's okay.

Doctor Squab: Yeah. See, as long as you are, you know, consistent about it, that you want to deny it 99 or 100, I'm okay with that. As long as you're persistent. That you always deny it 99 or always deny it 100.

Professor Squirrel: I see. Okay. Okay. Okay. Sure. Because I guess, like, what I would be thinking about sort of in real code is that it's probably unlikely to matter because it's, like, one millisecond, and it's one of these things where, like, rounding errors, like, you could spend a lot of time thinking about them. But I think you wouldn't make your code that much more useful if you did. But in any case, let's. Let's look at this. So n equals two. T is 100. The first request comes in at time one, and they're all for the same client, so that's good. And at time one, we definitely say yes, which I'll say t for true, maybe like yes. Okay, so at time two, we definitely say yes as well. And the idea should be that our code pushes to the queue and remembers all this. Okay, so then, yeah, time at the third request. So t equals 100, I guess. Yeah. I mean, let's just see what the code currently does or. Well, yeah, let's make a decision about what we want it to do, I guess. So in the last 100 milliseconds, which I guess, let's say, includes one through 100 inclusive. Sure. So let's say we want to deny this. Yeah, I think that's a pretty reasonable choice there. And so that looks like, I guess, how do I say one question I actually didn't think to ask would be like a denied request. Should that count towards the quota, the limit, or not?

Doctor Squab: No, it should not count because you denied it.

Professor Squirrel: Yeah. Okay, that sounds good. I'll make sure the code actually does that. But I wasn't really thinking hard about that before now. So let's. Maybe I'll just skim the code now. So I see. Fascinating. Okay. Okay. So I want to say this actually only happens at the end. This is like, if I'm guessing, this is probably what I want, but I'll come back to this. Okay. Okay. Let me come back in a moment. So back to the example. What do I expect from this? So 50 through 150. Let me think about this. So the one should have been cleaned up. The hundred didn't count. 15, 150. There are 100 apart. So if my window includes 100 elements, only one of them ends up in the window. Basically they. I think they all get cleaned up. So we'll say yes. And it's actually, how do I say this? Like, yeah, it's even if n equals one would be cool. So then next up, we're looking at this pair of things. They're both in the window, but it's still. Yes, because it's allowed. And then lastly, for 200, we're looking at 199 and 200 and 150, which are sort of too close together. The window is already full, I guess is the way I should think about it. This feels really helpful, actually. Maybe I should have drawn a test case earlier. But anyways, the window feels full and will deny this one. So this is my intention for the code is to do this, I guess. Now I'd like to run through it and catch any bugs or any deviations from that, if that sounds good to you.

Doctor Squab: Sounds good. Yeah, this is the expected output, I believe.

Professor Squirrel: Sweet. Okay, sounds good. Sounds good. Okay, so let's, like, trace the code and see what happens. So t equals 100 and equals two. Put those. Okay, so the constructor fine is allowed self client ids. Client ids.

Doctor Squab: Yeah.

Professor Squirrel: Fine. And we get the cube. Okay. So we get a current timestamp. Yeah. Let's see what the code does with this. So time equals one or first cleaning up the queue, limiting to t. That makes sense, I think, like limit. So I want to limit from the range curatime minus key up to current time. If that's 100, let's say. But I don't want to include both elements because then I'd have 101. So let's say we do. This is the goal. And so how are we doing that? We're looking at the front of the queue. And if timestamp less than. Yeah, 1 second. One sec. Minus t. That makes sense. Um. Compare it to timestamp. Boy. Okay. Okay. If timestamp. Okay, so I think really it should be like, well, let's think about this. If less than, then you keep popping. It's greater than or equal. Maybe I'll write this the other way. Yeah, I'm definitely going to invert this condition. So, greater than or equal. I want to do this stuff otherwise I can. That looks cleaner if the timestamp is. Yeah, but now actually I want this to be greater. So that's, that's, I think, what I want. So if timestamp is greater than. And I think this works even with ed cases like when t equals or. Sorry. When the current time is one and we subtract 100, we'll get zero. And so timestamps that are equal to zero. No, there's actually edge cases. So annoying. It would make my life easier if these were signed integers. So I'm going to pretend timestamps are signed like I 64. Is that okay with you?

Doctor Squab: Yeah, that's fine.

Professor Squirrel: Yeah. Okay, cool. Because then the edge case will actually work. Let's do that. And I guess timestamps. Let's see. The queue has to have I 64. The current time has to be I 64. Fine. Great. Anyways, ok, so now I think I'm good because if I'm inbounds, I keep it and I break.

Doctor Squab: Ok, great.

Professor Squirrel: Ok, I'm happy with this. The Q cleanup. And then I want to check the off by ones on the n. So if I want this to be strictly. This. Ok. Yeah, yeah, yeah. This is not the most obvious code, but like, how do I say this? Yeah, yeah. I mean, how do I say this? I think the code is reasonable. I'm trying to think if I can write it in a slightly cleaner way. But the general idea here, I think is good. Yeah. Let me trace you the full example. So with time one, we'll push the queue and then we'll say the queue length is one but n is two. So. Excuse me, the queue length. I'm sorry. So we haven't pushed it yet. We'll push it after.

Doctor Squab: No, no, I'm good. Good.

Professor Squirrel: Yeah. Okay. Yeah. So 150. I mean, how do I say this? I feel fairly confident in the Code.

Doctor Squab: Okay.

Professor Squirrel: Is there anything else you want to see from me? Like do you want to see an Example Sort of traced in more detail, or is there Sort of like.

Doctor Squab: Yeah, do you want to write a test case for this?

Professor Squirrel: Okay, sure, sure. Yeah, I'll try to test case.

Doctor Squab: Well, I'm also interested in like, what kind of scenarios you will test for this.

Professor Squirrel: Yeah, I see, yeah. Okay, great questions. I think there's some edge cases that I'm probably not handling of t and n being weird numbers. So let's say I think it makes sense for t to be only positive. Let's think about that. So past t milliseconds, yeah. An interval of zero would mean denying every Request, which I think is pretty Wonky. So let's say we have to have t greater than zero, okay. And n being zero would also mean denying every Request, okay has made more than n requests. So let's say we'll force n to be greater than zero. And the way I think I would like to do that in Code is I would write assertions in the constructor. So like zero. And you would like to document it. So you'd have a comment here that says like describes basically what the valid inputs are.

Doctor Squab: Okay.

Professor Squirrel: Interval Ms. And so that's kind of what I would want to do here, although I'd definitely be happy as well to handle cases of zero and just happen, the weird edge cases where you deny every request if that's something that the user of this API really wants. Okay, so that's those messages down. I think aside from that, I guess you could test a mix of client ids, but it's sort of very clear from the code that they don't mix. Like each client is treated very independently and so it's not something I would be super concerned to actually write tests for, if that's fair enough to say.

Doctor Squab: Yeah.

Professor Squirrel: Let'S see. Uh, what would I want to write tests for? Um, I guess you could have, so I'll just write like various timestamps. Like it could be like you could do negative timestamps because I'm saying those are allowed. Uh, well, yeah, sure. So like you can test like minus five and then like, sorry, so, so, okay, test case. I'll say t equals t equals one. It's like a reasonable test case. Yes, and n. So those are some missed cases. Then maybe you'd have an input like, yeah, t equals zero, t one, t two, or something. Then I would expect this to be, what would I explain? So yes, yes, yes. I think because the idea would be that is that the current thing is the only thing that has happened. Oh, yeah. One cool thing we could do is have things come in with the same. Oh, okay, sorry. So let me back up here. So this is one test case I like. Another test case I like would be to test something like this. I think multiple of the same timestamp is totally possible and we want to handle it correctly, and I think we are. But it's like this would be a good test case to write. I think. I think one thing that didn't occur to me until now is what if you had sort of going down? Like, I guess there's a question for you is like, can we assume that the clock or the time source is actually monotonic, or might it be doing.

Doctor Squab: Yeah, I think that is fair assumption to make right now. Okay, I think let's pause this part here.

Professor Squirrel: Sure.

Doctor Squab: So now let's say that the server is getting, you know, multiple requests from different clients, right? And how would you allow, how will you handle multiple clients simultaneously?

Professor Squirrel: I'm not sure I understand what you mean.

Doctor Squab: Like, so let's say, let's say that, you know, the server is allowed to, let's say this is used for some payment processing, for example. Right, okay. And hundreds of phones are connected and they are processing their payments like multiple apps are somebody submitting requests. And now on. And you are, you are providing a service which transfers money from one account to another and you are using this. Right. So my point is that multiple requests can come at exactly same time. So how is server going to handle that with this implementation of the code?

Professor Squirrel: That's a great question. So I guess it seems kind of like the middle test case here, where you have timestamps being equal, I think. Oh, maybe. I think I see what you're getting at the API as written. It's actually kind of fun because in rust, the compiler statically, well, how do I say this? At compile time, data races are prevented, so it's impossible to write code that has unsynchronized accesses to data. So that the first thing that'll happen is if you try to write code where you're concurrently accessing an unsynchronized data structure, you'll get a compile time error, which I think is really cool. I think rust is great, and that's one thing that's great about it. That being said, if what you were trying to do was have things happen very concurrently, then to fix that compiler error would probably add locks. Specifically, I'm imagining adding a mutex around the rate limiter object such that the because the sort of is allowed method doesn't take super long to run. And like, I guess I can think hard if like it was a really really really high throughput thing. Like maybe you'd have to do some deep thinking about data structure design, but for the sort of simple case you just want to add a lockdown. The is allowed method gets sort of called, how do I say this? Accesses get sequentially ordered and only one mutation happens at a time. If that makes sense.

Doctor Squab: Yeah, can we improve this a little bit? Because that means that this class becomes strictly serial.

Professor Squirrel: Right, right.

Doctor Squab: Yeah, that doesn't sound that good of a.

Professor Squirrel: You know, that's actually a really good point and I appreciate that feedback. One thing that's really nice about this problem is that the data structure we're using is very very amenable to allowing parallelism for different clients. So if different people are accessing the recent requests, then you could concurrently compute the is allowed for different client ids simultaneously. So I guess what that would actually look like in code. If you like, you add a mutex to each of these and, let's see, mutex. Oh, I need to import it. So use the sync maybe. So you'd add mutex to each of these and then this recent request entry, client id or default log. You would lock the queue and then get compile time errors. Popfile result. Oh, lock. Yeah, so the standard library mutex has API detail where you need to unwrap, but that's the general idea. And then it needs to be mutable. But then I think we're like literally done. And the fact that the compiler guides us through all of those details is awesome in my opinion.

Doctor Squab: Yeah, yeah, perfect. Yeah, this is what I was looking for, that you probably need a client level access, right. Rather than. Okay, now let's say that the system is, right now we are imposing per client limits right now I want to extend that limit to an entire system. That what rate limit is trying to do is that it is trying to protect a resource which has certain constraints that how many people can access it eventually. That's why we have this rate limiter. So let's say that entire system has a new limit called m. That doesn't matter how many clients are there, not more than these many active requests can access it. And that's much bigger than the end per client request. So m much much greater than n. And we just want to impose that limit. How would you tweak your code to do that?

Professor Squirrel: That's a great question is that are we still assuming there is like n as in Nancy limit as well, or we.

Doctor Squab: So that one particular client doesn't kind of take away entire resource, but the m is that the system is just constrained with how many deployments we have done.

Professor Squirrel: Okay, and is the m as in Mike, is it also for the past t milliseconds, is that the.

Doctor Squab: No, that has nothing to do with the time. It's just that over at any. I mean, yes, in a way that at any time there should not be. You're right, in any given tea time there should not be more than m active requests. Accessing the resource.

Professor Squirrel: Requests should be allowed. Okay, so I think I understand what you're asking with this. Let me think about how to solve it because I don't have any ideas. Jump to mind, but let's think. Hmm. Wow. So it's a large number. Yeah. Interesting. I mean the sort of like if we start with something sort of simple and naive, like we could be doing the same thing but with a single global queue of every request. Now the issue with that is it doesn't play well with the desire to be parallel because it's this single piece of data that's accessed by every query. Does that make sense, what I'm saying so far?

Doctor Squab: Yeah.

Professor Squirrel: So that's an option and that would be correct in the sense of we could implement that to satisfy the spec. But I'm interested in trying to think about if there's something nicer and better, I guess, in terms of efficiency. Yeah. Wow. Yeah, I wonder. I mean, okay, I'll just think sort of broadly because I don't have specifics in mind yet, but something I'm thinking about is like maybe individual, like per client counts could somehow be like atomically added and subtracted from like a global count. So like every time the issue is, I guess by anyway. So that's like a vague sort of something worth looking into. But yeah, the issue that comes to mind with that is that when a given client, id say client five, gets some requests and then later there is no requests from client five for a long time. The sort of cleanup step won't run for that client. So that idea doesn't obviously work right away. There's that issue with it. Yeah. I mean, yeah, I'm going to be honest, nothing is really jumping to mind, but it seems like an interesting and challenging problem to try to solve.

Doctor Squab: Yeah.

Professor Squirrel: Do you want me to keep like sort of.

Doctor Squab: That's ok. You don't have to implement this. Another follow up, I just wanted to hear your thoughts on is what kind of error handling you will do on the client side. So this is more server side thinking happening. Right. So what kind of errors you will throw at client and what kind of handling you will do on client side if, let's say that you get a rate limiting.

Professor Squirrel: Cool, great question. Okay, so the first idea that pops into my head just from like pattern matching on things I've heard about would be like some sort of exponential backup so you don't overwhelm the system. I guess rewinding a bit, it's like some, how do I say this? Probably the client still wants to perform their operation, although I guess it depends. So the client side logic maybe has to express intent about what it wants, but different possibilities are to give up because it was something that was only useful if it was going to happen right away. Maybe you're trading stocks and you're like, oh, now's a good time to buy the stock. You wouldn't want to auto retry that because maybe the stock price had changed. That would be a sample of that. But if you do want to retry it, then great. Except you don't want to just spam retries because it's wasteful. So what would you do? I mean, like you could pick an initial like interval to like wait that long before retrying. And I'm trying to think how to make a good number for that. Maybe it relates to t somehow. Go ahead.

Doctor Squab: Yeah. Exponential backup will have a time. You know, there will be a parameter, right? Like how much to back off? How much to back off? So, okay. And the very last question is what kind of errors can you expect to come out of this class so that, you know, client, do you think that client will have different handling for different types of cases or what kind of things you will back off at with what kind of things you will give up at?

Professor Squirrel: So can you repeat, are you talking about the different, like something more than a boolean that the is allowed my return? Like if it's giving the client more information than just deny, allow, is that what you're suggesting or something else?

Doctor Squab: Yeah, I mean, Boolean is the is when things are great. But let's say that code is poorly written and it still cause exceptions. Let's say you go out of memory or whatever. So something unexpected can still come out of your code for whatever reason. I don't know. But for those cases, do you expect to get different kind of handling?

Professor Squirrel: Right. Okay. Okay. I think I can think of some examples. Like, I guess if the server running the rate limiter has crashed entirely. Like the client won't get a response. Like it'll be like, you won't get a true, you won't get a false, you just won't get anything. Like that's maybe an example of the kind of thing that could go wrong. The code as is, I don't think has any ways to crash besides running out of memory, which kind of is analogous to the server going down.

Doctor Squab: Yeah, this is good. Yeah. Yeah. I think we have pretty much taken everything out of this question.

Professor Squirrel: Okay, sure.

Doctor Squab: So we can stop here. Yeah. So do you want to discuss a quick feedback before I let you go, or you would rather prefer a written feedback?

Professor Squirrel: I think verbal feedback would be great, if you don't mind.

Doctor Squab: Okay, sounds good. No, yeah. So let me. Yeah, you did, of course. I think you probably feel it. You did extremely well on this question.

Professor Squirrel: Thank you.

Doctor Squab: Yeah, pretty much. I think so far, I don't know, probably the best performance I have seen in alumni.

Professor Squirrel: Thank you very much.

Doctor Squab: Yeah. So, and I have asked this question like 100 times. So I'm very happy that you were able to reach all the parts of the question. Typically most people struggle in the first itself. Then some who complete, they can't get to the test cases. Those who get to the test cases cannot go to the thread safety and then the exception handling and the multi threading and then client side handling and stuff like that. It's a good discussion, which kind of makes you get lots of signals whether you are, you know, just the algorithm person. Your code is also very clean. And I think a little bit of rust is helping you with Singleton and threat safety, which kind of came out as a class other languages have. Sometimes it changes language to language. Somebody wrote code in JavaScript yesterday and then like, oh gosh, this is not going to be thread safe. So, so, yeah, only one feedback. To be honest, I would say I'm really nitpicking here. You would definitely would have got a strong higher, at least higher. Google has like strong higher leading higher leading no higher and then no higher. These are the five grids and I think everybody will give you a higher. I would have given you a strong higher, which is the highest rating. They give. They give, yeah. And only thing I would have done is doing a little bit test case discussion upfront that would kind of shape the code a little bit better. When I gave you that, you know, code, you kind of thought about few things. Oh yeah, this, this, should I handle it? The big day? And then that's the only part. But as soon as I gave you a test case, you. You were able to fix it yourself. So, yeah, I think, great job. Really. To be honest, I don't have much feedback. This is the first time I don't have much feedback because.

Professor Squirrel: I think that's a really helpful and actionable piece of advice, starting with test cases. So thanks for calling that out.

Doctor Squab: Yeah. Because this question is, as you see, like, it's not that hard. Only thing is that this tests heavily on the programming rather than algorithms. Some people do struggle with algorithm itself, but it's not really that tricky in terms of getting it right. But people do write that clean code. So that's the one question I tried to lead you and you do so that you can write clean code. Your variable namings are triggered. You do comment. That's also another good one. Yeah, I think if you have to kind of go extra mile, you can actually write the test case. You know, like how you will actually write the test case. So that's another extra mile you can go if you want to. Yeah. Google typically doesn't compile the test cases, but if you are trying other places as well, they might expect you to run the code, so.

Professor Squirrel: Gotcha. Okay. Yeah, that makes sense. Cool. Yeah, I'm trying to think if I have any other questions, like, is there? So. Yeah. So I should give you a little bit of background about me, I guess. I actually was working at Google for eight months out of university and I got laid off. Yeah. So I did pass an interview loop once before, although I think it was a very different hiring market at the time.

Doctor Squab: Sorry about that.

Professor Squirrel: Oh, no worries. No, no, no. It's all good, so. Right. And I expect I'll probably actually be mostly considered for l three roles, given I only have eight months of full time experience. But it felt like the l four interview was like a really good practice. I guess this felt something new and very helpful. Do you have any resources to prepare for questions with this sort of, like, style?

Doctor Squab: I think you're pretty good at coding and I don't be honest, I didn't realize that you. I would feel sad that if you are kind of your maturity in terms of code souls, that you are ready for al four. But I don't know how good you are at system design. And system design is probably one thing. They might lead a little bit more for l four signals. In terms of code, it is hard to get signals between l three and l four s. Basically, some strong l three s do as well as l four s into code, even at l five, really, code is not that great way of getting a strong signal. But if you do, if you do, because you will have Gnl, right? Google leadership, and you will have system design. I would really focus on those two. So the maturity you are, I think you are definitely ready for the code just there. You might see the questions, especially in Gnl, if they ask you stuff like, how would you do something? So a maturity of a leader, that's where you know, l three is that given a work, they can complete it independently. L four is that they can think about the solution by themselves as well. L three is given the solution altogether. They were told like, hey, here, you will do it. And they are supposed to just do it. That's what LC rubric is. And l four is that you are given a problem that, hey, can you implement a rate limiter for this? That's it. And then you come up with the entire idea of like how to do it. You will write a small doc around it. And so the maturity of a four five will actually think at a project level, six will think at multiple project level. So you at least need to show that given a problem, without any hints toward, you can independently do the research, you will come up with the plan design and you can implement it. So that's the expectation. So when you answer that question, or these questions in DNL, make sure you keep in mind that you have to sow the maturity. Always do not confine yourself to answering in a way that yourself think a little more broadly that, how will this thing go? That's the only thing they will be looking for, these signals to say whether you are ready for four or not. Even a system design is hard to say whether this person is ready or not. And a lot of people just think that GL as a, as a binary that, let me just pass it. I mean, you will pass it if you just answer right way. You know, if you don't be jerk and you just answer. And I say, you will probably pass it. But the thing is, like, if you sow more maturity, you might get a strong labeling kind of idea and people might write that, hey, see, I talked to this guy. This guy is like really mature. That's the maturity we just want. They are looking for a really mature person between three and four. So, yeah, that's the only tip I can give you in system design. Yeah, system design, they are. I think you just have to pass, I think at four, also at three, they don't even do it at four. The users need to pass, so practice a little bit. But really, that's not the criteria. Coding is at five, design you have, coding becomes binary, and design becomes the criteria to hire. At four, coding is the main signal. And system design is a little bit more lightweight.

Professor Squirrel: Yeah. Okay. That's really cool. That's super helpful to know. Thanks.

Doctor Squab: Cool. Yeah. Thank you. Thank you for taking time.

Professor Squirrel: Thank you. This is a lot of fun. Thanks again.

Doctor Squab: Thank you. All right, take care. Bye.