A fixed-size ring buffer for the last N ticks

Question

You want to retain only the most recent N ticks from an endless stream, in fixed memory. Implement a circular (ring) buffer that overwrites the oldest tick once full and can report its contents oldest-to-newest.

capacity 3: push 10, 20, 30  -> recent = [10, 20, 30]
push 40                      -> recent = [20, 30, 40]   # 10 evicted

Implement push and a recent() readout in O(1) push time and O(N) space.

Accepted Answer

Store a fixed array and a head pointer marking the next write slot. Each push writes at head (overwriting whatever was there) and advances head modulo the capacity. Track size so that before the buffer is full you only report the filled portion; once full, the logical order starts at head (the oldest) and wraps around. Tracing capacity 3: pushing 10, 20, 30 fills the buffer and recent() is [10, 20, 30]; pushing 40 overwrites slot 0, and recent() reads from head to give [20, 30, 40]. Time O(1) per push, O(N) for a readout, space O(N). Edge cases: before the buffer fills, only the written prefi…

A fixed-size ring buffer for the last N ticks

Your answer

More Coding questions