Design Circular Deque

Medium

Design Circular Deque

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum capacity of the circular deque that needs to be supported?
Can I assume the values inserted into the deque will be integers, or do I need to handle other data types?
What should happen if I try to insert an element when the deque is full (both front and rear)? Should it throw an exception, return a specific value, or is this an invalid operation?
What should the `getFront` and `getRear` methods return when the deque is empty? Should it be null, a special value, or should an exception be thrown?
Do I need to handle any potential integer overflow scenarios when performing operations like incrementing or decrementing indices within the circular buffer?

Brute Force Solution

Approach

The brute force method for building a circular deque involves directly simulating all operations. For each new element, we attempt to insert it at all possible positions, and for removals, we simply shift elements to fill the gap.

Here's how the algorithm would work step-by-step:

To start, imagine you have an empty container that can hold a specific number of things.
If you want to add something to the front, just put it there, but check if the container is already full first.
If you want to add something to the back, put it at the end, again ensuring there's space.
If you want to remove something from the front, take it out and shift everything else forward to close the gap.
If you want to remove something from the back, just take out the last thing.
Each time you add or remove, make sure you're not going over the container's limit.
If you try to add to a full container or remove from an empty container, just say you can't.

Code Implementation

class MyCircularDeque:

    def __init__(self, max_size):
        self.deque = [None] * max_size
        self.max_size = max_size
        self.current_size = 0

    def insertFront(self, value):
        if self.isFull():
            return False

        # Shift elements to make space at the front.
        for index in range(self.current_size, 0, -1):
            self.deque[index] = self.deque[index - 1]

        self.deque[0] = value
        self.current_size += 1
        return True

    def insertLast(self, value):
        if self.isFull():
            return False

        self.deque[self.current_size] = value
        self.current_size += 1
        return True

    def deleteFront(self):
        if self.isEmpty():
            return False

        # Shift elements to fill the gap at the front.
        for index in range(0, self.current_size - 1):
            self.deque[index] = self.deque[index + 1]

        self.deque[self.current_size - 1] = None

        self.current_size -= 1
        return True

    def deleteLast(self):
        if self.isEmpty():
            return False

        # Removing the last element.
        self.deque[self.current_size - 1] = None
        self.current_size -= 1
        return True

    def getFront(self):
        if self.isEmpty():
            return -1
        return self.deque[0]

    def getRear(self):
        if self.isEmpty():
            return -1

        # Return last element.
        return self.deque[self.current_size - 1]

    def isEmpty(self):
        return self.current_size == 0

    def isFull(self):
        # Checking if the container is already full.
        return self.current_size == self.max_size

Big(O) Analysis

Time Complexity

O(n) – The addFront and removeFront operations in the brute force approach involve shifting elements. In the worst-case scenario, adding or removing from the front requires shifting all existing elements (n elements) to make space or fill the gap. Since other operations like addRear and removeRear take constant time, the dominant operations are addFront and removeFront that take O(n) time. Thus, the overall time complexity for a single addFront or removeFront operation is O(n).

Space Complexity

O(1) – The brute force implementation of the circular deque, as described, does not utilize any auxiliary data structures that scale with the input size. It operates directly within the fixed-size container, adding and removing elements by shifting existing ones. No temporary lists, hash maps, or recursion are involved. Therefore, the space complexity remains constant, independent of the container's maximum size.

Optimal Solution

Approach

We'll create a data structure that acts like a line of people waiting, where people can join at either end. The key is to use a fixed amount of space, and remember the location of the first and last person in line, adjusting these locations as people join and leave.

Here's how the algorithm would work step-by-step:

Set aside a specific, unchangeable amount of space to hold the people in line.
Keep track of where the front and back of the line are located within this space.
When someone joins the back of the line, place them in the next available spot and adjust the 'back' location.
If the 'back' reaches the end of the space, loop it back to the beginning.
When someone joins the front of the line, place them in the previous available spot and adjust the 'front' location.
If the 'front' reaches the beginning of the space, loop it back to the end.
When someone leaves the front of the line, just update the 'front' location to point to the next person.
When someone leaves the back of the line, just update the 'back' location to point to the previous person.
Make sure that as people join and leave, the 'front' and 'back' locations never cross each other, indicating an empty line.
Also, ensure the 'front' and 'back' locations only loop around if they reach the start or end of the reserved space.

Code Implementation

class CircularDeque:

    def __init__(self, circular_deque_capacity):
        self.circular_deque_capacity = circular_deque_capacity
        self.circular_deque = [None] * circular_deque_capacity
        self.front_index = 0
        self.back_index = 0
        self.current_size = 0

    def insertFront(self, value):
        if self.isFull():
            return False

        # Move front back, looping if necessary
        self.front_index = (self.front_index - 1) % self.circular_deque_capacity

        self.circular_deque[self.front_index] = value
        self.current_size += 1
        return True

    def insertLast(self, value):
        if self.isFull():
            return False

        self.circular_deque[self.back_index] = value
        self.back_index = (self.back_index + 1) % self.circular_deque_capacity

        self.current_size += 1
        return True

    def deleteFront(self):
        if self.isEmpty():
            return False

        self.circular_deque[self.front_index] = None
        # Move front forward, looping if necessary
        self.front_index = (self.front_index + 1) % self.circular_deque_capacity

        self.current_size -= 1
        return True

    def deleteLast(self):
        if self.isEmpty():
            return False

        # Move back backward, looping if necessary
        self.back_index = (self.back_index - 1) % self.circular_deque_capacity
        self.circular_deque[self.back_index] = None

        self.current_size -= 1
        return True

    def getFront(self):
        if self.isEmpty():
            return -1
        return self.circular_deque[self.front_index]

    def getRear(self):
        if self.isEmpty():
            return -1

        rear_index = (self.back_index - 1) % self.circular_deque_capacity
        return self.circular_deque[rear_index]

    def isEmpty(self):
        return self.current_size == 0

    def isFull(self):
        # Check if queue is full.
        return self.current_size == self.circular_deque_capacity

Big(O) Analysis

Time Complexity

O(1) – All operations in this circular deque implementation, such as inserting or deleting elements at the front or back, involve a fixed number of steps: updating the head or tail pointer, and accessing or modifying an element at a specific index within the fixed-size array. The size of the deque (n) does not affect the time taken for these operations. Thus, each operation takes constant time, independent of the number of elements currently stored, and the time complexity is O(1).

Space Complexity

O(1) – The data structure utilizes a fixed amount of space to store the elements in the line, determined during initialization. It maintains two index variables, 'front' and 'back', to keep track of the line's boundaries within this fixed space. The amount of space used by these index variables and the fixed storage is independent of the number of operations performed (joining or leaving), so the auxiliary space used remains constant regardless of the number of elements N. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Deque capacity is 0	The constructor should probably throw an exception or the operations return an error code as no elements can be stored.
Adding elements beyond deque's capacity	Insertion operations should either return an error code, throw an exception, or silently do nothing, depending on the design requirements.
Removing from an empty deque	Removal operations should return an error code, throw an exception, or return a specific value (e.g., null) to indicate an empty deque.
Operations called in rapid succession (e.g., many inserts then many deletes)	Check for potential race conditions if the Deque is intended for multi-threaded use, and ensure proper locking mechanisms are in place.
Integer overflow when calculating indices (e.g., head or tail)	Use appropriate data types (e.g., long) or modulo operations to prevent integer overflow when performing index calculations.
Testing with very large capacity deque (close to max integer value)	Check memory allocation to ensure there are no out-of-memory errors when initializing a very large deque.
Alternating addFront and addRear operations to fill the queue	This tests that both front and rear pointers are correctly incremented/decremented in the wrap-around fashion.
Deleting all elements then adding elements again	This ensures the pointers are reset properly, and the insertion works fine after the Deque has been emptied out.