Design Circular Queue

📋

Problem

Imagine a ticketing system at a busy amusement park where visitors form a line that loops back to the start when full, ensuring no space is wasted.

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It supports the following operations: MyCircularQueue(k): Constructor, set the size of the queue to be k. Front: Get the front item from the queue. Rear: Get the last item from the queue. enQueue(value): Insert an element into the circular queue. Return true if the operation is successful. deQueue(): Delete an element from the circular queue. Return true if the operation is successful. isEmpty(): Checks whether the circular queue is empty or not. isFull(): Checks whether the circular queue is full or not.

1 ≤ k ≤ 10^50 ≤ value ≤ 1000At most 10^5 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Edge cases: Enqueue on full queue → should return falseDequeue on empty queue → should return falseFront and Rear on empty queue → should return -1

</>

IDE

class MyCircularQueue: def __init__(self, k: int): pass def enQueue(self, value: int) -> bool: pass def deQueue(self) -> bool: pass def Front(self) -> int: pass def Rear(self) -> int: pass def isEmpty(self) -> bool: pass def isFull(self) -> bool: passclass MyCircularQueue { public MyCircularQueue(int k) { // constructor } public boolean enQueue(int value) { // enqueue } public boolean deQueue() { // dequeue } public int Front() { // front } public int Rear() { // rear } public boolean isEmpty() { // isEmpty } public boolean isFull() { // isFull } }class MyCircularQueue { public: MyCircularQueue(int k) { // constructor } bool enQueue(int value) { // enqueue } bool deQueue() { // dequeue } int Front() { // front } int Rear() { // rear } bool isEmpty() { // isEmpty } bool isFull() { // isFull } };class MyCircularQueue { constructor(k) { // constructor } enQueue(value) { // enqueue } deQueue() { // dequeue } Front() { // front } Rear() { // rear } isEmpty() { // isEmpty } isFull() { // isFull } }

class MyCircularQueue:
    def __init__(self, k: int):
        # Write your solution here
        pass
    def enQueue(self, value: int) -> bool:
        pass
    def deQueue(self) -> bool:
        pass
    def Front(self) -> int:
        pass
    def Rear(self) -> int:
        pass
    def isEmpty(self) -> bool:
        pass
    def isFull(self) -> bool:
        pass

class MyCircularQueue {
    public MyCircularQueue(int k) {
        // Write your solution here
    }
    public boolean enQueue(int value) {
        return false;
    }
    public boolean deQueue() {
        return false;
    }
    public int Front() {
        return -1;
    }
    public int Rear() {
        return -1;
    }
    public boolean isEmpty() {
        return true;
    }
    public boolean isFull() {
        return false;
    }
}

class MyCircularQueue {
public:
    MyCircularQueue(int k) {
        // Write your solution here
    }
    bool enQueue(int value) {
        return false;
    }
    bool deQueue() {
        return false;
    }
    int Front() {
        return -1;
    }
    int Rear() {
        return -1;
    }
    bool isEmpty() {
        return true;
    }
    bool isFull() {
        return false;
    }
};

class MyCircularQueue {
    constructor(k) {
        // Write your solution here
    }
    enQueue(value) {
        return false;
    }
    deQueue() {
        return false;
    }
    Front() {
        return -1;
    }
    Rear() {
        return -1;
    }
    isEmpty() {
        return true;
    }
    isFull() {
        return false;
    }
}

Common Bugs to Avoid

Wrong: enQueue returns true when queue is fullNot checking size before enqueue; using head == tail to detect full incorrectly.✅ Maintain a size variable and check if size == capacity before enQueue; return false if full.

Wrong: deQueue returns true but queue state not updatedNot updating head pointer or size after dequeue.✅ Increment head modulo capacity and decrement size on successful deQueue.

Wrong: Front or Rear returns incorrect element after wrap-aroundIncorrect modulo arithmetic for head or tail pointers.✅ Use (index + 1) % capacity to advance pointers and access elements correctly.

Wrong: Front or Rear returns -1 even when queue is not emptyIncorrect empty check or size variable usage.✅ Return -1 only if size == 0; otherwise return element at head or tail.

Wrong: Implementation causes TLE on large inputsUsing list shift operations causing O(n) dequeue complexity.✅ Use fixed-size array with head and tail pointers and size variable for O(1) operations.

✓

Test Cases

Focus on handling empty and full states explicitly and test single element scenarios.

Test wrap-around behavior and multiple dequeues/enqueues to catch pointer update bugs.

Optimize your implementation to avoid shifting elements and achieve O(1) time per operation.

t1_01basic

Input{"operations":["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","Rear","isFull","deQueue","enQueue","Rear"],"arguments":[[3],[1],[2],[3],[4],[],[],[],[4],[]]}

Expected[null,true,true,true,false,3,true,true,true,4]

⏱ Performance - must finish in 2000ms

We create a circular queue of size 3. We enqueue 1, 2, 3 successfully. The fourth enqueue fails because the queue is full. Rear returns 3. isFull returns true. We dequeue one element (1). Then enqueue 4 successfully. Rear now returns 4.

💡 Model the queue as a fixed-size array with head and tail pointers.

💡 Use modulo arithmetic to wrap around the array indices.

💡 Maintain a size variable to distinguish full and empty states.

Why it failed: Basic case failed - likely incorrect handling of full condition or wrong modulo arithmetic. Fix by ensuring enQueue returns false when size == capacity and use (tail + 1) % capacity for tail advancement.

✓ Core circular queue operations implemented correctly.

t1_02basic

Input{"operations":["MyCircularQueue","enQueue","deQueue","enQueue","Rear","Front","isEmpty","isFull"],"arguments":[[2],[10],[],[20],[],[],[],[]]}

Expected[null,true,true,true,20,20,false,false]

⏱ Performance - must finish in 2000ms

Create queue size 2. Enqueue 10, dequeue it, enqueue 20. Rear and Front both return 20. Queue is not empty and not full.

💡 Check that deQueue correctly updates head and size.

💡 Ensure Front and Rear return -1 when queue is empty.

💡 Verify isEmpty and isFull reflect current size accurately.

Why it failed: Basic case failed - likely incorrect update of head or size on deQueue. Fix by incrementing head modulo capacity and decrementing size on deQueue.

✓ Basic enqueue, dequeue, and query operations work as expected.

t2_01edge

Input{"operations":["MyCircularQueue","deQueue","Front","Rear","isEmpty","isFull"],"arguments":[[3],[],[],[],[],[]]}

Expected[null,false,-1,-1,true,false]

⏱ Performance - must finish in 2000ms

Dequeue on empty queue returns false. Front and Rear return -1. Queue is empty and not full.

💡 Check behavior when queue is empty before dequeue or access.

💡 Front and Rear should return -1 if queue is empty.

💡 isEmpty should return true and isFull false when empty.

Why it failed: Empty queue operations failed - likely missing empty checks before dequeue or Front/Rear. Fix by returning false on deQueue if size == 0 and -1 for Front/Rear if empty.

✓ Empty queue edge cases handled correctly.

t2_02edge

Input{"operations":["MyCircularQueue","enQueue","deQueue","isEmpty","isFull","Front","Rear"],"arguments":[[1],[100],[],[],[],[],[]]}

Expected[null,true,true,true,false,-1,-1]

⏱ Performance - must finish in 2000ms

Single element enqueue and dequeue results in empty queue. Front and Rear return -1 after dequeue.

💡 Test single element enqueue and dequeue transitions.

💡 Ensure size updates correctly to zero after dequeue.

💡 Front and Rear must return -1 when queue is empty.

Why it failed: Single element enqueue/dequeue failed - likely size not updated correctly after dequeue. Fix by decrementing size and updating head/tail properly.

✓ Single element enqueue and dequeue transitions handled correctly.

t2_03edge

Input{"operations":["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","isFull"],"arguments":[[3],[1],[2],[3],[4],[]]}

Expected[null,true,true,true,false,false]

⏱ Performance - must finish in 2000ms

Enqueue on full queue returns false. isFull returns false because queue is not full after last enqueue fails.

💡 Check that enQueue returns false when queue is full.

💡 Verify isFull returns true only when size == capacity.

💡 Ensure no elements are added when queue is full.

Why it failed: Enqueue on full queue failed - likely missing size check before enqueue. Fix by returning false if size == capacity before adding element.

✓ Full queue enqueue rejection handled correctly.

t3_01corner

Input{"operations":["MyCircularQueue","enQueue","enQueue","deQueue","enQueue","Rear","Front"],"arguments":[[3],[1],[2],[],[3],[],[]]}

Expected[null,true,true,true,true,3,2]

⏱ Performance - must finish in 2000ms

Test wrap-around: after dequeue, enqueue at tail wraps to start. Rear returns 3, Front returns 2.

💡 Check modulo arithmetic for head and tail pointers.

💡 Ensure tail wraps to 0 after reaching capacity-1.

💡 Verify Front and Rear reflect correct elements after wrap.

Why it failed: Wrap-around failed - likely tail pointer not modulo capacity. Fix by using (tail + 1) % capacity when advancing tail.

✓ Wrap-around behavior correctly implemented.

t3_02corner

Input{"operations":["MyCircularQueue","enQueue","enQueue","enQueue","deQueue","deQueue","enQueue","Rear","Front"],"arguments":[[3],[1],[2],[3],[],[],[4],[],[]]}

Expected[null,true,true,true,true,true,true,4,3]

⏱ Performance - must finish in 2000ms

Test multiple dequeues and enqueue after wrap-around. Rear returns 4, Front returns 3.

💡 Verify size updates correctly after multiple dequeues.

💡 Check head pointer advances modulo capacity.

💡 Ensure enqueue after dequeues places element correctly.

Why it failed: Multiple dequeues and enqueue failed - likely incorrect size or head update. Fix by decrementing size on deQueue and advancing head modulo capacity.

✓ Multiple dequeues and enqueue after wrap-around handled correctly.

t3_03corner

Input{"operations":["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","deQueue","enQueue","isFull"],"arguments":[[3],[1],[2],[3],[4],[],[5],[]]}

Expected[null,true,true,true,false,true,true,true]

⏱ Performance - must finish in 2000ms

Test greedy trap: enQueue returns false when full, but after dequeue enqueue succeeds. isFull returns true at end.

💡 Avoid greedy assumption that enqueue always succeeds if tail != head.

💡 Use size variable to distinguish full vs empty states.

💡 Check isFull returns true only when size == capacity.

Why it failed: Greedy trap failed - likely using head == tail to detect full instead of size. Fix by maintaining size variable and checking size == capacity for full.

✓ Greedy trap avoided by correct full detection.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Test large number of operations (up to 10^5) to ensure O(1) per operation implementation completes within time limit.

💡 Use fixed-size array with head and tail pointers for O(1) operations.

💡 Avoid shifting elements on dequeue to prevent O(n) complexity.

💡 Maintain size variable to distinguish full and empty states efficiently.

Why it failed: TLE due to O(n) dequeue or inefficient operations. Fix by implementing circular queue with head/tail pointers and size variable for O(1) operations.

✓ Efficient O(1) operations confirmed for large input.

Practice

1. You are given a list of asteroids represented by integers where the absolute value represents size and the sign represents direction (positive moving right, negative moving left). When two asteroids moving in opposite directions collide, the smaller one explodes. Which algorithmic approach guarantees an optimal solution to determine the state of asteroids after all collisions?

easy

A. Sorting asteroids by size and simulating collisions from largest to smallest

B. Greedy approach that removes pairs of colliding asteroids in a single pass without revisiting previous elements

C. Dynamic programming that stores subproblems of asteroid states to avoid recomputation

D. Stack simulation that processes asteroids sequentially, resolving collisions by comparing the current asteroid with the top of the stack

Solution

1. Step 1: Understand the collision condition

   Collisions only happen when a right-moving asteroid (positive) meets a left-moving asteroid (negative) coming after it.

2. Step 2: Recognize stack simulation suitability

   A stack naturally models the sequence of asteroids and allows checking the last asteroid's direction and size to resolve collisions efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach handles direction and size checks correctly [OK]

Hint: Stack simulates collisions by tracking last asteroid [OK]

Common Mistakes:

• Assuming greedy single pass without stack handles all cases
• Using DP unnecessarily
• Sorting breaks order-dependent collisions

2. What is the time complexity of the optimal iterative stack-based algorithm to evaluate a Reverse Polish Notation expression with n tokens?

medium

A. O(n) because each token is processed exactly once with constant-time stack operations

B. O(n) for processing tokens plus O(n) for recursion stack space

C. O(n log n) due to sorting or priority queue operations involved

D. O(n^2) because each operator requires scanning the stack to find operands

Solution

1. Step 1: Identify operations per token

   Each token is processed once; operands are pushed, operators pop two operands and push one result.

2. Step 2: Analyze stack operations

   Stack push/pop are O(1), so total time is proportional to number of tokens n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   No nested loops or recursion in iterative approach [OK]

Hint: Stack operations are O(1), so linear time overall [OK]

Common Mistakes:

• Assuming O(n^2) due to repeated stack scans
• Confusing recursion stack space with time
• Thinking sorting is involved

3. What is the time complexity of the optimal maximalRectangle solution that uses row-wise histogram transformation and largestRectangleArea with a monotonic stack for a matrix of size rows x cols?

medium

A. O(rows^2 * cols^2)

B. O(rows * cols^2)

C. O(rows^2 * cols)

D. O(rows * cols)

Solution

1. Step 1: Analyze outer loop over rows and inner loop over columns

   For each row, heights array is updated in O(cols) time.

2. Step 2: Analyze largestRectangleArea call per row

   largestRectangleArea uses a monotonic stack with O(cols) amortized time per call.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each row processed in O(cols), total O(rows * cols) [OK]

Hint: Each row processed once, stack operations amortize to O(cols) [OK]

Common Mistakes:

• Confusing nested loops leading to O(rows * cols^2)
• Assuming stack operations are O(cols^2)
• Forgetting amortized analysis

4. Suppose the asteroid collision problem is modified so that asteroids can split into smaller asteroids upon collision instead of simply exploding. Which of the following algorithmic changes correctly adapts the stack simulation to handle this variant efficiently?

hard

A. Modify the while loop to push the smaller split asteroid back onto the stack and continue collision checks with the remaining part

B. Replace the stack with a queue to process asteroids in order and handle splits by enqueuing new smaller asteroids

C. Use recursion to simulate all possible splits and collisions, returning the final stable configuration

D. Preprocess the input to split all asteroids into smallest units before running the original stack simulation

Solution

1. Step 1: Understand splitting behavior

   When an asteroid splits, the remaining part may still collide with others, requiring continued checks.

2. Step 2: Adapt stack simulation

   By pushing the smaller split asteroid back onto the stack and continuing the while loop, the algorithm correctly simulates ongoing collisions.

3. Step 3: Evaluate other options

   Queue breaks order assumptions; recursion risks TLE; preprocessing loses collision dynamics.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack with adjusted loop handles splits and collisions efficiently [OK]

Hint: Push remaining split asteroid back to stack for continued checks [OK]

Common Mistakes:

• Switching to queue breaks collision order
• Recursion causes inefficiency
• Preprocessing loses dynamic collisions

5. Suppose the calculator must now support expressions where numbers can be reused multiple times (e.g., "2*2*2") and the input length can be very large. Which modification to the optimal approach is necessary to handle this efficiently?

hard

A. Switch to a brute force left-to-right evaluation ignoring precedence to reduce complexity.

B. Implement memoization to cache results of subexpressions to avoid recomputation.

C. Use a stack to immediately evaluate multiplication and division, but keep track of last_num to handle repeated operations efficiently.

D. Use recursion with backtracking to explore all possible reuse combinations.

Solution

1. Step 1: Understand reuse impact

   Repeated multiplication/division requires immediate evaluation to maintain precedence and efficiency.

2. Step 2: Identify suitable approach

   Using a stack or stack-like variables to immediately compute * and / handles repeated operations efficiently without extra overhead.

3. Step 3: Reject alternatives

   Brute force ignores precedence, memoization is unnecessary for linear evaluation, recursion/backtracking is inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Immediate evaluation with stack variables handles reuse and large inputs efficiently [OK]

Hint: Immediate evaluation with stack variables handles repeated ops efficiently [OK]

Common Mistakes:

• Ignoring precedence in reuse
• Using recursion unnecessarily
• Trying brute force for efficiency