Interview q: Data structure and algorithm for O(1) retrieval of avg. response time in client server architecture

Question

Intv Q: In a client-server architecture, there are multiple requests from multiple clients to the server. The server should maintain the response times of all the requests in the previous hour. What data structure and algo will be used for this? Also, the average response time needs to be maintained and has to be retrieved in O(1).

My take: algo: maintain a running mean

mean =          mean_prev *n + current_response_time

                -------------------------------
                              n+1


 DS: a set (using order statistic tree).

My question is whether there is a better answer. I felt that my answer is very trivial and the answer to the questions(in the interview) before this one and after this one where non trivial.

EDIT: Based on what amit suggested:

cleanup()
    while(queue.front().timestamp-curr_time > 1hr)
        (timestamp,val)=queue.pop();
         sum=sum-val
         n=n-1;

insert(timestamp,value)
    queue.push(timestamp,value);
    sum=sum+val
    n=n+1;
    cleanup();

query_average()
    cleanup();
    return sum/n;

And if we can ensure that cleanup() is triggered once every hour or half an hour, then query_average() will not take very long. But if someone were to implement timer trigger for a function call, how would they do it?

Answer 1

The problem with your solution is it only takes the total average since the beginning of time, and not for the last one hour, as you supposed to.

To do so, you need to maintain 2 variables and a queue of entries (timestamp,value).

The 2 variables will be n (the number of elements that are relevant to the last hours) and sum - the sum of the elements from the last hour.

When a new element arrives:

queue.add(timestamp,value)
sum = sum + value
n = n+1

When you have a query for average:

while (queue.front().timestamp > currentTimeAtamp() - 1 hour):
    (timestamp,value) = queue.pop()
    sum = sum - value
    n = n-1
return sum/n

Note that the above is still O(1) on average, because for every insertion to the queue - you do exactly one deletion. You might add the above loop to the insertion procedure as well.