Breaking the Cycle - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Cycle Detection, Floyd’s Cycle Detection Algorithm

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 identify and return the values of nodes that are part of any cycle in a linked list.
  • What should be returned?
    • An array containing the values of nodes that form a cycle in the linked list.
HAPPY CASE
Input: clue1 = Node("Unmarked sedan seen near the crime scene")
       clue2 = Node("The stolen goods are at an abandoned warehouse")
       clue3 = Node("The mayor is accepting bribes")
       clue4 = Node("They dumped their disguise in the lake")
       clue1.next = clue2
       clue2.next = clue3
       clue3.next = clue4
       clue4.next = clue2  # Creates a cycle
Output: ["The stolen goods are at an abandoned warehouse", "The mayor is accepting bribes", "They dumped their disguise in the lake"]
Explanation: These are the values of the nodes that form a cycle in the linked list.

HAPPY CASE
Input: clue5 = Node("A masked figure was seen fleeing the scene")
       clue6 = Node("Footprints lead to the nearby woods")
       clue7 = Node("A broken window was found at the back")
       clue5.next = clue6
       clue6.next = clue7
       clue7.next = None  # No cycle
Output: []
Explanation: No cycle detected, so the function returns an empty list.

EDGE CASE
Input: clue1 = Node("Unmarked sedan seen near the crime scene")
       clue1.next = clue1  # Self-loop
Output: ["Unmarked sedan seen near the crime scene"]
Explanation: The node points to itself, forming 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:

  • Floyd's Cycle Detection Algorithm: Also known as the "Tortoise and Hare" algorithm, this technique can be used to detect cycles and determine the start of the cycle.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use Floyd's Cycle Detection Algorithm to detect if a cycle exists in the linked list. If a cycle is detected, we will identify the starting node of the cycle and then collect all nodes that are part of the cycle.

1) Use Floyd's Cycle Detection Algorithm to detect if there is a cycle:
    a) Initialize two pointers, `slow` and `fast`, both pointing to the head of the list.
    b) Move `slow` by one step and `fast` by two steps.
    c) If `slow` meets `fast`, a cycle is detected.
2) If a cycle is detected, find the starting node of the cycle:
    a) Reset `slow` to the head of the list.
    b) Move both `slow` and `fast` one step at a time until they meet. The meeting point is the start of the cycle.
3) Traverse the cycle and collect all node values in an array.
4) Return the array of values.

⚠️ Common Mistakes

  • Failing to handle cases where the list is empty or contains no cycle.
  • Incorrectly identifying or traversing the cycle, leading to incorrect results.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def collect_false_evidence(evidence):
    if not evidence:
        return []

    # Step 1: Detect cycle using Floyd's Cycle Detection Algorithm
    slow = evidence
    fast = evidence

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        # No cycle detected
        return []

    # Step 2: Find the start of the cycle
    slow = evidence
    while slow != fast:
        slow = slow.next
        fast = fast.next

    # Step 3: Collect all nodes in the cycle
    cycle_start = slow
    cycle_values = []
    current = cycle_start
    while True:
        cycle_values.append(current.value)
        current = current.next
        if current == cycle_start:
            break

    return cycle_values

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 clue1 and clue5 linked lists to verify that the function correctly identifies and returns the nodes in the cycle.

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.
  • Space Complexity: O(K) where K is the length of the cycle, to store the nodes in the cycle.