Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 3: Cycle in a Circular Array (hard)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

case [0, 1, 2, 3, 4] / there is no cycle from index 0 we cant move to any direction

here is my solution

from math import fmod

class Solution:
  def loopExists(self, arr):
    # this method calculates the new index/direction after + or - shift
    # the new index will be in the range of array length
    def move(index, arr):
      val = arr[index]

      new_index = index + val

      # figure out the direction of the move
      direction = 'n' # no direction
      if new_index > index:
        direction = 'r' # right
      elif new_index < index:
        direction = 'l' # left

      # if index exceeds the boundary of the array
      if new_index < 0 or new_index >= len(arr):
        if new_index > 0:
          index = fmod(new_index, len(arr)) # positive or zero
Show 1 reply
A

Anonymous

· 3 years ago

In example 3 with input [2, 1, -1, -2] we already have a circle 1 -> 2 -> 1 isn't it?

Show 1 reply
A

Anonymous

· 3 years ago

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
A

Anonymous

· 3 years ago

as the title suggest, when I am at index i, i already have the information if the num at i is < 0 or > 0. why do we need to check again when we calculate the next index?

A

Anonymous

· 4 years ago

use a hash

A

Anonymous

· 4 years ago

It would be really helpful if code for Alternate Approach that improves algorithm to O(N) was also posted here..

A

Anonymous

· 5 years ago

The test Java code runs, but when I do a walk through of the second array the first do loop and second run of findIndex() on fast results in direction != isForward and should result in false. findNextIndex() should exit with -1 whenever this occurs, but it doesn't here. What am I missing - arr[2] == -1 and arr[0] == 2?

Reading Progress

0%

Vote for new content