~/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.

Pools & pipelines

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 % capacity for 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.

esc