Implement a ring buffer
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates implementation skills for fixed-capacity circular buffers and competency in array-based data structures, including O(1) push/pop/peek/isEmpty/isFull/size operations and logical-order iteration.
Constraints
- 1 <= capacity
- Each operation is one of: push, pop, peek, isEmpty, isFull, size, toList.
- Pushing to a full buffer is rejected (push returns False); existing elements are preserved.
- pop/peek on an empty buffer return None.
- All core operations must be O(1); only array indexing is allowed (no dynamic resize, no linked list).
Examples
Input: (3, [['isEmpty'], ['push', 1], ['push', 2], ['push', 3], ['isFull'], ['push', 4], ['size'], ['toList']])
Expected Output: [True, True, True, True, True, False, 3, [1, 2, 3]]
Explanation: Buffer starts empty. Push 1,2,3 fills it to capacity 3 (isFull becomes True). Pushing 4 is rejected (returns False) under the reject-on-full policy, size stays 3, and toList shows the elements oldest->newest: [1, 2, 3].
Input: (2, [['push', 10], ['push', 20], ['pop'], ['push', 30], ['toList'], ['pop'], ['pop'], ['pop'], ['isEmpty']])
Expected Output: [True, True, 10, True, [20, 30], 20, 30, None, True]
Explanation: Tests wraparound: after popping 10 (head advances), pushing 30 wraps the write index back to slot 0. Logical order is [20, 30]. Draining returns 20 then 30, a pop on empty returns None, and the buffer ends empty.
Input: (1, [['peek'], ['push', 99], ['peek'], ['isFull'], ['pop'], ['isEmpty'], ['size']])
Expected Output: [None, True, 99, True, 99, True, 0]
Explanation: Capacity-1 edge case: peek on empty is None, after pushing 99 the buffer is simultaneously full, peek returns 99 without removing it, pop returns 99 and empties the buffer.
Input: (3, [['push', 5], ['push', 6], ['pop'], ['pop'], ['pop'], ['push', 7], ['push', 8], ['push', 9], ['toList'], ['size']])
Expected Output: [True, True, 5, 6, None, True, True, True, [7, 8, 9], 3]
Explanation: Drains to empty (third pop returns None) then refills past a wrap point. head has moved to index 2, so pushing 7,8,9 wraps around; toList still reports correct logical order [7, 8, 9] with size 3.
Input: (2, [['size'], ['isEmpty'], ['toList']])
Expected Output: [0, True, []]
Explanation: Empty-buffer baseline: size is 0, isEmpty is True, and toList returns an empty list.
Hints
- Track the index of the oldest element (head) and the current count. The write position is (head + count) % capacity, so you never need a separate tail variable.
- Using head + count (instead of head + tail) sidesteps the classic ambiguity where a head==tail state could mean either 'empty' or 'full'.
- On pop, advance head = (head + 1) % capacity and decrement count; clearing the slot is optional but helps avoid leaking references.
- To iterate in logical order, read buf[(head + i) % capacity] for i in 0..count-1.
- For a thread-safe blocking version: one mutex plus two condition variables — not_full (push waits while full, pop signals) and not_empty (pop waits while empty, push signals).