One particularly desirable property for systems we design is that they consume a predictable quantity of resources. In this day and age, it is still common for engineers to be woken from their sweet dreams by an alert informing them logs have suddenly consumed the majority of the disk space on one of their servers.
In the fight for predictability, ring buffers are an interesting data structure which allow us to use a fixed amount of memory, and which are frequently used for storing time series data. In short, a ring buffer is a datastructure which wraps around when it reaches its end, always maintaining a fixed size, and prefers to overwrite earlier data instead of extending itself.
Let's imagine we are relying on ring buffer to store `n`, number of requests over each second to one of our services for the last `k` seconds, and each second we write a number of requests. There are two operations we an perform:
write(n, t) will add a new entry for the number of requests at time `t`.
This operation should never fail. If the buffer is full, then
it should loop around the buffer.
read(t) should return the number of requests per second at time `t`,
and should return -1 if a value is not stored for for time `t`,
(for example, if that time is too far in the past and has already been
Taking a simple case, a program would take these inputs over stdin:
10 r 0 w 10 1 w 5 2 r 1 r 2 r 3
# no output, this is 'k', the size of buffer 0 -1 # no output # no output 1 20 2 5 3 -1
Then getting a bit trickier, consider this:
w 4 8 r 3 r 4
# no output 3 0 4 8
Although you never wrote a value for
t=3, because you wrote a value at
a later point in time, you know that there was no traffic until that point
(in this problem, where we are operating in a world without race conditions)!
Pushing your implementation a bit further, taking this input:
10 r 0 r 10 r 100 w 1 3 w 2 5 w 3 7 r 2 r 4 w 10 11 r 5 r 9 r 10 r 1 w 11 13 r 11 r 1 w 50 17 r 11 r 49 r 50
# no input 0 -1 10 -1 100 -1 # no input # no input # no input 2 5 4 -1 # no input 5 0 9 0 10 11 1 3 # no input 11 11 1 -1 # no input 11 -1 49 0 50 17
If your implementation worked correctly, then you're definitely ready to validate your solution!