Quick Overview

This question evaluates understanding of FIFO data structures, algorithmic complexity analysis, memory and cache behavior, and concurrent access concerns.

Design a queue and analyze tradeoffs

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a FIFO queue data structure that supports enqueue, dequeue, peek, and isEmpty. Compare implementations using a singly linked list, a dynamic array, and a circular buffer. Analyze time and space complexity, amortized costs of resizing, memory overhead, and cache locality. Discuss edge cases such as underflow and overflow, potential blocking vs. non-blocking behavior for concurrent access, and when each implementation is preferable.

Overview: This question evaluates understanding of FIFO data structures, algorithmic complexity analysis, memory and cache behavior, and concurrent access concerns.

Design a FIFO queue that supports enqueue, dequeue, peek, and isEmpty. For the coding portion, implement a fixed-capacity queue using circular-buffer semantics so that no dequeue operation shifts elements. You are given a list of operations to perform and must return the result of each operation in order. Use this implementation as the basis for an interview follow-up discussion comparing singly linked lists, dynamic arrays, and circular buffers in terms of worst-case and amortized time, memory overhead, cache locality, overflow/underflow handling, and concurrency tradeoffs. For this problem, assume single-threaded access only.

Constraints

  • 0 <= capacity <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • Queue values are integers in the range [-10^9, 10^9]
  • Each operation is one of 'enqueue', 'dequeue', 'peek', or 'isEmpty'
  • Assume single-threaded execution; concurrency discussion is a follow-up, not part of the implementation

Examples

Input: ([('enqueue', 1), ('enqueue', 2), ('peek',), ('dequeue',), ('enqueue', 3), ('dequeue',), ('dequeue',), ('isEmpty',)], 2)

Expected Output: [True, True, 1, 1, True, 2, 3, True]

Explanation: After removing 1, the enqueue of 3 wraps around into the freed slot. The remaining dequeues return 2 and then 3.

Input: ([('enqueue', 5), ('enqueue', 6), ('enqueue', 7), ('isEmpty',), ('peek',), ('dequeue',), ('dequeue',), ('dequeue',)], 2)

Expected Output: [True, True, False, False, 5, 5, 6, 'underflow']

Explanation: The third enqueue fails because the queue is full. After removing 5 and 6, one more dequeue underflows.

Hints

  1. Track the index of the front element and the current size. The next insertion position can be computed from these values.
  2. A circular buffer lets you reuse freed slots with modulo arithmetic instead of shifting elements after every dequeue.

Loading coding console...

Show the approach

Approach

This solution implements a fixed-capacity FIFO queue with circular-buffer (ring-buffer) semantics, so no operation ever shifts elements — every operation is O(1).

State. Three variables track the queue inside a single pre-allocated list buffer of length capacity:

  • front — index of the current head element.
  • size — number of elements currently stored.
  • results — the answer collected per operation.

Why front + size? The occupied slots are the window [front, front+1, ..., front+size-1] taken modulo capacity, so the slot just past the tail is (front + size) % capacity. That is exactly where the next value goes — no separate rear pointer is needed.

Operations:

  • enqueue(v): if size == capacity the queue is full, append False (overflow). Otherwise write v at (front + size) % capacity, increment size, append True.
  • dequeue(): if empty append 'underflow'; else read buffer[front], clear that slot, advance front = (front + 1) % capacity, decrement size, and return the value.
  • peek(): return buffer[front] without moving anything, or 'underflow' if empty.
  • isEmpty(): append size == 0.

Correctness. The modulo wrap lets front and the insert index move circularly through the array, reusing freed slots, so capacity is fully exploited without copying. The capacity == 0 case is handled specially: buffer is [], size always equals capacity (0), so enqueue always returns False and the dequeue branch guards the modulo with if capacity > 0 else 0, avoiding division by zero. Tracking size explicitly (rather than comparing front/rear) cleanly distinguishes the otherwise-ambiguous full and empty states.

Time complexity:
O(m), where m = len(operations) — each operation does O(1) work (index math, one array read/write).
Space complexity:
O(capacity) for the pre-allocated buffer, plus O(m) for the returned results list.