Python 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 successful requests in the past T milliseconds.

Example:
Input:
N=2, T=100

Requests (c is client id, t is timestamp):
c=1, t=1
c=1, t=50
c=1, t=100
c=1, t=150
c=1, t=199
c=1, t=200

Interview Feedback

Feedback about The Legendary Waffle (the interviewee)
Advance this person to the next round?
Yes

• Technical skills:
  4/4
• Problem-solving ability:
  4/4
• Communication ability:
  4/4

+ Algorithms & DS (Outstanding):
* Came up with optimal solution within minutes.
* Correctly figures out space and time complexity.
* Initially up with sub-optimal datastructure but quickly realizes than list could have been a queue for O(1) deletion. Solid improvement.
- Couldn't come up with solid solution for the followup.

+ Programming (Solid):
* Checks on edge cases such as bad input.
* Clean code, nice handling of edge cases.
- During implementation time complexity changes to O(N), doesn't notice while can be if for O(1) complexity.
* Nice debugging skills, walk through the code.
* Mentions concurrency for multiple client handling.
* Mentions exception for error handling.
- Struggled a bit on implementation of followup.

+ Values Feedback (Outstanding):
* When pointed about complexity, comes up with better solution of O(log(N)).
* When hinted toward production traffic, thinks about concurrency.

+ Communication (Outstanding):
* Excellent communication, overall kept it casual and easy.

Overall:
Strong Hire at L3. Learning Hire at L4.
TC absolutely crushed the interview. Great job across all rubrics. I have no reservation in recommending a hire for them at L3.

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

It felt like you were pushing my solution to be better throughout the interview through the follow-up questions, which I really appreciated. I also appreciated that the question was more practical, and less of a "trick" LeetCode question. The feedback at the end was very helpful as well! Thanks for your time today.

Interview Transcript

Doctor Squab: Yeah. Okay, I usually start with introduction and please feel free to introduce as much or as little you would like. Yeah, I left Google recently. I was a staff engineer there...

The Legendary Waffle: Sure. So I'm a software engineer with about three years of experience...

Doctor Squab: Yeah, since you're targeting Google, it would be nice to very quickly go over the Google rubric of coding interviews and what they're looking for...

... maintain a priority queue with a pointer, to the original queue...