algoadvance

Problem Statement

A circular deque (double-ended queue) is a deque data structure that supports various operations to insert and delete elements from both ends. Implement the following operations:

  1. MyCircularDeque(k): Constructor, set the size of the deque to be k.
  2. insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
  3. insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
  4. deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
  5. deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
  6. getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
  7. getRear(): Gets the last item from the Deque. If the deque is empty, return -1.
  8. isEmpty(): Checks whether the circular deque is empty or not.
  9. isFull(): Checks whether the circular deque is full or not.

Clarifying Questions

  1. Are there any constraints on the values of k (the size of the deque)?
  2. What range of values can elements of the deque take?
  3. Is it possible to get negative values for the operations return, or is it always non-negative integers?

Strategy

  1. Use a fixed-size array to implement the deque along with two pointers (front and last) to manage the insertion and deletion at both ends.
  2. Maintain a count of the current number of elements in the deque to help check if it is empty or full.
  3. Use modular arithmetic to handle the wrap-around in the circular deque.

Time Complexity

Let’s write the code:

class MyCircularDeque:
    def __init__(self, k: int):
        self.deque = [0] * k
        self.size = 0
        self.capacity = k
        self.front = 0
        self.rear = -1
    
    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.front = (self.front - 1) % self.capacity
        self.deque[self.front] = value
        self.size += 1
        return True
    
    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        self.rear = (self.rear + 1) % self.capacity
        self.deque[self.rear] = value
        self.size += 1
        return True
    
    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True
    
    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1) % self.capacity
        self.size -= 1
        return True
    
    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.deque[self.front]
    
    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.deque[self.rear]
    
    def isEmpty(self) -> bool:
        return self.size == 0
    
    def isFull(self) -> bool:
        return self.size == self.capacity

# Example usage:
# circularDeque = MyCircularDeque(3)
# print(circularDeque.insertLast(1))  # return True
# print(circularDeque.insertLast(2))  # return True
# print(circularDeque.insertFront(3)) # return True
# print(circularDeque.insertFront(4)) # return False, the queue is full
# print(circularDeque.getRear())      # return 2
# print(circularDeque.isFull())       # return True
# print(circularDeque.deleteLast())   # return True
# print(circularDeque.insertFront(4)) # return True
# print(circularDeque.getFront())     # return 4

This implementation maintains efficient operations with O(1) time complexity for insertion, deletion, and access operations in the deque.

Try our interview co-pilot at AlgoAdvance.com