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.

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.