You’re given a stream of timestamp and weight pairs, with timestamp monotonically increasing. Implement a class which supports calculating average weight across all events in the past K mins.
For instance, given a stream: (1,7), (3,4), (5,2) where the first value of the pair corresponds to the timestamp and the second value corresponds to the weight of the event, give the average weight in the past K = 3 minutes. We do not know K before hand.
In this case, the average weight is 3, since the first event is not counted.
I do know a solution is possible O(log n) by binary searching through a list of timestamps to find the index that should be marked as the cutoff for events in the past K minutes and using prefix sums to get the average value in that time.