Case study: 33 Search rotated sorted array

Sept. 2, 2019

Introduction

I had 10:00 PM mock interview today. I met an engineer and he surprised me with his super good performance. I think that it really makes me grounded, I understand that I have to be humble, and learn from each mock interview as an interviewer.

Case study

I will implement the idea using C# code and share on Leetcode discuss as well.

	'''
	Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
	(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
	You are given a target value to search. If found in the array return its index, otherwise return -1.
	You may assume no duplicate exists in the array.
	Your algorithm's runtime complexity must be in the order of O(log n).
	Example 1:
	Input: nums = [4,5,6,7,0,1,2], target = 0
	Output: 4
	Example 2:
	Input: nums = [4,5,6,7,0,1,2], target = 3
	Output: -1
	'''
	def myfunc(nums,target):
	if not nums: return -1
	pivot = findpivot(nums)
	rval = search(nums[:pivot],target)
	if rval !=-1: return rval
	rval = search(nums[pivot:],target)
	return -1 if rval==-1 else rval+pivot
	def findpivot(nums):
	length = len(nums)
	l,r = 0,length-1
	while (l<=r):
	mid = (l+r)/2
	if mid+1<length and nums[mid]>nums[mid+1]: return mid+1
	elif mid>0 and nums[mid]<nums[mid-1]: return mid
	elif nums[mid]<nums[l]: r=mid-1
	elif nums[mid]>nums[r]: l=mid+1
	else: return 0
	def search(nums,target):
	if not nums: return -1
	l,r = 0,len(nums)-1
	while (l<=r):
	mid = (l+r)/2
	if target>nums[mid]: l=mid+1
	elif target<nums[mid]: r=mid-1
	else: return mid
	return -1
	print myfunc([4,5,6,7,0,1,2],0)
	print myfunc([4,5,6,7,0,1,2],3)
	print myfunc([4,5,6,7,0,1,2],4)
	print myfunc([4,5,6,7,0,1,3],3)
	print myfunc([],3)
	print myfunc([0,1,2,3,4,5,6],3) #[3, 1], target 1
	print myfunc([3,1],1)

view raw SearchRotatedSortedArray.py hosted with ❤ by GitHub

Actionable Items

I should learn from the interviewee. He has over 10 years experience in Silicon Valley. He worked very hard to test the code, go through all possible test cases.

I need to figure out how to motivate myself to test my own code.