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.