Next in Queue - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Data Structures, Linked List, Queue

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem

• Q: What does the problem ask for?
  • A: The problem asks for the implementation of a queue data structure using a singly linked list with the specified methods.
• Q: What should be returned?
  • A: The methods should perform the following actions:
    • 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

2: M-atch

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:

• Enqueue: Add a new node to the end of the linked list.
• Dequeue: Remove the node from the front of the linked list.
• Peek: Return the value of the front node without removing it.
• Is_Empty: Check if the front node is None.

3: P-lan

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

• Forgetting to handle the case where the queue becomes empty after a dequeue.
• Incorrectly managing the front and rear pointers during enqueue and dequeue.

4: I-mplement

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

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Example: Use the provided example usage to verify that the queue methods work correctly.

6: E-valuate

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.