Volume Control - codepath/compsci_guides GitHub Wiki

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-35 mins
• 🛠️ Topics: Linked Lists, Two Pointers, Cycle Detection

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 to return the length of the cycle in a linked list if a cycle exists, otherwise return 0.
• Q: What approach can be used?
  • A: The problem can be solved using the two-pointer technique with a slow and fast pointer to detect and then measure the cycle.

HAPPY CASE
Input: playlist with 4 songs, where the last song points to the second song
Output: 3
Explanation: The linked list contains a cycle of length 3.

EDGE CASE
Input: playlist = None
Output: 0
Explanation: An empty list does not contain a cycle.

EDGE CASE
Input: playlist with 3 songs, no cycle
Output: 0
Explanation: The linked list does not contain a cycle.

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 involving Cycle Detection and Measurement, we want to consider the following approaches:

• Two Pointers (Floyd's Cycle Detection Algorithm): Use slow and fast pointers to detect the cycle, then measure its length.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will first use two pointers to detect the cycle. Once a cycle is detected, we will keep one pointer fixed and move the other pointer to count the length of the cycle.

1) Initialize two pointers, `slow` and `fast`, both pointing to the `head` of the list.
2) Traverse the list:
    a) Move the `slow` pointer by one step.
    b) Move the `fast` pointer by two steps.
    c) If the slow pointer and fast pointer meet, a cycle exists.
3) If a cycle is detected:
    a) Keep one pointer fixed at the meeting point.
    b) Move the other pointer step by step until it meets the fixed pointer again, counting the number of steps.
4) Return the count as the length of the cycle.
5) If no cycle is detected, return `0`.

⚠️ Common Mistakes

• Failing to check if the list is empty or if the fast pointer reaches the end.
• Incorrectly counting the cycle length by not resetting the pointer or not correctly identifying the cycle.

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

# Function to detect the length of the cycle
def loop_length(playlist_head):
    if not playlist_head:
        return 0

    slow = playlist_head
    fast = playlist_head

    # First, detect if a cycle exists
    while fast and fast.next:
        slow = slow.next          # Move slow pointer by 1 step
        fast = fast.next.next     # Move fast pointer by 2 steps

        # Cycle detected
        if slow == fast:
            # Now calculate the cycle length
            cycle_length = 0
            current = slow
            while True:
                current = current.next
                cycle_length += 1
                if current == slow:
                    break
            return cycle_length

    # No cycle found
    return 0

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 playlist example where the last song points to the second song, and ensure that loop_length returns 3.
• Watch: Verify that the slow and fast pointers move as expected and detect and count the cycle length 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 nodes in the linked list.

• Time Complexity: O(N) because each node is visited at most twice, once to detect the cycle and once to measure it.
• Space Complexity: O(1) because only a constant amount of extra space is used for the pointers.