Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
There may be a bug in the final soln

kfaham

Nov 30, 2023

For the input: [0,1,2,3,4]

It should result in false, since although its a cycle, there's only 1 element. But instead the "correct" answer says its supposed to be "True"

My answer for reference:

class Solution:   def loopExists(self, arr):     next_index = self.traverse(0, arr[0], arr)     slow = next_index     fast = self.traverse(0, arr[0], arr)     fast = self.traverse(fast, arr[fast], arr)     while slow != fast:       slow = self.traverse(slow, arr[slow], arr)       fast = self.traverse(fast, arr[fast], arr)       fast = self.traverse(fast, arr[fast], arr)     #We have now entered the main cycle.     #From here, we want to see if we meet again without hitting any other direction     fast = self.traverse(fast, arr[fast], arr)     if slow == fast:       return False     if arr[slow] > 0:       while slow != fast:         if arr[fast] < 0:           return False         fast = self.traverse(fast, arr[fast], arr)       return True     if arr[slow] < 0:       while slow != fast:         if arr[fast] > 0:           return False         fast = self.traverse(fast, arr[fast], arr)       return True     return False   def traverse(self, start, steps, arr):     length = len(arr)     totalLocation = start + steps     if totalLocation >= 0 and totalLocation < len(arr) - 1:       return totalLocation     elif totalLocation > 0:       return totalLocation % length     elif totalLocation < 0:       x = -1 * (abs(totalLocation) % length)       finLocation = len(arr) + x       return finLocation

1

0

Comments
Comments
Tu Huy Nguyen
Tu Huy Nguyen9 months ago

There are many paths for this and at least a path have more than 1 element.

On this page