Coding questions · Amazon
Design a fixed-capacity circular queue
This question evaluates understanding of fixed-capacity circular queue data structures, array-based indexing, modular arithmetic, and the requirement for constant-time (O(1)) enqueue/dequeue operations.
Design a fixed-capacity circular queue that supports enqueue(x), dequeue(), front(), rear(), isEmpty(), and isFull() operations in O(1) time. Implement it using an array and modular arithmetic. Explain how you manage head and tail indices, how you distinguish between empty and full states, and provide the time and space complexity.
Fixed-Capacity Circular Queue Operations
Examples
Example 1
Input: (3, [['enqueue',1], ['enqueue',2], ['rear'], ['dequeue'], ['front'], ['isFull']])
Output: [True, True, 2, True, 2, False]
Explanation: Basic queue operations.
Example 2
Input: (1, [['isEmpty'], ['enqueue',5], ['enqueue',6], ['isFull'], ['rear']])
Output: [True, True, False, True, 5]
Explanation: Full queue.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.