Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Amazon SWE interview with a data structures question that went deeper than I expected. The circular queue problem sounds straightforward until you're actually explaining index management out loud under pressure.

Questions Asked (1)

Design a fixed-capacity circular queue using an array. It needs to support enqueue, dequeue, front, rear, isEmpty, and isFull, all in O(1). Walk through how you handle the head and tail indices, how you tell empty from full, and what the time and space complexity looks like.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the modular arithmetic part well enough but fumbled explaining how to distinguish empty vs full state.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and constraints, then describe the array-based implementation with head and tail indices, emphasizing the modulo arithmetic for wrap-around. Explain the full/empty distinction using either a size counter or a reserved slot, and conclude with O(1) time and O(n) space complexity.

Pro tip: Mention the trade-off between using a size counter (simpler, uses extra space) and a reserved slot (no extra space, but capacity effectively n-1). This shows you consider practical constraints and can adapt to interviewer preferences.

1. Clarify Requirements and Constraints

Ask if the queue is fixed-capacity, if it's single-threaded, and if the capacity is known upfront. Confirm that all operations must be O(1).

2. Design the Data Structure

Use an array of size capacity, and maintain head (front index) and tail (next insertion index) indices. Optionally, maintain a size variable or use a reserved slot to distinguish full from empty.

3. Explain Enqueue and Dequeue Operations

For enqueue: check if full, place element at tail, update tail = (tail + 1) % capacity. For dequeue: check if empty, retrieve element at head, update head = (head + 1) % capacity.

4. Handle Empty vs Full Conditions

If using a size counter: empty when size == 0, full when size == capacity. If using a reserved slot: empty when head == tail, full when (tail + 1) % capacity == head.

5. Analyze Complexity and Edge Cases

All operations are O(1) time. Space is O(capacity). Discuss edge cases: enqueue to full queue, dequeue from empty queue, and wrap-around behavior.

Key Points to Mention

Use modulo arithmetic to wrap indices: (index + 1) % capacity.
Two common approaches to distinguish full/empty: maintain a size counter or reserve one empty slot.
All operations (enqueue, dequeue, front, rear, isEmpty, isFull) run in O(1) time.
Space complexity is O(capacity) for the array, plus O(1) for indices and optional size variable.
Edge cases: enqueue when full, dequeue when empty, and wrap-around when head or tail reaches the end.
Thread-safety considerations if the queue is used in a concurrent environment (e.g., use locks or atomic operations).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.