PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Akuna Capital
  • Coding & Algorithms
  • Software Engineer

Implement a ring buffer

Company: Akuna Capital

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Implement a fixed-capacity circular buffer (ring buffer) supporting push, pop, peek, isEmpty, isFull, and size in O( 1) time using an array. Define and implement the behavior when pushing to a full buffer (either overwrite the oldest element or reject the push—choose and document). Provide iteration over current elements in logical order. Discuss how you would extend it to a thread-safe version with optional blocking push/pop using condition variables, and analyze time/space complexity.

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.

Implement a fixed-capacity circular buffer (ring buffer) backed by a plain array, supporting push, pop, peek, isEmpty, isFull, and size — each in O(1) time. When pushing to a full buffer, use the **reject-on-full** policy: the push is refused and reports failure (the existing elements are preserved). Elements are dequeued in FIFO order (oldest first), and you must be able to iterate the current elements in logical order (oldest → newest). To make this runnable and gradable, implement a single function `solution(capacity, operations)` that simulates the buffer: - `capacity` — a positive integer, the fixed buffer size. - `operations` — a list of operations applied in order. Each operation is a list whose first element is the op name: - `['push', x]` → push `x`; append `True` if accepted, `False` if the buffer was full (reject policy). - `['pop']` → remove and return the oldest element; append `None` if the buffer is empty. - `['peek']` → return the oldest element without removing it; `None` if empty. - `['isEmpty']` → `True` if the buffer is empty. - `['isFull']` → `True` if the buffer is full. - `['size']` → the current number of elements. - `['toList']` → the current elements as a list in logical order (oldest → newest). Return the list of results, one entry per operation, in order. Use two indices (`head` for the oldest element and a `count`/`size`), computing the write position as `(head + count) % capacity`. This avoids the classic full-vs-empty ambiguity without sacrificing a slot. **Thread-safety extension (discussion):** wrap each operation in a mutex; for a *blocking* variant, use two condition variables — `not_full` (push waits on it while `count == capacity`, pop signals it) and `not_empty` (pop waits on it while `count == 0`, push signals it). Each op stays O(1) amortized; space is O(capacity).

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

  1. 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.
  2. Using head + count (instead of head + tail) sidesteps the classic ambiguity where a head==tail state could mean either 'empty' or 'full'.
  3. On pop, advance head = (head + 1) % capacity and decrement count; clearing the slot is optional but helps avoid leaking references.
  4. To iterate in logical order, read buf[(head + i) % capacity] for i in 0..count-1.
  5. 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).
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Compute Graph Spread and Portfolio Trades - Akuna Capital (medium)
  • Find minimum swaps to sort array with duplicates - Akuna Capital (hard)
  • Compute max profit across dated stock quotes - Akuna Capital (Medium)
  • Break a palindrome to smallest non-palindrome - Akuna Capital (Medium)
  • Count inversions in an array efficiently - Akuna Capital (Medium)