Queue three ways: ring buffer, growable array, linked list

medium 3 levels ~40 min Optiver

Level 1 Fixed-size circular queue

Implement CircularQueue(capacity), a FIFO queue that holds at most capacity items (capacity >= 1). Store the items in a Python list of length capacity allocated once in __init__, and track the front index and the size yourself. Don't use collections.deque, list.pop(0), insert(0, ...) or slicing to shift items.

Methods:

enqueue(value) -> bool: add at the back; return False (and change nothing) if the queue is full.
dequeue(): remove and return the front item; return None if the queue is empty.
front() / rear(): the first / last item without removing it, or None if empty.
is_empty() -> bool, is_full() -> bool, and len(q).

q = CircularQueue(2)
q.enqueue(1)    # True
q.enqueue(2)    # True
q.enqueue(3)    # False (full)
q.dequeue()     # 1
q.enqueue(3)    # True -- wraps around to slot 0
q.rear()        # 3
len(q)          # 2

The classic bug is telling "full" from "empty" when the front and back indices coincide. Keeping an explicit size avoids it. Values can be falsy, such as 0 or "", so never test a slot for truthiness.

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.