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 circular queue data structure | Optiver Coding Question

Quick Overview

This question evaluates understanding of circular buffer data structures and the ability to implement fixed-capacity queue operations with O(1) time and O(k) space guarantees, testing skills in index management and state representation within the Coding & Algorithms domain.

Design a circular queue data structure

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Design and implement a fixed-capacity **circular queue** that supports constant-time operations. A circular queue stores elements in an array of size `k` and uses wrap-around indices so that freed space at the front can be reused. ### API to implement Create a class (or module) with the following methods: - `MyCircularQueue(k)`: initialize the queue with capacity `k`. - `enQueue(x) -> bool`: insert element `x` into the queue. Return `true` if the operation succeeds; return `false` if the queue is full. - `deQueue() -> bool`: delete the element from the front of the queue. Return `true` if the operation succeeds; return `false` if the queue is empty. - `Front() -> int`: get the front element. Return `-1` if the queue is empty. - `Rear() -> int`: get the last element. Return `-1` if the queue is empty. - `isEmpty() -> bool`: return whether the queue is empty. - `isFull() -> bool`: return whether the queue is full. ### Constraints / requirements - `1 <= k <= 10^5` - Each operation should run in **O(1)** time. - Use **O(k)** additional space. ### Notes Be careful to correctly handle wrap-around behavior and the distinction between **empty** and **full** states.

Quick Answer: This question evaluates understanding of circular buffer data structures and the ability to implement fixed-capacity queue operations with O(1) time and O(k) space guarantees, testing skills in index management and state representation within the Coding & Algorithms domain.

Implement a fixed-capacity circular queue (ring buffer) that supports standard queue operations efficiently. You are given the queue capacity `k` and a list of operations to perform in order. Each operation is one of: - ('enq', x): enqueue integer x. Return True if successful, otherwise False (queue full). - ('deq',): dequeue the front element. Return True if successful, otherwise False (queue empty). - ('front',): return the front element, or -1 if empty. - ('rear',): return the last (most recently enqueued) element, or -1 if empty. - ('isEmpty',): return True if the queue is empty, else False. - ('isFull',): return True if the queue is full, else False. Return a list containing the outputs of every operation, in the same order as the operations are given.

Constraints

1 <= k <= 100000
1 <= len(operations) <= 200000
For ('enq', x), x is an integer in the 32-bit signed range
operations contain only: 'enq', 'deq', 'front', 'rear', 'isEmpty', 'isFull'

Examples

Input: (3, [('enq', 1), ('enq', 2), ('enq', 3), ('enq', 4), ('rear',), ('isFull',), ('deq',), ('enq', 4), ('rear',), ('front',)])

Expected Output: [True, True, True, False, 3, True, True, True, 4, 2]

Explanation: Queue fills to capacity 3; enq(4) fails. After one deq, enq(4) succeeds and wraps around.

Input: (1, [('deq',), ('front',), ('enq', 5), ('isFull',), ('enq', 6), ('rear',), ('deq',), ('isEmpty',)])

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

Explanation: Capacity 1: cannot dequeue or read front when empty; cannot enqueue when full.

Input: (2, [('enq', 1), ('enq', 2), ('deq',), ('enq', 3), ('front',), ('rear',)])

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

Explanation: After removing 1, enqueue 3 goes into the freed slot via wrap-around.

Input: (4, [('isEmpty',), ('isFull',), ('front',), ('rear',)])

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

Explanation: Fresh queue is empty, not full, and has no front/rear values.

Quick Overview