If 100% accuracy is required:
Have a linked-list of all requests and 3 counts - for the last hour, the last minute and the last second.
You will have 2 pointers into the linked-list - for a minute ago and for a second ago.
An hour ago will be at the end of the list. Whenever the time of the last request is more than an hour before the current time, remove it from the list and decrement the hour count.
The minute and second pointers will point to the first request that occurred after a minute and a second ago respectively. Whenever the time of the request is more than a minute / second before the current time, shift up the pointer and decrement the minute / second count.
When a new request comes in, add it to all 3 counts and add it to the front of the linked-list.
Requests for the counts would simply involve returning the counts.
All of the above operations are amortised constant time.
If less than 100% accuracy is acceptable:
The space-complexity for the above could be a bit much, depending on how many requests per second you would typically get; you can reduce this by sacrificing slightly on accuracy as follows:
Have a linked-list as above, but only for the last second. Also have the 3 counts.
Then have a circular array of 60 elements indicating the counts of each of the last 60 seconds. Whenever a second passes, subtract the last (oldest) element of the array from the minute count and add the last second count to the array.
Have a similar circular array for the last 60 minutes.
Loss of accuracy: The minute count can be off by all the requests in a second and the hour count can be off by all the requests in a minute.
Obviously this won't really make sense if you only have one request per second or less. In this case you can keep the last minute in the linked-list and just have a circular array for the last 60 minutes.
There are also other variations on this - the accuracy to space used ratio can be adjusted as required.
A timer to remove old elements:
If you remove old elements only when new elements come in, it will be amortised constant time (some operations might take longer, but it will average out to constant time).
If you want true constant time, you can additionally have a timer running which removes old elements, and each invocation of this (and of course insertions and checking the counts) will only take constant time, since you're removing at most a number of elements inserted in the constant time since the last timer tick.
