Design Circular Queue
Asked at NVIDIA
Problem
Design Circular Queue asks you to implement a fixed-capacity FIFO queue backed by a ring buffer, supporting enqueue, dequeue, front, rear, and empty/full checks. It is a systems-flavored design question — ring buffers show up in network drivers, logging, and producer-consumer pipelines.
Asked At
| Company | Difficulty | |
|---|---|---|
| NVIDIA | Medium | View all NVIDIA questions → |
How to Think About It
A plain array with pop(0) shifts every element: O(n) per dequeue. A ring buffer avoids shifting by letting indices wrap around.
Key insight: store a head index and a count. The tail slot is (head + count) % capacity. Tracking count avoids the classic ambiguity where head == tail could mean either empty or full.
enQueue: if full, return false; write at (head + count) % k and increment count. deQueue: if empty, return false; advance head = (head + 1) % k and decrement count.
Front is buf[head]; Rear is buf[(head + count - 1) % k]. Both return -1 when the queue is empty.
Walkthrough with capacity 3: enQueue 1, 2, 3 -> full, so enQueue 4 fails. Rear = 3. deQueue removes 1, head moves to index 1. enQueue 4 writes to index 0 (wraps). Rear = 4.
Optimal Approach
State: buf of size k, head = 0, count = 0.
enQueue(v): if count == k return false; buf[(head + count) % k] = v; count += 1; return true.deQueue(): if count == 0 return false; head = (head + 1) % k; count -= 1; return true.Front(): -1 if empty, else buf[head].Rear(): -1 if empty, else buf[(head + count - 1) % k].isEmpty(): count == 0. isFull(): count == k.
Time: O(1) per operation. Space: O(k).
What Trips People Up in Real Interviews
Using only head and tail pointers without a count or a spare slot. Then head == tail is ambiguous between empty and full.
Forgetting the modulo when computing the rear index, which reads past the end after wrap-around.
Returning a stale value from Front/Rear on an empty queue instead of -1.
Using a dynamic list with pop(0). That is not a ring buffer and costs O(n) per dequeue.
Solution Code
class MyCircularQueue:
def __init__(self, k):
self.buf = [0] * k
self.k = k
self.head = 0
self.count = 0
def enQueue(self, value):
if self.count == self.k:
return False
self.buf[(self.head + self.count) % self.k] = value
self.count += 1
return True
def deQueue(self):
if self.count == 0:
return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.count == 0 else self.buf[self.head]
def Rear(self):
if self.count == 0:
return -1
return self.buf[(self.head + self.count - 1) % self.k]
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == self.kFrequently Asked Questions
What is the Design Circular Queue problem?
Design Circular Queue asks you to implement a fixed-capacity FIFO queue backed by a ring buffer, supporting enqueue, dequeue, front, rear, and empty/full checks. It is a systems-flavored design question — ring buffers show up in network drivers, logging, and producer-consumer pipelines.
How do you solve Design Circular Queue?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design Circular Queue?
Design Circular Queue is asked at NVIDIA. It is a medium difficulty problem.
What are common mistakes on Design Circular Queue?
- Using only `head` and `tail` pointers without a count or a spare slot. Then `head == tail` is ambiguous between empty and full.
- Forgetting the modulo when computing the rear index, which reads past the end after wrap-around.
- Returning a stale value from `Front`/`Rear` on an empty queue instead of `-1`.
- Using a dynamic list with `pop(0)`. That is not a ring buffer and costs `O(n)` per dequeue.