Am I crazy or is the first answer terrible? I sat down and wrote out and answer for the problem and I initialized one integer and one timestamp. It should be O(1) time and O(1) memory easily, right? I'm seeing comments saying they'd use an array or a hash table -- why are you using any data structure? You don't need to remember how many times it was called 61 seconds ago; just keep a timestamp and the last time you reset the timestamp. If you need it to be clock-minutes instead of rolling (it doesn't; whose clock, anyway?), then just round the timestamp. The obvious follow-up question is "ok, what if it needs to be limited to 10,000 calls per minute?" You're going to keep 10,000+ elements in some collection for no reason? I wouldn't immediately reject a candidate for coming up with this answer but I would seriously question their thought process on this one.
In fact it's kind of ironic that his first example exposes how bad this advice is: by trying to meta-game, starting from a few example data structures, he shows he completely misses the solution that is both simpler and much more performant.
In fact it's kind of ironic that his first example exposes how bad this advice is: by trying to meta-game, starting from a few example data structures, he shows he completely misses the solution that is both simpler and much more performant.