TIP102 Unit 6 Session 2 Standard (Click for link to problem statements)
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?
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.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:
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
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_valuesReview the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
clue1 and clue5 linked lists to verify that the function correctly identifies and returns the nodes in the cycle.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.
O(N) because each node is visited at most twice.O(K) where K is the length of the cycle, to store the nodes in the cycle.