PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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

  • Medium
  • Optiver
  • Coding & Algorithms
  • Software Engineer

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.

Quick Answer: 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.

Input: ([('isEmpty',), ('enqueue', 10), ('peek',), ('dequeue',)], 0)

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

Explanation: A queue with capacity 0 is always empty, cannot accept new items, and both peek and dequeue underflow.

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

Expected Output: [True, True, -1, -1, False]

Explanation: Negative values and duplicates should be handled normally in FIFO order.

Input: ([], 4)

Expected Output: []

Explanation: With no operations, the result list is empty.

Input: ([('enqueue', 9), ('enqueue', 10), ('dequeue',), ('enqueue', 10), ('peek',), ('isEmpty',)], 1)

Expected Output: [True, False, 9, True, 10, False]

Explanation: Capacity 1 checks single-slot behavior: the queue alternates between full and empty correctly.

Solution

def solution(operations, capacity):
    buffer = [None] * capacity if capacity > 0 else []
    front = 0
    size = 0
    results = []

    for op in operations:
        cmd = op[0]

        if cmd == 'enqueue':
            if size == capacity:
                results.append(False)
            else:
                insert_idx = (front + size) % capacity
                buffer[insert_idx] = op[1]
                size += 1
                results.append(True)

        elif cmd == 'dequeue':
            if size == 0:
                results.append('underflow')
            else:
                value = buffer[front]
                buffer[front] = None
                front = (front + 1) % capacity if capacity > 0 else 0
                size -= 1
                results.append(value)

        elif cmd == 'peek':
            if size == 0:
                results.append('underflow')
            else:
                results.append(buffer[front])

        elif cmd == 'isEmpty':
            results.append(size == 0)

        else:
            raise ValueError('Invalid operation: ' + str(cmd))

    return results
Explanation
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..

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.
Last updated: Apr 27, 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

  • Find missing numbers in sequences - Optiver (hard)
  • Design a circular queue data structure - Optiver (medium)
  • Optimize flight and cargo bookings for profit - Optiver (hard)
  • Compare two programs for equivalence - Optiver (Medium)
  • Solve a Skyscraper puzzle efficiently - Optiver (Medium)