Design a fixed-capacity circular queue
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
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.
Quick Answer: 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.
Simulate enqueue, dequeue, front, rear, isEmpty, and isFull operations on a circular queue.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (3, [['enqueue',1], ['enqueue',2], ['rear'], ['dequeue'], ['front'], ['isFull']])
Expected Output: [True, True, 2, True, 2, False]
Explanation: Basic queue operations.
Input: (1, [['isEmpty'], ['enqueue',5], ['enqueue',6], ['isFull'], ['rear']])
Expected Output: [True, True, False, True, 5]
Explanation: Full queue.
Input: (2, [['dequeue'], ['front']])
Expected Output: [False, None]
Explanation: Empty queue.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.