Moving Average on Metrics

source: test project for Erlang developer in AlertLogic (2017) - not specific to Erlang though

Important: for this problem your code is actually executed and tested. Submit in one of the languages supported by sandbox (C/C++, Java, C#, Go, Python3, etc)

There is also a simplified version of this task, in form of exercise, on our main site: Moving Average in Time.

Problem Statement

Some system continuously produces various metrics. Every record has 3 fields:

metric-name timestamp value

where metric-name is a sequence of letters (and possibly digits, dashes, underscores - but without spaces), timestamp is the number of milliseconds (e.g. since system start) and value - integer value of the given metric. For example:

temperature 1000 25
voltage 1005 231
temperature 1010 26
pressure 1013 101300
...

means we measured T=25, V=231 and so on at the moments 1.000, 1.005 sec and so on.

at some moments we want to know average for the given metric over the last minute (e.g. 60 seconds) - then the line included with question mark instead of the value.

You are to write the code which collects metrics, fed in such format to standard input, and printing average values, when requested (each on a new line). Stop when line starting with --- instead of metric name is read.

As values are changing constantly we do not insist on great accuracy: your results should fit about 2% tolerance. On the other hand take care your algorithm is not too slow. It is no good to collect metrics slower than they are produced. Checker will produce over 500000 metric values and has limitation of 3 seconds runtime (however its virtual server is few times slower than typical modern laptop).

Example

input:

V 10000 200
A 10002 11
V 11000 220
V 30000 ?
A 70000 8
A 70010 ?
--- 0 0

answer:

210
8

Explanation: here both voltage metrics at moments 10000 and 11000 are included in average requested at moment 30000, so it is 210. But when current average is requested at moment 70010 we only use the value from the moment 70000 while the value from 10002 should be already forgotten (it was more than minute ago).