Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 3: Rotation Count

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

    lo = 0
    hi = len(arr) - 1
    while lo <= hi:
      mid = (lo + hi) // 2
      if mid > 0 and arr[mid-1] > arr[mid]:
        return mid

      if arr[0] < arr[mid]:
        lo = mid + 1
      else:
        hi = mid - 1
    
    return len(arr) - 1 - mid
A

Anonymous

· 2 years ago

class Solution:
  def countRotations(self, arr):
    length = len(arr) - 1
    b, e = 0, length
    m = (b + e) // 2 
    
    # edge case: if the array is fully reversed like [5, 4, 3, 2, 1]
    if arr[b] > arr[m] > arr[e]:
      return length     

    while b <= e:
      m = (b + e) // 2    

      # check and discard the first half 
      if arr[b] <= arr[m]:
        # before [b = m + 1] check if we have found the index 
        if m < length and arr[m] > arr[m + 1]:
          return m + 1
        # nothing found just discard 
        b = m + 1
      
      # check and discard the the second half  
      elif arr[m] <= arr[e]:
        # before [e = m - 1] check if we have found the index 
        if m - 1 >= 0 and arr[m - 1] > arr[m]:
          return m
        # nothing
A

Anonymous

· 3 years ago

The stated algorithm provides 3 as the rotation count instead of 5.

A

Anonymous

· 3 years ago

The problem states that we can assume the array has no duplicates. However, one of the test cases is [10, 20, 30, 10, 20]. Elements 10 and 20 are duplicates... Was it a mistake to have those test cases in there?

A

Anonymous

· 4 years ago

For the similar problem, we never checked the 'end' value for the original solution. so why should we check for that in the similar problem?

Show 4 replies
A

Anonymous

· 4 years ago

I always find my solutions look quite different in terms of internal comparisons than the solution... is that OK?

def solve(arr): start, end = 0, len(arr) - 1 if arr[start] < arr[end]: return 0 while start

Reading Progress

0%

Vote for new content