Re:A Wretched Google Interview Experience
by stinkypete on Tuesday August 20, 2013 @02:17PM
(#6245515)
I don't know about an official answer but using a simple variation on a round-robin database (RRD) ought to do the trick. Basically:
You end up losing a small amount of accuracy, the worst being for keeping track of the second counts. You can avoid that by using an actual list of counter values for the seconds bucket and dumping those out when they get older than a second, or maybe by introducing another subdivision -- 1/10th of a second probably is good -- so that you actually have .9 seconds worth of data and can interpolate the last bit.
[ Parent
| on HN ]
Re:A Wretched Google Interview Experience
by informatimago on Tuesday August 20, 2013 @05:48PM
(#6246812)
The last hour now goes back from 22:45:03.435123897 (remember, nanosecond timer, but now it is from 22:46:07.223981453. Unless you can round the time when the last second, the last minute, etc start, you have to keep the full history of increment events up to the nanosecond for the last 24 hours. That's O(246060*1e9).
But if you do round the time to an acceptable degree of accuracy (say, to within 1ms of the second count and 1m of the day count) then it does work within a fixed amount of memory. It's probably the best solution.
It's a lovely exercise in algorithm tradeoffs. In this case it's mainly accuracy vs. memory, with lots of opportunity to explore implementation optimizations.