On Repeat - 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, Two Pointers, Cycle Detection

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 determine if a linked list contains a cycle, where a node's next pointer points back to a previous node.
  • What approach can be used?
    • The problem can be solved using the two-pointer technique with a slow and a fast pointer to detect cycles.
HAPPY CASE
Input: playlist with 4 songs, where the last song points to the second song
Output: True
Explanation: The linked list contains a cycle.

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

EDGE CASE
Input: playlist with 3 songs, no cycle
Output: False
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, we want to consider the following approaches:

  • Two Pointers (Floyd's Cycle Detection Algorithm): Use slow and fast pointers to traverse the list at different speeds to detect cycles.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use two pointers, a slow pointer and a fast pointer. The slow pointer will move one step at a time, while the fast pointer will move two steps. If there is a cycle, the fast pointer will eventually meet the slow pointer. If the fast pointer reaches the end of the list, then there is no 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 the fast pointer reaches the end of the list, return False (no cycle).
4) Return True if a cycle is detected; otherwise, return False.

⚠️ Common Mistakes

  • Failing to check if the list is empty or if the fast pointer reaches the end.
  • Forgetting to increment both pointers properly.

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

def on_repeat(playlist_head):
    if not playlist_head:
        return False

    slow = playlist_head
    fast = playlist_head

    while fast and fast.next:
        slow = slow.next          # Move slow pointer by 1 step
        fast = fast.next.next     # Move fast pointer by 2 steps

        # If slow and fast meet, there's a cycle
        if slow == fast:
            return True

    # If fast reaches the end, there's no cycle
    return False

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 on_repeat returns True.
  • Watch: Verify that the slow and fast pointers move as expected and detect the cycle 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 once.
  • Space Complexity: O(1) because only a constant amount of extra space is used for the pointers.