Grokking Oracle Coding Interview

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
O

Or

· 4 years ago

״However, if there are duplicates, it is not always possible to know which part is sorted. We will look into this case in the ‘Similar Problems’ section.״

But there is no such section.

Show 1 reply
M

Mike Xu

· 4 years ago

In the similar problem, why is it that "the best we can do is to skip one number from both ends"?

Thanks

Show 2 replies
Santha Kumar Ramaiyan

Santha Kumar Ramaiyan

· 2 years ago

The problem statement should say the solution should be in the order of log(n). Otherwise, it is a very trivial problem since we can just find the index of the key in the input array and return which just takes o(n).

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago



class Solution:
  def search(self, arr, key):
    # standard binary search 
    def binary_search(b, e):
      while b <= e:
        m = (b + e) // 2
        if arr[m] == key:
          return m 
        elif arr[m] < key:
          b = m + 1
        else:
          e = m - 1
      return -1

    '''
      original array 
      1 2 3 4 5 6 7 8 9 10 11 12

      case: 1 b < m > e
      4 5 6 7 8 9 10 11 12 1 2 3
      ^           ^            ^
      b           m            e
      if key in the sorted range 
          do binary search 
      else:
          discard the sorted side
          
      case 2:  b > m < e
      10 11 12 1 2 3 4 5 6 7 8 9
      ^          ^             ^
      b          m             e
      if key in the sorted range 
          do binary search
Show 1 reply