Ok, the RealTimeCounter problem got me thinking. It's a great question. It seems very simple, but as the author notes even PhD's are stumped by it. Here my solution.
One very important purpose it serves is to see how well you can identify problems in algorithms. Probably I'm guessing it's not even important that you get it perfect, just that you can recognize and talk through the challenges.
One challenge relates to understanding the requirements. It needs to return the count for the preceding period of duration N, whether N is a second or a day. It could and usually does start in the middle of the preceding second, day, etc. It's a constantly moving window. That means if you just reset the counter each time you pass the absolute boundary of the next N (1:00, 1:01, etc.), you lose accuracy.
So that suggests that you might have to track each individual increment() somehow. But there's the next challenge, memory usage. If you just store all the timestamps, that's linear memory growth every time increment() is called.
So it seems to me like the solution is a tradeoff between memory usage and accuracy. If you don't call increment() very much or have a lot of memory, you can get perfect accuracy.
So that's the "theory". Now here's where it gets more interesting from an engineering perspective. Optimal implementations. Here's what I came up with in about 15 minutes.
First you minimize memory usage by storing offsets instead of the complete timestamp. Do this in 2 arrays, one for the preceding interval and one for the current one. This makes it easy to exploit our knowledge of when we've crossed the interval boundary, e.g. via now().getSecond(), to clear out old data.
(I am only considering one type of interval like seconds here.. you could extend this to minutes, hours, days by duplicating this method, or perhaps theres some way to consolidate more optimally.)
Anyway, increment() takes the offset from the fixed start of the current interval, i.e. the nanoseconds since the start of the current second, and appends it to the Current array. It also checks if we've passed into the next interval, in which case it reassigns the Current array to the Preceding array and starts a new Current array. The getter functions also do this.
To get the count, the getter simply
1) Finds the nearest offset in the Preceding array to the current offset (could just loop over it, start in the middle, etc.)
2) Subtracts that index from the array length to count the number of in-scope increments from that preceding interval (this works because the array is naturally sorted)
3) Adds that to the length of the Current array (because everything in the current array is in-scope)
SO, that should be a pretty fast way to do it with minimal memory requirements. If memory's going to be a problem,
A) you could spend a little more computation to do a kind of garbage collection. In step 2, resize the array to clear out the out-of-scope indexes. (Maybe you'd want a more optimized kind of data structure than a vanilla array for this.)
B) reduce accuracy by quantizing the offsets.
Ok am I hired yet? I'll go wait by the phone.
Just kidding, I'm sure this is wrong in many ways. But the point I'm trying to make is that it's a great problem for exploring tradeoffs, yet easy to understand what's being asked and requires no special technical knowledge.