Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Binary search as it is will not work here. You need to tweak it a bit as the array is rotated.
Yeah Vijay, I agree with your answer. What I wanted to convey at that time was that the idea is similar to binary search.
It was intuitive obviously due to the 'sorted' array.
The following Algorithm (as explained in the program)
For further queries:- comment plz
#include<stdio.h>
/*
*A[] is the array in which we have to search
*no is the number to be searched
*start is the starting index to search in the array
*end is th terminating index to search in the array
*/
int indexSearch(int A[], int no, int start, int end)
{
/*similar to binary search we have to compare with the middle element*/
int mid=(start+end)/2 ;
// printf("Start = %d End = %d \n",start,end);
/* Base Case if not found, or originally the limits were inserted in wrong order*/
if(start>end)
return -1;
/*If the middle element matches the number, we are done, base case if found*/
if(no==A[mid])
return mid;
else
/*If the middle element is smaller then number, the answer may be in right or left*/
if(no>A[mid])
{
/*if the number is smaller then the rightmost end then recursively search for the number in the right sided array*/
if(no<=A[end])
return indexSearch(A,no, mid+1,end);
/*otherwise recursively search in the left side*/
return indexSearch(A,no, start,mid-1);
}
else
/*If the middle element is greater then number, the answer may be in right or left*/
if(no<A[mid])
{
/*if the number is greater then the leftmost end then recursively search for the number in the left sided array*/
if(no>=A[start])
return indexSearch(A,no,start,mid-1);
/*otherwise recursively search in the right side*/
return indexSearch(A,no,mid+1,end);
}
}
int main()
{
int A[]={7,-1,6};
int toSearch=6;
int start=0;
int end=sizeof(A)/sizeof(A[0])-1;
int index;
index=indexSearch(A,toSearch,start,end);
printf("%d is at index %d\n",toSearch,index);
}
As we hv rotated array (consider it as s1=xy).....first create s2=s1s1(by concatation(if space is not problem))......then apply binary search..........
s2-->678123456712345
like search for 4 (4<5)
left half-->67812345
(4>1)
right half-->2345
then u got again right half finally 4......(time compO(logn) ..and space compO(n))
45
input - 67812345
check for the min number in the array, capture the location and also note the last digit in the array eg. A[n] =5 or A[7]=5 .
Now if the element to search is 4, then check with last digit and set the array value to 3 i.e A[3] or min value position. else
if the element to search is 7, then check with last digit check and set the array value to 0 i.e A[0].
write the code for binary search,
let left = index of smallest element
right = index of largest element + n.
replace all the places where you are using array index, say m with m%n,
where n = number of elements.
you're done.
#include<stdio.h>
void intput(int *a, int n)
{
int i;
for(i=0; i<n; i++)
scanf("%d", &a[i]);
}
void print(int *a, int n)
{
int i;
printf("\nThe elements in the array are:\n");
for(i=0; i<n; i++)
printf("%d\t", a[i]);
}
int search(int *a, int lb, int ub, int data)
{
int mid;
if(lb>ub)
return 0;
mid = (lb+ub)/2;
if(a[mid] == data)
return mid;
else if(a[lb]<=a[mid])
{
if( (a[lb]<=data) && (data<a[mid]) )
search(a, lb, mid-1, data);
else
search(a, mid+1, ub, data);
}
else
{
if( (a[mid]<data) && (data<=a[ub]) )
search(a, mid+1, ub, data);
else
search(a, lb, mid-1, data);
}
}
int main()
{
int n, s, indx, *arr;
printf("Enter the size of array. ");
scanf("%d", &n);
arr = (int*)malloc(n*sizeof(int));
intput(arr, n);
print(arr, n);
printf("\nEnter the element to search. ");
scanf("%d", &s);
indx = search(arr, 0, n, s);// Time Complexity = O(log n)
if(indx)
printf("\nThe element is found at location: %d.", indx);
else
printf("\nThe element is not found.");
return 0;
}
Goal: to preserve O(log n) running time for searching an element in a rotated array.
If we somehow figure out by how many indexes has the array been rotated then we can use a slightly modified version of binary search:
The real trick is to come up with an algo to search for the amount of rotation with a running time not worse than O(log n). This will result in a total complexity ( find the amount of rotation + search) of 2*O(log n) which is in-fact just O(log n).
The algo to search for the amount of rotation is quite similar to binary search. Here's the code:
- Vivek Thakyal March 29, 2012