Glitching Out - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 1 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Debugging

1: U-nderstand

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

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What does the problem ask for?
    • The problem asks to remove the first node with a given song from a singly linked list.
  • What are potential edge cases?
    • The list could be empty.
    • The song to be removed could be at the head of the list.
    • The song to be removed might not be present in the list.
HAPPY CASE
Input: playlist = SongNode("SOS", "ABBA", SongNode("Dreams", "Fleetwood Mac", SongNode("Lovely Day", "Bill Withers")))
Output: ("SOS", "ABBA") -> ("Lovely Day", "Bill Withers")
Explanation: "Dreams" is correctly removed from the list.

EDGE CASE
Input: playlist = None, song = "Dreams"
Output: None
Explanation: An empty list remains empty.

EDGE CASE
Input: playlist = SongNode("SOS", "ABBA"), song = "Dreams"
Output: ("SOS", "ABBA")
Explanation: Since "Dreams" is not present, the list remains unchanged.

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 Linked List problems, we want to consider the following approaches:

  • Traversal: We need to traverse the list to find the node with the specified song.
  • Pointer Manipulation: Once the node is found, we need to update pointers to remove the node.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list, and when we find the node with the specified song, we will adjust the pointers to remove that node from the list.

1) If the list is empty, return None.
2) If the head node contains the song to be removed, return the next node.
3) Traverse the list:
    a) If the next node contains the song to be removed, adjust the current node's next pointer to skip the next node.
4) Continue until the end of the list is reached or the song is removed.
5) Return the (possibly modified) head of the list.

⚠️ Common Mistakes

  • Updating current instead of current.next after removing a node.
  • Not properly handling the case where the head node is the one to be removed.

4: I-mplement

Implement the code to solve the algorithm.

class SongNode:
    def __init__(self, song, artist, next=None):
        self.song = song
        self.artist = artist
        self.next = next

# For testing
def print_linked_list(node):
    current = node
    while current:
        print((current.song, current.artist), end=" -> " if current.next else ")
        current = current.next
    print()

# Fixed function!
def remove_song(playlist_head, song):
    if not playlist_head:
        return None

    # If the head node itself needs to be removed
    if playlist_head.song == song:
        return playlist_head.next

    current = playlist_head
    while current.next:
        if current.next.song == song:
            # Fix: properly update the next pointer to skip the node
            current.next = current.next.next
            return playlist_head  # head remains the same

        current = current.next

    return playlist_head

5: R-eview

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

  • Example: Run the code with a playlist containing the song to be removed both at the head and in the middle of the list.
  • Watch: Confirm that current.next is updated correctly and the node with the given song is removed.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the linked list.

  • Time Complexity: O(N) because we may need to traverse the entire list to find the song to remove.
  • Space Complexity: O(1) because we are not using any extra space beyond the list itself.