Expedia Interview Question
Software Engineer / DevelopersPseodocode:array index starts from 0,1,...
------------------------------------------------------------
p=given number to find
N=size of array
k=index of smallest element //amount of rotation in O(N) time
l=left index=k
r=right index = (k-1+N)%N
l1=transform(l)=(l-k+N)%N
r1=transform(r)=(r-k+N)%N
while(l1<=r1)
{
mid1=(l1+r1)/2
mid=inverseTransform(mid1)=(mid+k)%N
if(p== [mid]) break
//p occurs at index mid. [mid] indicates value at index=mid
if(p> [mid])
{
l1=mid1+1
}
else
{
r1=mid1-1
}
}
//code to check if p doesn't exist in array
-----------------------------------------------------
Note: variables l,r,mid indicates the indices of the given array
and variable l1,r1,mid1 are indices if the array would have not
been rotated,i.e. the lowest index (zero) contains smallest element
Binary search with some extra conditions will be the way to find the element in log n time.
n= total size
Find(a,low,high,i,val)
{
if a[i]>a[(i+1)%n]
Left Rotation with i=n-i;
else if a[i]<a[i+1]
Right Rotation with i=i;
else if a[i]=a[i+1]
return Find(a,low,high,i-1);
mid= ((low+high)/2 + i)%n;
low = (low+i)%n;
high = (high+i)%n;
if(val < a[mid])
return ((low==(mid-1+n)%n) ? -1: Find(low, (mid-1+n)%n));
else if(val > a[mid])
return (((mid+1)%n==high)?-1:Find((mid+1)%n,high));
else if(val == a[mid])
return mid;
}
Please comment. Didnt tested thorougly
The amount "i" rotated, can be found in o(n) time. After finding "i", standard binary search can be applied with an additional mapping to the index. Index k has to mapped to (k-i+n)%n before indexing the array
- Anonymous December 13, 2006