~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Ring buffers and producer/consumer pipelines
Fixed-size circular buffers, head/tail indexes, back-pressure.
Notes
Recognise it when: you need a fixed-capacity queue with no allocation, streaming between a producer and consumers, or "latest N items" buffers.
class Ring:
def __init__(self, capacity):
self.buf = [None] * capacity
self.head = 0 # next read position
self.size = 0
def push(self, x):
if self.size == len(self.buf):
raise OverflowError # or overwrite the oldest / block
self.buf[(self.head + self.size) % len(self.buf)] = x
self.size += 1
def pop(self):
x = self.buf[self.head]
self.head = (self.head + 1) % len(self.buf)
self.size -= 1
return x
- Single producer, many consumers: each consumer keeps its own read cursor into a shared sequence. The producer mustn't overwrite a slot until the slowest consumer has passed it (back-pressure), or the design explicitly drops old data.
- Monotonic 64-bit sequence numbers, with
seq % capacityfor the slot, make "full" and "empty" unambiguous.
Gotchas: telling full from empty when head == tail (keep a size, or use sequence numbers), and wrap-around off-by-ones.
5 problems
Concurrency
Pools & pipelines Thread pools, crawlers, producer/consumer buffers.
Ring buffers and producer/consumer pipelines
- Basics: blocking ring buffer basics easy
- Greenhouse thermometer log easy
- Single-producer, multi-consumer ring buffer 3 levels Citadel medium
- Queue three ways: ring buffer, growable array, linked list 3 levels Optiver medium
- Overwriting byte ring buffer with UTF-8 text 2 levels medium