641. Design Circular Deque
Problem Description
This problem asks you to implement a circular double-ended queue (deque) data structure with a fixed maximum capacity.
A deque is a data structure that allows insertion and deletion of elements from both ends (front and rear). The "circular" aspect means the underlying storage wraps around - when you reach the end of the array, the next position is back at the beginning.
You need to implement the MyCircularDeque
class with the following operations:
-
Constructor
MyCircularDeque(k)
: Creates a deque with maximum capacity ofk
elements. -
insertFront(value): Adds an element to the front of the deque. Returns
true
if successful,false
if the deque is full. -
insertLast(value): Adds an element to the rear of the deque. Returns
true
if successful,false
if the deque is full. -
deleteFront(): Removes the front element. Returns
true
if successful,false
if the deque is empty. -
deleteLast(): Removes the rear element. Returns
true
if successful,false
if the deque is empty. -
getFront(): Returns the value of the front element, or
-1
if the deque is empty. -
getRear(): Returns the value of the rear element, or
-1
if the deque is empty. -
isEmpty(): Returns
true
if the deque contains no elements,false
otherwise. -
isFull(): Returns
true
if the deque has reached its maximum capacity,false
otherwise.
The solution uses an array-based implementation with:
- A fixed-size array
q
to store elements - A
front
pointer to track the index of the front element - A
size
counter to track the current number of elements - The
capacity
to store the maximum size
The circular nature is handled using modulo arithmetic % capacity
to wrap indices around when they exceed the array bounds. When inserting at the front, the front pointer moves backward (with wraparound), and when inserting at the rear, elements are placed at position (front + size) % capacity
.
Intuition
The key insight for implementing a circular deque is to avoid the expensive operation of shifting elements when inserting or deleting from the front. In a regular array, inserting at position 0 would require moving all existing elements one position to the right, which takes O(n)
time.
The circular approach solves this by treating the array as if it wraps around - imagine the array bent into a circle where the last position connects back to the first. This way, we can maintain a "logical" front and rear that can be anywhere in the physical array.
We arrive at this solution by recognizing that:
-
We need fast operations at both ends: Using just a simple array would make front operations expensive. Using a linked list would work but requires extra memory for pointers.
-
Fixed capacity suggests array usage: Since we know the maximum size upfront, we can allocate a fixed-size array, which is memory-efficient.
-
Tracking positions with pointers: Instead of moving data, we move pointers. We only need to track where the front element is located (
front
pointer) and how many elements we have (size
). The rear position can always be calculated as(front + size - 1) % capacity
. -
Modulo arithmetic for wrapping: When we move past the array boundaries, modulo brings us back to the beginning. For example, if
front = 0
and we insert at the front, the new front becomes(0 - 1 + capacity) % capacity = capacity - 1
, which is the last position in the array. -
Size tracking simplifies empty/full checks: Rather than using complex pointer comparisons, we simply track the number of elements. Empty means
size == 0
, full meanssize == capacity
.
This design ensures all operations run in O(1)
time while using O(k)
space, where k
is the deque's capacity.
Learn more about Queue and Linked List patterns.
Solution Approach
The implementation uses an array-based circular buffer with three key variables to manage the deque state:
Data Structure Setup
- Array
q
: Fixed-size array of lengthk
to store elements front
: Index pointing to the front element (initialized to 0)size
: Current number of elements in the deque (initialized to 0)capacity
: Maximum capacityk
Core Operations Implementation
1. insertFront(value)
- First check if the deque is full using
isFull()
- If not empty, move the front pointer backward:
front = (front - 1 + capacity) % capacity
- Adding
capacity
before modulo ensures we get a positive result whenfront - 1
is negative
- Adding
- Place the value at the new front position:
q[front] = value
- Increment size by 1
2. insertLast(value)
- Check if the deque is full
- Calculate the rear position:
idx = (front + size) % capacity
- This gives us the next empty position after the current last element
- Place the value at this position:
q[idx] = value
- Increment size by 1
3. deleteFront()
- Check if the deque is empty using
isEmpty()
- Move the front pointer forward:
front = (front + 1) % capacity
- Decrement size by 1
- Note: We don't need to clear the old value; it will be overwritten if needed
4. deleteLast()
- Check if the deque is empty
- Simply decrement size by 1
- The rear element becomes inaccessible through the size reduction
5. getFront()
- Return
-1
if empty - Otherwise return
q[front]
6. getRear()
- Return
-1
if empty - Calculate rear position:
idx = (front + size - 1) % capacity
- We subtract 1 because
front + size
points to the next empty position
- We subtract 1 because
- Return
q[idx]
7. isEmpty() and isFull()
isEmpty()
: Simply check ifsize == 0
isFull()
: Check ifsize == capacity
Example Walkthrough
Consider a deque with capacity 3:
- Initial state:
q = [0, 0, 0]
,front = 0
,size = 0
insertLast(1)
:q = [1, 0, 0]
,front = 0
,size = 1
insertFront(2)
:front
becomes(0 - 1 + 3) % 3 = 2
,q = [1, 0, 2]
,size = 2
insertLast(3)
: Insert at(2 + 2) % 3 = 1
,q = [1, 3, 2]
,size = 3
- The logical order is:
[2, 1, 3]
with 2 at front (index 2) and 3 at rear (index 1)
This circular approach ensures all operations execute in O(1)
time complexity with O(k)
space complexity.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a sequence of operations on a circular deque with capacity 4 to see how the solution works:
Initial State:
q = [_, _, _, _]
(empty slots)front = 0
,size = 0
,capacity = 4
Step 1: insertLast(5)
- Check if full:
size (0) < capacity (4)
✓ - Calculate position:
idx = (0 + 0) % 4 = 0
- Insert value:
q[0] = 5
- Update size:
size = 1
- State:
q = [5, _, _, _]
,front = 0
,size = 1
Step 2: insertFront(3)
- Check if full:
size (1) < capacity (4)
✓ - Move front backward:
front = (0 - 1 + 4) % 4 = 3
- Insert value:
q[3] = 3
- Update size:
size = 2
- State:
q = [5, _, _, 3]
,front = 3
,size = 2
- Logical order:
[3, 5]
Step 3: insertFront(7)
- Check if full:
size (2) < capacity (4)
✓ - Move front backward:
front = (3 - 1 + 4) % 4 = 2
- Insert value:
q[2] = 7
- Update size:
size = 3
- State:
q = [5, _, 7, 3]
,front = 2
,size = 3
- Logical order:
[7, 3, 5]
Step 4: insertLast(9)
- Check if full:
size (3) < capacity (4)
✓ - Calculate position:
idx = (2 + 3) % 4 = 1
- Insert value:
q[1] = 9
- Update size:
size = 4
- State:
q = [5, 9, 7, 3]
,front = 2
,size = 4
- Logical order:
[7, 3, 5, 9]
Step 5: getRear()
- Not empty:
size > 0
✓ - Calculate rear:
idx = (2 + 4 - 1) % 4 = 1
- Return
q[1] = 9
Step 6: deleteFront()
- Not empty:
size > 0
✓ - Move front forward:
front = (2 + 1) % 4 = 3
- Update size:
size = 3
- State:
q = [5, 9, 7, 3]
,front = 3
,size = 3
- Logical order:
[3, 5, 9]
(7 is no longer accessible)
Step 7: getFront()
- Not empty:
size > 0
✓ - Return
q[3] = 3
This example demonstrates how the circular nature allows efficient insertion at both ends without shifting elements, with the front pointer wrapping around the array using modulo arithmetic.
Solution Implementation
1class MyCircularDeque:
2 def __init__(self, k: int):
3 """
4 Initialize the circular deque with a fixed capacity.
5
6 Args:
7 k: Maximum capacity of the deque
8 """
9 # Pre-allocate array with fixed size for O(1) operations
10 self.buffer = [0] * k
11 # Index pointing to the front element
12 self.front_index = 0
13 # Current number of elements in the deque
14 self.current_size = 0
15 # Maximum capacity of the deque
16 self.max_capacity = k
17
18 def insertFront(self, value: int) -> bool:
19 """
20 Insert an element at the front of the deque.
21
22 Args:
23 value: The value to insert
24
25 Returns:
26 True if insertion was successful, False if deque is full
27 """
28 # Check if deque has space for new element
29 if self.isFull():
30 return False
31
32 # Move front pointer backward circularly only if deque is not empty
33 # If empty, we insert at current front_index position
34 if not self.isEmpty():
35 self.front_index = (self.front_index - 1 + self.max_capacity) % self.max_capacity
36
37 # Place the new value at the front position
38 self.buffer[self.front_index] = value
39 # Increment the size counter
40 self.current_size += 1
41 return True
42
43 def insertLast(self, value: int) -> bool:
44 """
45 Insert an element at the rear of the deque.
46
47 Args:
48 value: The value to insert
49
50 Returns:
51 True if insertion was successful, False if deque is full
52 """
53 # Check if deque has space for new element
54 if self.isFull():
55 return False
56
57 # Calculate the rear position using front_index and size
58 rear_index = (self.front_index + self.current_size) % self.max_capacity
59 # Place the new value at the rear position
60 self.buffer[rear_index] = value
61 # Increment the size counter
62 self.current_size += 1
63 return True
64
65 def deleteFront(self) -> bool:
66 """
67 Remove the front element from the deque.
68
69 Returns:
70 True if deletion was successful, False if deque is empty
71 """
72 # Cannot delete from empty deque
73 if self.isEmpty():
74 return False
75
76 # Move front pointer forward circularly
77 self.front_index = (self.front_index + 1) % self.max_capacity
78 # Decrement the size counter
79 self.current_size -= 1
80 return True
81
82 def deleteLast(self) -> bool:
83 """
84 Remove the rear element from the deque.
85
86 Returns:
87 True if deletion was successful, False if deque is empty
88 """
89 # Cannot delete from empty deque
90 if self.isEmpty():
91 return False
92
93 # Simply decrement size; the rear position is calculated dynamically
94 self.current_size -= 1
95 return True
96
97 def getFront(self) -> int:
98 """
99 Get the value of the front element without removing it.
100
101 Returns:
102 The front element value, or -1 if deque is empty
103 """
104 # Return -1 for empty deque as per problem specification
105 if self.isEmpty():
106 return -1
107
108 # Return the element at front_index
109 return self.buffer[self.front_index]
110
111 def getRear(self) -> int:
112 """
113 Get the value of the rear element without removing it.
114
115 Returns:
116 The rear element value, or -1 if deque is empty
117 """
118 # Return -1 for empty deque as per problem specification
119 if self.isEmpty():
120 return -1
121
122 # Calculate rear position: front + size - 1 (wrapped around)
123 rear_index = (self.front_index + self.current_size - 1) % self.max_capacity
124 return self.buffer[rear_index]
125
126 def isEmpty(self) -> bool:
127 """
128 Check if the deque is empty.
129
130 Returns:
131 True if deque contains no elements, False otherwise
132 """
133 return self.current_size == 0
134
135 def isFull(self) -> bool:
136 """
137 Check if the deque is at maximum capacity.
138
139 Returns:
140 True if deque cannot accept more elements, False otherwise
141 """
142 return self.current_size == self.max_capacity
143
144
145# Your MyCircularDeque object will be instantiated and called as such:
146# obj = MyCircularDeque(k)
147# param_1 = obj.insertFront(value)
148# param_2 = obj.insertLast(value)
149# param_3 = obj.deleteFront()
150# param_4 = obj.deleteLast()
151# param_5 = obj.getFront()
152# param_6 = obj.getRear()
153# param_7 = obj.isEmpty()
154# param_8 = obj.isFull()
155
1class MyCircularDeque {
2 // Array to store deque elements
3 private int[] deque;
4 // Index pointing to the front element
5 private int frontIndex;
6 // Current number of elements in the deque
7 private int currentSize;
8 // Maximum capacity of the deque
9 private int maxCapacity;
10
11 /**
12 * Initialize your data structure here. Set the size of the deque to be k.
13 * @param k The maximum capacity of the circular deque
14 */
15 public MyCircularDeque(int k) {
16 deque = new int[k];
17 frontIndex = 0;
18 currentSize = 0;
19 maxCapacity = k;
20 }
21
22 /**
23 * Adds an item at the front of Deque. Return true if the operation is successful.
24 * @param value The value to be inserted at the front
25 * @return true if insertion is successful, false if deque is full
26 */
27 public boolean insertFront(int value) {
28 // Check if deque is full
29 if (isFull()) {
30 return false;
31 }
32
33 // Move front pointer backwards only if deque is not empty
34 if (!isEmpty()) {
35 // Circular decrement: move front index one position back
36 frontIndex = (frontIndex - 1 + maxCapacity) % maxCapacity;
37 }
38
39 // Insert value at new front position
40 deque[frontIndex] = value;
41 currentSize++;
42 return true;
43 }
44
45 /**
46 * Adds an item at the rear of Deque. Return true if the operation is successful.
47 * @param value The value to be inserted at the rear
48 * @return true if insertion is successful, false if deque is full
49 */
50 public boolean insertLast(int value) {
51 // Check if deque is full
52 if (isFull()) {
53 return false;
54 }
55
56 // Calculate rear position: front + size gives us the next empty slot
57 int rearIndex = (frontIndex + currentSize) % maxCapacity;
58 deque[rearIndex] = value;
59 currentSize++;
60 return true;
61 }
62
63 /**
64 * Deletes an item from the front of Deque. Return true if the operation is successful.
65 * @return true if deletion is successful, false if deque is empty
66 */
67 public boolean deleteFront() {
68 // Check if deque is empty
69 if (isEmpty()) {
70 return false;
71 }
72
73 // Move front pointer forward (circular increment)
74 frontIndex = (frontIndex + 1) % maxCapacity;
75 currentSize--;
76 return true;
77 }
78
79 /**
80 * Deletes an item from the rear of Deque. Return true if the operation is successful.
81 * @return true if deletion is successful, false if deque is empty
82 */
83 public boolean deleteLast() {
84 // Check if deque is empty
85 if (isEmpty()) {
86 return false;
87 }
88
89 // Simply decrease size, no need to move pointers
90 currentSize--;
91 return true;
92 }
93
94 /**
95 * Get the front item from the deque.
96 * @return The front element value, or -1 if deque is empty
97 */
98 public int getFront() {
99 if (isEmpty()) {
100 return -1;
101 }
102 return deque[frontIndex];
103 }
104
105 /**
106 * Get the last item from the deque.
107 * @return The rear element value, or -1 if deque is empty
108 */
109 public int getRear() {
110 if (isEmpty()) {
111 return -1;
112 }
113
114 // Calculate rear position: last element is at (front + size - 1)
115 int rearIndex = (frontIndex + currentSize - 1) % maxCapacity;
116 return deque[rearIndex];
117 }
118
119 /**
120 * Checks whether the circular deque is empty or not.
121 * @return true if deque is empty, false otherwise
122 */
123 public boolean isEmpty() {
124 return currentSize == 0;
125 }
126
127 /**
128 * Checks whether the circular deque is full or not.
129 * @return true if deque is full, false otherwise
130 */
131 public boolean isFull() {
132 return currentSize == maxCapacity;
133 }
134}
135
136/**
137 * Your MyCircularDeque object will be instantiated and called as such:
138 * MyCircularDeque obj = new MyCircularDeque(k);
139 * boolean param_1 = obj.insertFront(value);
140 * boolean param_2 = obj.insertLast(value);
141 * boolean param_3 = obj.deleteFront();
142 * boolean param_4 = obj.deleteLast();
143 * int param_5 = obj.getFront();
144 * int param_6 = obj.getRear();
145 * boolean param_7 = obj.isEmpty();
146 * boolean param_8 = obj.isFull();
147 */
148
1class MyCircularDeque {
2private:
3 vector<int> buffer; // Fixed-size array to store deque elements
4 int frontIndex; // Index pointing to the front element
5 int currentSize; // Current number of elements in the deque
6 int maxCapacity; // Maximum capacity of the deque
7
8public:
9 // Constructor: Initialize circular deque with maximum size k
10 MyCircularDeque(int k) {
11 buffer.assign(k, 0);
12 frontIndex = 0;
13 currentSize = 0;
14 maxCapacity = k;
15 }
16
17 // Insert an element at the front of the deque
18 bool insertFront(int value) {
19 // Check if deque is full
20 if (isFull()) {
21 return false;
22 }
23
24 // Move front pointer backward circularly (only if deque is not empty)
25 if (!isEmpty()) {
26 frontIndex = (frontIndex - 1 + maxCapacity) % maxCapacity;
27 }
28
29 // Insert value at new front position
30 buffer[frontIndex] = value;
31 currentSize++;
32 return true;
33 }
34
35 // Insert an element at the rear of the deque
36 bool insertLast(int value) {
37 // Check if deque is full
38 if (isFull()) {
39 return false;
40 }
41
42 // Calculate rear position and insert value
43 int rearIndex = (frontIndex + currentSize) % maxCapacity;
44 buffer[rearIndex] = value;
45 currentSize++;
46 return true;
47 }
48
49 // Delete the front element from the deque
50 bool deleteFront() {
51 // Check if deque is empty
52 if (isEmpty()) {
53 return false;
54 }
55
56 // Move front pointer forward circularly
57 frontIndex = (frontIndex + 1) % maxCapacity;
58 currentSize--;
59 return true;
60 }
61
62 // Delete the last element from the deque
63 bool deleteLast() {
64 // Check if deque is empty
65 if (isEmpty()) {
66 return false;
67 }
68
69 // Simply decrease size (rear pointer is calculated dynamically)
70 currentSize--;
71 return true;
72 }
73
74 // Get the front element of the deque
75 int getFront() {
76 return isEmpty() ? -1 : buffer[frontIndex];
77 }
78
79 // Get the rear element of the deque
80 int getRear() {
81 if (isEmpty()) {
82 return -1;
83 }
84 // Calculate rear position: (front + size - 1) with wrap-around
85 int rearIndex = (frontIndex + currentSize - 1) % maxCapacity;
86 return buffer[rearIndex];
87 }
88
89 // Check if the deque is empty
90 bool isEmpty() {
91 return currentSize == 0;
92 }
93
94 // Check if the deque is full
95 bool isFull() {
96 return currentSize == maxCapacity;
97 }
98};
99
100/**
101 * Your MyCircularDeque object will be instantiated and called as such:
102 * MyCircularDeque* obj = new MyCircularDeque(k);
103 * bool param_1 = obj->insertFront(value);
104 * bool param_2 = obj->insertLast(value);
105 * bool param_3 = obj->deleteFront();
106 * bool param_4 = obj->deleteLast();
107 * int param_5 = obj->getFront();
108 * int param_6 = obj->getRear();
109 * bool param_7 = obj->isEmpty();
110 * bool param_8 = obj->isFull();
111 */
112
1// Global variables for circular deque implementation
2let vals: number[]; // Array to store deque elements
3let length: number; // Current number of elements in deque
4let size: number; // Maximum capacity of deque
5let start: number; // Index pointing to the front element
6let end: number; // Index pointing to the position after rear element
7
8/**
9 * Initialize the circular deque with maximum size k
10 * @param k - Maximum capacity of the deque
11 */
12function MyCircularDeque(k: number): void {
13 vals = new Array(k).fill(0);
14 start = 0;
15 end = 0;
16 length = 0;
17 size = k;
18}
19
20/**
21 * Add an element at the front of the deque
22 * @param value - Value to be inserted
23 * @returns true if operation successful, false if deque is full
24 */
25function insertFront(value: number): boolean {
26 // Check if deque is full
27 if (isFull()) {
28 return false;
29 }
30
31 // Move start pointer backward circularly
32 if (start === 0) {
33 start = size - 1;
34 } else {
35 start--;
36 }
37
38 // Insert value at new front position
39 vals[start] = value;
40 length++;
41 return true;
42}
43
44/**
45 * Add an element at the rear of the deque
46 * @param value - Value to be inserted
47 * @returns true if operation successful, false if deque is full
48 */
49function insertLast(value: number): boolean {
50 // Check if deque is full
51 if (isFull()) {
52 return false;
53 }
54
55 // Insert value at current end position
56 vals[end] = value;
57 length++;
58
59 // Move end pointer forward circularly
60 if (end + 1 === size) {
61 end = 0;
62 } else {
63 end++;
64 }
65 return true;
66}
67
68/**
69 * Delete an element from the front of the deque
70 * @returns true if operation successful, false if deque is empty
71 */
72function deleteFront(): boolean {
73 // Check if deque is empty
74 if (isEmpty()) {
75 return false;
76 }
77
78 // Move start pointer forward circularly
79 if (start + 1 === size) {
80 start = 0;
81 } else {
82 start++;
83 }
84 length--;
85 return true;
86}
87
88/**
89 * Delete an element from the rear of the deque
90 * @returns true if operation successful, false if deque is empty
91 */
92function deleteLast(): boolean {
93 // Check if deque is empty
94 if (isEmpty()) {
95 return false;
96 }
97
98 // Move end pointer backward circularly
99 if (end === 0) {
100 end = size - 1;
101 } else {
102 end--;
103 }
104 length--;
105 return true;
106}
107
108/**
109 * Get the front element of the deque
110 * @returns Front element value, or -1 if deque is empty
111 */
112function getFront(): number {
113 // Return -1 if deque is empty
114 if (isEmpty()) {
115 return -1;
116 }
117
118 // Return element at start position
119 return vals[start];
120}
121
122/**
123 * Get the rear element of the deque
124 * @returns Rear element value, or -1 if deque is empty
125 */
126function getRear(): number {
127 // Return -1 if deque is empty
128 if (isEmpty()) {
129 return -1;
130 }
131
132 // Get the actual rear position (one position before end)
133 if (end === 0) {
134 return vals[size - 1];
135 }
136 return vals[end - 1];
137}
138
139/**
140 * Check if the deque is empty
141 * @returns true if deque is empty, false otherwise
142 */
143function isEmpty(): boolean {
144 return length === 0;
145}
146
147/**
148 * Check if the deque is full
149 * @returns true if deque is full, false otherwise
150 */
151function isFull(): boolean {
152 return length === size;
153}
154
Time and Space Complexity
Time Complexity:
__init__(k)
:O(k)
- initializing an array of size kinsertFront(value)
:O(1)
- only involves modular arithmetic and array indexinginsertLast(value)
:O(1)
- only involves modular arithmetic and array indexingdeleteFront()
:O(1)
- only involves modular arithmetic and updating pointersdeleteLast()
:O(1)
- only involves decrementing the size countergetFront()
:O(1)
- direct array access at the front indexgetRear()
:O(1)
- calculating index using modular arithmetic and array accessisEmpty()
:O(1)
- simple comparison operationisFull()
:O(1)
- simple comparison operation
Space Complexity:
- Overall space complexity:
O(k)
where k is the capacity of the deque - The implementation uses a fixed-size array
self.q
of size k to store elements - Additional variables (
self.front
,self.size
,self.capacity
) useO(1)
extra space - No additional space is used that scales with the number of operations
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect Front Pointer Movement in insertFront()
Pitfall: A critical bug in the provided code is that insertFront()
only moves the front pointer backward when the deque is not empty. This causes incorrect behavior when inserting multiple elements at the front starting from an empty deque.
Example of the bug:
deque = MyCircularDeque(3) deque.insertFront(1) # front_index stays 0, size = 1 deque.insertFront(2) # front_index becomes 2, overwrites at index 2 # Buffer: [1, 0, 2], but logically should be [2, 1]
Solution: Always move the front pointer backward before insertion:
def insertFront(self, value: int) -> bool:
if self.isFull():
return False
# Always move front pointer backward for front insertion
self.front_index = (self.front_index - 1 + self.max_capacity) % self.max_capacity
self.buffer[self.front_index] = value
self.current_size += 1
return True
2. Negative Index Wraparound Without Adding Capacity
Pitfall: When calculating (front_index - 1) % capacity
, if front_index
is 0, the result becomes -1 % capacity
, which in Python gives capacity - 1
(correct), but in other languages like Java or C++, it might give -1
, causing array index out of bounds.
Solution: Always add capacity before taking modulo to ensure positive result:
# Safe approach that works in all languages self.front_index = (self.front_index - 1 + self.max_capacity) % self.max_capacity
3. Confusion Between Rear Index and Next Empty Position
Pitfall: Mixing up the actual rear element position with the next insertion position. The rear element is at (front + size - 1) % capacity
, while the next insertion position for insertLast()
is at (front + size) % capacity
.
Example mistake:
def getRear(self) -> int:
if self.isEmpty():
return -1
# Wrong: This gives the next empty position, not the rear element
rear_index = (self.front_index + self.current_size) % self.max_capacity
return self.buffer[rear_index]
Solution: Remember that:
- Rear element position:
(front + size - 1) % capacity
- Next insertion position:
(front + size) % capacity
4. Not Handling Edge Case of Single Element
Pitfall: When the deque has only one element, both getFront()
and getRear()
should return the same value, but incorrect index calculations might fail this case.
Test case to verify:
deque = MyCircularDeque(3) deque.insertFront(5) assert deque.getFront() == 5 # Should be 5 assert deque.getRear() == 5 # Should also be 5
5. Memory Leak Concerns (Language-Specific)
Pitfall: In languages with manual memory management or when storing objects, not clearing references when deleting elements can cause memory leaks.
Solution for object storage:
def deleteFront(self) -> bool:
if self.isEmpty():
return False
# Optional: Clear the reference if storing objects
# self.buffer[self.front_index] = None
self.front_index = (self.front_index + 1) % self.max_capacity
self.current_size -= 1
return True
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!