Buffer Queue: Implement a Fixed-Capacity Circular Buffer Queue with Overflow Policy
Question Details
Problem
Implement a fixed-capacity circular buffer queue that supports enqueue, dequeue, peek, and is_full/is_empty operations. When full, the enqueue operation should overwrite the oldest element (ring buffer semantics). The buffer should be O(1) for all operations.
python
class BufferQueue:
def __init__(self, capacity: int): ...
def enqueue(self, item) -> None: ...
def dequeue(self):
**returns** item or raises if empty
def peek(self):
**returns** next item without removing
def is_full(self) -> bool: ...
def is_empty(self) -> bool: ...
def __len__(self) -> int: ...
Example:
bq = BufferQueue(3)
bq.enqueue(1); bq.enqueue(2); bq.enqueue(3)
bq.is_full() -> True
bq.enqueue(4) # overwrites oldest: [2,3,4]
bq.dequeue() -> 2
bq.dequeue() -> 3
bq.is_empty() -> False
Follow-ups
- How do you distinguish a full buffer from an empty buffer when using only head and tail pointers (the classic off-by-one problem)?
- What is the difference between overwrite-on-full semantics and block-on-full semantics, and where is each used?
- How would you make this thread-safe for a single producer and single consumer without a mutex (lock-free SPSC queue)?
- How is this data structure used in audio/video streaming pipelines (e.g., jitter buffers)?
Full Details
Problem
Implement a fixed-capacity circular buffer queue that supports enqueue, dequeue, peek, and is_full/is_empty operations. When full, the enqueue operation should overwrite the oldest element (ring buffer semantics). The buffer should be O(1) for all operations.
python
class BufferQueue:
def __init__(self, capacity: int): ...
def enqueue(self, item) -> None: ...
def dequeue(self):
**returns** item or raises if empty
def peek(self):
**returns** next item without removing
def is_full(self) -> bool: ...
def is_empty(self) -> bool: ...
def __len__(self) -> int: ...
Example:
bq = BufferQueue(3)
bq.enqueue(1); bq.enqueue(2); bq.enqueue(3)
bq.is_full() -> True
bq.enqueue(4) # overwrites oldest: [2,3,4]
bq.dequeue() -> 2
bq.dequeue() -> 3
bq.is_empty() -> False
Follow-ups
- How do you distinguish a full buffer from an empty buffer when using only head and tail pointers (the classic off-by-one problem)?
- What is the difference between overwrite-on-full semantics and block-on-full semantics, and where is each used?
- How would you make this thread-safe for a single producer and single consumer without a mutex (lock-free SPSC queue)?
- How is this data structure used in audio/video streaming pipelines (e.g., jitter buffers)?
About This Question
This is a reported interview question from a rubrik interview during the phone round.
It covers the following topics: Coding, Onsite, Phone, Queue .