~/problems / Pools & pipelines / Ring buffers and producer/consumer pipelines

Single-producer, multi-consumer ring buffer

medium 3 levels ~50 min Citadel

Level 1 Fixed-capacity ring buffer

Build RingBuffer(capacity), a FIFO queue stored in a list of exactly capacity slots allocated once, with a read index, a write index and a size (or another way to tell "full" from "empty", e.g. a size counter). Indexes wrap around modulo capacity.

  • try_push(item) -> bool: append item at the back. If the buffer is full, leave it unchanged and return False (the overflow policy here is "reject the newest").
  • try_pop(): remove and return the front item. Raise IndexError if the buffer is empty.
  • __len__(), is_empty(), is_full(), and capacity as an attribute.

capacity >= 1. Items can be anything, including None. Every operation must be O(1): no list.pop(0), no insert(0, ...), no shifting.

rb = RingBuffer(2)
rb.try_push("a")   # True
rb.try_push("b")   # True
rb.try_push("c")   # False (full)
rb.try_pop()       # "a"
rb.try_push("c")   # True  (wraps around into slot 0)
[rb.try_pop(), rb.try_pop()]   # ["b", "c"]
rb.try_pop()       # IndexError

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Ring buffers and producer/consumer pipelines. Fixed-size circular buffers, head/tail indexes, back-pressure.

0:00
Ctrl ' run · Ctrl ↵ submit
esc