New UMPIRE Problem: Queues

Problem Highlights

• 🔗 Leetcode Link: Design Circular Queue
• 💡 Problem Difficulty: Medium
• ⏰ Time to complete: 25 mins
• 🛠️ Topics: Array, Queue, Design
• 🗒️ Similar Questions: Implement Queue using Stacks, Moving Average from Data Stream, Design Circular Deque

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What should Front() and Rear() return when the queue is empty?
  • Return -1 for both operations when the queue is empty.
• What happens when enQueue is called on a full queue, or deQueue on an empty queue?
  • The operation fails and returns false; the queue is left unchanged.
• What are the constraints on the capacity and the values?
  • 1 <= k <= 1000, 0 <= value <= 1000, and at most 3000 calls will be made to the operations, so a fixed-size array of k slots is always enough storage.

HAPPY CASE
Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // queue = [1], return True
myCircularQueue.enQueue(2); // queue = [1, 2], return True
myCircularQueue.enQueue(3); // queue = [1, 2, 3], return True
myCircularQueue.enQueue(4); // queue is full, return False
myCircularQueue.Rear();     // rear element is 3, return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // queue = [2, 3], return True
myCircularQueue.enQueue(4); // the freed slot is reused, queue = [2, 3, 4], return True
myCircularQueue.Rear();     // rear element is 4, return 4

EDGE CASE
Input
["MyCircularQueue", "Front", "Rear", "deQueue", "enQueue", "Front", "Rear", "isFull"]
[[1], [], [], [], [5], [], [], []]
Output
[null, -1, -1, false, true, 5, 5, true]

Explanation
With capacity k = 1, Front and Rear return -1 while the queue is empty, deQueue fails,
and after one successful enQueue the single element is both the front and the rear.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For design problems around Queues, we want to pick an underlying structure that supports the required operations efficiently:

• Use a fixed-size Array as a ring buffer
  • The capacity k is fixed up front, so a plain array of k slots holds every element; wrapping the indices with modulo arithmetic lets us reuse the slots freed by deQueue instead of shifting elements.
• Track the front with an index instead of moving elements
  • Dequeuing by shifting every remaining element costs O(N); advancing a front index with (front + 1) % k makes every operation O(1).
• Keep a size count to tell full and empty apart
  • With only front/rear indices, a full queue and an empty queue can look identical; an explicit size count (or permanently sacrificing one slot) disambiguates the two states.
• A Linked List also works
  • Nodes allocated on demand also give O(1) operations, but the fixed capacity makes the array simpler and avoids per-node overhead.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Store the elements in a fixed array of k slots. Keep a front index and a size count, and wrap every computed index with modulo k so the queue reuses freed slots circularly. The rear element lives at index (front + size - 1) % k, and the next free slot is (front + size) % k.

1. Create a fixed array of k slots, a front index at 0, and a size count at 0
2. enQueue: if the queue is full return false, else write the value at (front + size) % k, grow size, return true
3. deQueue: if the queue is empty return false, else advance front to (front + 1) % k, shrink size, return true
4. Front: return the element at front, or -1 when the queue is empty
5. Rear: return the element at (front + size - 1) % k, or -1 when the queue is empty
6. isEmpty: size is 0; isFull: size equals k

⚠️ Common Mistakes

• Testing both “empty” and “full” with front == rear — without a size count (or one permanently unused slot) those two states are indistinguishable in a ring buffer.
• Forgetting the modulo wrap when computing the write or rear index, which runs off the end of the array once the queue has wrapped around.
• Returning 0 instead of -1 from Front()/Rear() on an empty queue — 0 is a legal stored value, so it cannot double as the empty sentinel.

4: I-mplement

Implement the code to solve the algorithm.

class MyCircularQueue:

    def __init__(self, k: int):
        # Create a fixed array of k slots, a front index at 0, and a size count at 0
        self.queue = [0] * k
        self.capacity = k
        self.front = 0
        self.size = 0

    def enQueue(self, value: int) -> bool:
        # If the queue is full return false
        if self.isFull():
            return False
        # Write the value at (front + size) % k, grow size, return true
        self.queue[(self.front + self.size) % self.capacity] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        # If the queue is empty return false
        if self.isEmpty():
            return False
        # Advance front to (front + 1) % k, shrink size, return true
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        # Return the element at front, or -1 when the queue is empty
        if self.isEmpty():
            return -1
        return self.queue[self.front]

    def Rear(self) -> int:
        # Return the element at (front + size - 1) % k, or -1 when the queue is empty
        if self.isEmpty():
            return -1
        return self.queue[(self.front + self.size - 1) % self.capacity]

    def isEmpty(self) -> bool:
        # isEmpty: size is 0
        return self.size == 0

    def isFull(self) -> bool:
        # isFull: size equals k
        return self.size == self.capacity

class MyCircularQueue {
    private int[] queue;
    private int capacity;
    private int front;
    private int size;

    public MyCircularQueue(int k) {
        // Create a fixed array of k slots, a front index at 0, and a size count at 0
        queue = new int[k];
        capacity = k;
        front = 0;
        size = 0;
    }

    public boolean enQueue(int value) {
        // If the queue is full return false
        if (isFull()) {
            return false;
        }
        // Write the value at (front + size) % k, grow size, return true
        queue[(front + size) % capacity] = value;
        size++;
        return true;
    }

    public boolean deQueue() {
        // If the queue is empty return false
        if (isEmpty()) {
            return false;
        }
        // Advance front to (front + 1) % k, shrink size, return true
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    public int Front() {
        // Return the element at front, or -1 when the queue is empty
        return isEmpty() ? -1 : queue[front];
    }

    public int Rear() {
        // Return the element at (front + size - 1) % k, or -1 when the queue is empty
        return isEmpty() ? -1 : queue[(front + size - 1) % capacity];
    }

    public boolean isEmpty() {
        // isEmpty: size is 0
        return size == 0;
    }

    public boolean isFull() {
        // isFull: size equals k
        return size == capacity;
    }
}

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

Tracing the HAPPY CASE with k = 3: after enQueue(1), enQueue(2), enQueue(3) the array is [1, 2, 3] with front = 0 and size = 3, so enQueue(4) fails and Rear() reads index (0 + 3 - 1) % 3 = 2, returning 3. deQueue() advances front to 1, and the next enQueue(4) writes at index (1 + 2) % 3 = 0 — the slot freed by the dequeue — so Rear() now reads index (1 + 3 - 1) % 3 = 0 and returns 4.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume k represents the capacity of the circular queue.

• Time Complexity: O(1) for every operation — each of enQueue, deQueue, Front, Rear, isEmpty, and isFull does a constant amount of index arithmetic, with no shifting or traversal.
• Space Complexity: O(k) to hold the fixed array of k slots, allocated once at construction.