Katkat
Back

Implement a fixed-capacity generic circular buffer

Applied IntuitionSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to implement a space-efficient data structure using fixed-size arrays, modular arithmetic for index wrapping, and generic type constraints.

Problem Statement

Design a thread-unsafe fixed-capacity circular buffer (also known as a ring buffer) that supports generic types. The buffer must have a fixed capacity defined at the time of construction.

Your implementation should support the following operations:

  • push(item): Adds an item to the end of the buffer. If the buffer is full, it should overwrite the oldest element.
  • pop(): Removes and returns the oldest item from the buffer. If the buffer is empty, throw an appropriate exception or return null.
  • is_empty(): Returns true if the buffer has no elements.
  • is_full(): Returns true if the buffer has reached its capacity.

Constraints

  • The buffer must use a fixed-size array or list allocated at initialization.
  • Both push and pop operations must perform in O(1) time complexity.
  • You must handle the wrap-around logic for the head and tail pointers.

Example

# Buffer with capacity 3
buffer = CircularBuffer(3)
buffer.push(1)
buffer.push(2)
buffer.push(3)
buffer.push(4) # Overwrites 1

buffer.pop() # Returns 2
buffer.pop() # Returns 3
buffer.pop() # Returns 4

Edge Cases

  • Operations on an empty buffer.
  • Overwriting elements when the buffer is full.
  • Interleaved push and pop operations that keep the buffer partially filled.

Hints

Hint 1

Use two pointers, `head` and `tail`, to keep track of where to add and remove elements.

Hint 2

Use the modulo operator (`%`) on the pointers to wrap them around to the beginning of the array when they reach the end of the capacity.

Hint 3

Maintain a `size` variable or a way to distinguish between a full buffer and an empty buffer when `head == tail`.

Follow-up questions

  • How would you make this buffer thread-safe for concurrent access by multiple producers and consumers?
  • How would you modify the buffer if you needed to support a dynamic capacity that grows when full?
  • What is the memory complexity of this implementation compared to a standard linked-list-based queue?