Coding Round Question

I was asked this question in the coding round discussion at Amazon.

There is a search engine which is hit with billions of search requests. Implement an API getCounter which will return the count of search requests hit in last one hour. This API can be called any time and it will return the number of search requests done in last one hour.

Approach

I came up with the following approach:

Created a counter class with two APIs : incrCount() and getCount().
The class also contains:

A circular array of size 3600 (1 hour has 3600 seconds). Each entry corresponds to the following pair:
pair<long long timestamp, long long count>;
For the first API, every time a search request comes, note its timestamp and for each entry (corresponding to the timestamp % 3600) increment its count value by 1. We also need logic to check if the timestamp at its entry is same as that needed or is it an old timestamp(in which the count is reset to 0).

Whenever the getCount() is called:
note the current timestamp.
Run a loop from idx = current timestamp % 3600 to idx = (current timetamp - 3600) % 3600 and check if the time stamp stored is the needed one, then update the sum.
Return the sum.

we need to take care of the. fact that during some lean period there may be some entries in this circular array which are stale and we do not need the count for those stale entries.

The time complexity of incrCount will be O(1), but getCount() will be O(n) in complexity.

Approach 2:

Instead of a circular array we can take a queue and everytime incrCount() is called, we check the value of the last entry in the queue. if its timestamp is same as that is to be inserted, then just update its count.
Also keep a count variable in this case which is updated by 1.

For getCount(), we start from the front of the queue and keep on removing the entries whose timestamps are lesser than current timestamp - 3600. while we remove these entries, subtract their count from the count variable which you have kept in incrCount().

The complexity of incrCount is O(1) and that of getCount() is O(n).

Interviewer wanted an O(1) approach for both incrCount() and getCount() methods. Considering the scale of the search engine, he wanted me to code a solution which does not bother about the stale entries in the Counter class.

I could not suggest anything on this at that time, but later on it came to my mind that one option may be to create a purging service that runs asynchronously and that does the purging of stale entries from the head. Just that there will be synchronization issues.

Please give suggestions in case you know how to make incrCount() and getCount() as both O(1).