TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem
enqueue
: Adds an element to the end of the queue.dequeue
: Removes and returns the element at the front of the queue.peek
: Returns the value of the element at the front of the queue without removing it.is_empty
: Returns True
if the queue is empty, otherwise False
.
HAPPY CASE
Input:
- Create a new Queue
- Enqueue the elements ('Love Song', 'Sara Bareilles'), ('Ballad of Big Nothing', 'Elliot Smith'), ('Hug from a Dinosaur', 'Torres')
- Peek at the front element
- Dequeue two elements
- Check if the queue is empty
- Dequeue the last element
- Check if the queue is empty again
Output:
- Queue after enqueues: ('Love Song', 'Sara Bareilles') -> ('Ballad of Big Nothing', 'Elliot Smith') -> ('Hug from a Dinosaur', 'Torres')
- Peek: ('Love Song', 'Sara Bareilles')
- Dequeue 1: ('Love Song', 'Sara Bareilles')
- Dequeue 2: ('Ballad of Big Nothing', 'Elliot Smith')
- Is Empty: False
- Dequeue 3: ('Hug from a Dinosaur', 'Torres')
- Is Empty: True
EDGE CASE
Input:
- Create a new Queue
- Dequeue from an empty queue
- Peek at the front element of an empty queue
Output:
- Dequeue: None
- Peek: None
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 Queue problems involving Linked List Implementation, we want to consider the following approaches:
None
.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Implement a Queue class using a linked list, where the front of the queue corresponds to the head of the linked list, and the rear corresponds to the tail.
1) Initialize a Queue class with `front` and `rear` pointers.
2) Implement the `enqueue` method to add a new node to the rear of the queue.
3) Implement the `dequeue` method to remove the node from the front of the queue and update the pointers accordingly.
4) Implement the `peek` method to return the value of the front node.
5) Implement the `is_empty` method to check if the queue is empty.
⚠️ Common Mistakes
dequeue
.front
and rear
pointers during enqueue
and dequeue
.Implement the code to solve the algorithm.
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next
class Queue:
def __init__(self):
self.front = None
self.rear = None
def is_empty(self):
return self.front is None
def enqueue(self, song, artist):
new_node = Node(song, artist)
if self.rear:
self.rear.next = new_node
self.rear = new_node
if not self.front:
self.front = new_node
def dequeue(self):
if self.is_empty():
return None
removed_node = self.front
self.front = self.front.next
if not self.front:
self.rear = None
return removed_node.value
def peek(self):
if self.is_empty():
return None
return self.front.value
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of elements in the queue.
Time Complexity:
enqueue
: O(1)
because adding an element to the end of the linked list takes constant time.dequeue
: O(1)
because removing the front element also takes constant time.peek
: O(1)
because accessing the front element takes constant time.is_empty
: O(1)
because it simply checks if the front
is None
.Space Complexity: O(N)
because each element requires a node in the linked list.