How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Optiver.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Optiver during technical interviews.

Design a queue and analyze tradeoffs | Optiver Coding Question

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

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

Quick Overview

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