> After being given the algorithm problem, ask for the specific runtime your solution will need to have. Almost certainly, the interviewer will tell you. In my experience, interviewers will rarely tell you the runtime of the optimal solution. Regardless, very interesting blog post.
Agreed.
What I'd actually ask as a candidate is what to optimize for. Are we looking at an N of 100 and a simple solution will do, or are we looking at an N of a million? Maybe memory is the constraint.
Atleast show the candidate that you're thinking pragmatically. The goal in the real world isn't to write the "fastest" algorithm, it's to write the most appropriate one.
I would also add heaps/priority queues to this list. They don't come up as often as HashTables/LinkedLists but come up often enough. If you wanna be thorough (esp if you are applying at companies known for harder interviews) I would add practicing backtracking problems where you are doing a full exhaustive search of the problem space as well (often O(k^n) or O(n!) complexity). Yes these are often mostly just DFS + Re…
There's a specific reason I didn't mention priority queues in the post. In most cases, anything you can do with a heap you can do with a binary tree instead! A binary tree has O(log(n)) insert and deletion which is the same as a traditional heap. The only advantage a traditional heap has is you can construct a heap in O(n) time whereas a binary tree takes O(nlog(n)) time.
Of course there are even more niche data structures like a Fibonacci heap which have O(1) insertion, but you will have to get extremely unlucky to get asked about a Fibonacci heap in an interview.
The solution described in the article is likely to be extremely wasteful in both time and memory, by allocating a queue entry for each call, and then O(n) scanning and dropping stale entries on each successive call. Tabulating call count by division(s) of time would be less obviously problematic.
Probably safe to say you aren't having to rate limit over a thousand endpoints from a single spot, so the linear scan sounds like a non issue. That said, I'd hesitate to get to fancy in client rate limiting. Sounds like an area that will hide bugs that are stupid hard to deal with.
I don't quite see it that way, although maybe we read the problem as something different. Suppose the rate limit is 500 per second; a client makes a burst of 500 requests in one second, sleeps two seconds, then another burst of 500. Isn't the author's planned approach going to end up doing a bunch of bogus work?
- putting 500 timestamps into a queue
- inspecting 500 queue entries and removing each
- putting 500 new timestamps into a queue
> After being given the algorithm problem, ask for the specific runtime your solution will need to have. Almost certainly, the interviewer will tell you. In my experience, interviewers will rarely tell you the runtime of the optimal solution. Regardless, very interesting blog post.
I’d turn that question back around at the candidate, unless it were for a junior candidate. I’ll give hints if the candidate is struggling, but I won’t just come out and tell them something like this. If they pushed me hard enough at the start, I would tell them and then fail them on the algorithms/reasoning component of the interview.
Yeah - why not just tell them?
You know, like IRL. What this is supposedly about.
Again, the question referred to the target performance, not the optimal performance.
Before people start complaining about leetcode and how it doesnt exemplify skills: its a proxy for a combination of: intelligence and how hard you are willing to study the computer science knowledge shown is just a bonus EDIT: One last thing to throw in, its pretty clear that theres a correlation between the top software companies and how hard their leetcode interviews are. You can claim all you want it doesnt work,…
Probably safe to say you aren't having to rate limit over a thousand endpoints from a single spot, so the linear scan sounds like a non issue. That said, I'd hesitate to get to fancy in client rate limiting. Sounds like an area that will hide bugs that are stupid hard to deal with.
I don't quite see it that way, although maybe we read the problem as something different. Suppose the rate limit is 500 per second; a client makes a burst of 500 requests in one second, sleeps two seconds, then another burst of 500. Isn't the author's planned approach going to end up doing a bunch of bogus work? - putting 500 timestamps into a queue - inspecting 500 queue entries and removing each - putting 500 new t…
Depends on the requirements. If it's enough that the client doesn't make >N requests within the same "calendar second", then counting in bins is enough, no need to store timestamps. But then you could have a client send N requests in the second half of second k and N requests in the first half of second k+1, so you'd have a 1 second period (that spans two "calendar seconds") with 2N requests allowed. Since such rate limits are often not extremely exact, just an order of magnitude, this quantization/rounding effect may be negligibe and the speed may be worth it. But maybe not always. The original problem statement did not say that it's fine. Probably it's a good sign if an interviewee asks if this would be okay too.
Many interviewers ask candidates to explain their thinking. I don't think this dubious process of elimination would pass that test.
The "algorithm" I wrote in this post is a formalized version of some problem solving techniques I picked up from the classic book "How to Solve It"[0]. In particular "working backwards". You start from the goal you want and see what you know that is applicable to getting you to goal.
Probably safe to say you aren't having to rate limit over a thousand endpoints from a single spot, so the linear scan sounds like a non issue. That said, I'd hesitate to get to fancy in client rate limiting. Sounds like an area that will hide bugs that are stupid hard to deal with.
I don't quite see it that way, although maybe we read the problem as something different. Suppose the rate limit is 500 per second; a client makes a burst of 500 requests in one second, sleeps two seconds, then another burst of 500. Isn't the author's planned approach going to end up doing a bunch of bogus work? - putting 500 timestamps into a queue - inspecting 500 queue entries and removing each - putting 500 new t…
I'd assume a linked list was used to be able to drop a lot in a single shot. In particular, seems safe to assume the queue is sorted by time. Such that as soon as you see a time that is outside the window, you can drop all of the rest in one shot.
The page wasn't loading for me, so I can't see the proposal. Just don't let a linear scan scare you, for small n.
I’d turn that question back around at the candidate, unless it were for a junior candidate. I’ll give hints if the candidate is struggling, but I won’t just come out and tell them something like this. If they pushed me hard enough at the start, I would tell them and then fail them on the algorithms/reasoning component of the interview.
Why??
Because in the real world you don't know the runtime of the optimal solution, except for certain very well studied and simple problems. At best you might know the runtime of the best published solution. But in many cases your problem isn't something that anyone has studied in that kind of detail and it's going to be on you to determine whether your solution is satisfactory or whether you should go back and improve.