Ring Buffer

Track: Data structures. 6 stages. Languages: Go, Python, JavaScript, Rust.

Build a fixed-size queue over an array you create once. It keeps values in the order you add them, so Pop always returns the value you pushed the longest time ago. When the array runs out of room at the end, new values wrap back around to the start, into slots already freed by earlier pops. Implement New(capacity), Push(v) -> bool, Pop() -> (v, ok), Peek() -> (v, ok) (like Pop, but it doesn't remove the value), and Len() -> int using your language's names. Build the array yourself. Do not use a ready-made queue or deque for the storage. Values are whole numbers, including 0 and negative numbers. Your buffer receives one call at a time. For help with the ideas, read the notes.

Where it is used

• Linux io_uring lets a program and the kernel pass I/O requests and results through two ring buffers in shared memory.
• The Linux kernel's tracing writes events into ring buffers. When one is full, it either writes over the oldest events or drops the newest, depending on the mode you choose.
• The LMAX Disruptor, a Java library for passing messages between threads with very low delay, is built around one ring buffer created up front.

In this challenge a full buffer refuses the push. A buffer that silently writes over values nobody has read yet loses data without telling anyone.

Stages

rb1: hello: push then pop (very easy)

Push one value, then take it back out with Pop. Example: capacity 2. Push(5) -> true. Pop() -> (5, true).

The tester will verify: Pop returns the value you just pushed.

rb2: push, peek, and pop in order (easy)

Push a few values. Peek shows the oldest one without removing it. Then Pop returns the values one at a time, oldest first. Popping or peeking an empty buffer must report nothing found. Example: capacity 4. Push(1), Push(2). Peek() -> (1, true). Pop() -> (1, true). Pop() -> (2, true). Pop() -> (0, false).

The tester will verify: Peek returns the oldest value and does not remove it, Pop returns the values in the order you pushed them, and both report nothing found once the buffer is empty.

rb3: full means full (medium)

A buffer only holds as many values as its capacity. Once it is full, Push must return false and change nothing. After you pop values back out, Push must work again. Example: capacity 4. Push(1) through Push(4) succeed, Push(5) returns false and nothing changes. Pop four times to get 1, 2, 3, 4, then Pop() reports nothing found. Push(6) now succeeds.

The tester will verify: exactly four values fit, the fifth Push returns false and changes nothing, the pops return 1, 2, 3, 4 and then report empty, and the buffer keeps working afterwards.

rb4: size and peek after wrapping around (medium)

Push and pop enough values that new ones start landing in slots freed by earlier pops, at the start of the array again. Len and Peek must stay right through all of it, including the moments when the buffer is completely full and completely empty.

slots (capacity 4):  [   ][   ][ C ][ D ]      4 slots, head at C, 2 slots free at the start
push E:              [ E ][   ][ C ][ D ]      E landed in slot 0: the buffer wrapped back to the start

Example: capacity 4. Push 1, 2, 3, 4 (now full). Pop twice (1 and 2 come out, freeing their slots). Push 5, 6 (they land in those freed slots). Len() -> 4. Peek() -> (3, true) (the oldest value left).

The tester will verify: Len gives the right count once the buffer has wrapped, once it is completely full, and once it is empty again, and Peek always returns the oldest value that is still there.

rb5: thousands of pushes and pops (hard)

Keep every answer right over thousands of pushes and pops in a row, with the buffer filling up and emptying out again and again. Values include zero and negative numbers, and the capacity is 7, a number that is not a power of two. Example: fill the buffer completely, drain it, then fill it again, many times over. Every pop and peek along the way must return the right value.

The tester will verify: every answer matches across the whole run. One wrong answer fails the stage.

rb6: push and pop speed (L2, hard)

Keep Push and Pop fast even under heavy use. Keep every answer correct. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.

The tester will verify: your code takes at most 1.5 times as long as our solution in the same language, and every answer stays correct.

Rules

• Build the ring yourself over a fixed-size array you allocate once. No ready-made queues or deques (collections.deque, container/list, VecDeque, ArrayDeque, Elixir's :queue, and so on). The array is the exercise.
• Standard library only.

Read the Ring Buffer notes in the wiki