educative.io

Why doesn't this work?

Courses
,
#1

I have come up with a slightly different solution that passes all test cases and seems correct, however it times out when submitting.

def circular_array_loop(arr):
    def _is_same_direction(value1, value2):
        return (value1 > 0) == (value2 > 0)

    def _is_infinite_loop(value):
        return value % len(arr) == 0

    for slow_index, slow_value in enumerate(arr):
        fast_index = slow_index
        fast_value = slow_value
        while _is_same_direction(slow_value, fast_value) and not _is_infinite_loop(fast_value):
            fast_index = (fast_index + fast_value) % len(arr)
            fast_value = arr[fast_index]
            if fast_index == slow_index:
                return True
    return False

Why is this failing?

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Circular Array Loop - Grokking Coding Interview Patterns in Python

#2

Hey @dip_n_dots

I also ran the code and it timed out for me too. You may want to check your implementation of the _is_infinite_loop function, as the code was unable to detect circularity in the array [1, 2, 1, 2, 1, 2].

Nevertheless, I’m glad to hear that you’re trying different solutions and I hope this helps. You can let me know if you have any further questions. Good luck with your solution!

Happy Learning

#3

Thank you so much for this response! That case is exactly why my solution does not work for this problem. I would suggest that this case be added to the lesson (or at least the test cases) because it is this case that necessitates the use of the fast and slow pointer approach and really helps one to understand why we need to use it. Without it, a simpler approach would work.
Thanks

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Palindrome Linked List - Grokking Coding Interview Patterns in Python