Microsoft Interview Question
Software Engineer / DevelopersJoe's answer is right.
Only thing is what if array is not rotated at all or array rotated million time (the lenght of array).
Need to put one more condition:
if go through whole array, and can not find previous element greater than the current then starting point is first element in array.
"million" number is just to make thing little challanging.
The condition can be improved. Just check whether first element is larger than the last. If not then the first element is the answer.
You guys are missing something. What if the array elements are allowed to repeat?
For instance the array was 0,0,0.....,0, 1 and then rotated by unknown quantity. How do you find out where the rotation starts in O(logn) time?
In case the elements are known to be unique, then an O(logn) solution exists as pointed out by "yeah".
Can be done in O(log n).
int findstart(int *a,int beg,int end)
{
int mid=(beg+end)/2;
if(beg==mid)
return end;
else if(a[beg]>a[mid])
return findstart(a,beg,mid);
else if(a[mid]>a[end])
return findstart(a,mid,end);
else if(a[beg]==a[mid] && a[mid]==a[end]) // if all 3 are same for cases like
{ // 9 9 9 1 9
if(findstart(a,beg,mid)==a[beg]) // if the starting point returned is same
return findstart(a,mid,end); // as a[beg] i.e the equal value as '9' in
// the above case move to the other half
else
return findstart(a,beg,mid); // if the other half also returns the same
} // value then array contains only 1 unique
} // element
Sample
Initial - 1 1 3 4 4 6 7
Rotated - 6 7 1 1 3 4 4
b m e
b m e
b m e
'b'e
'm'
Initial - 0 1 6 6 6 6 6
Rotated - 6 6 6 6 0 1 6
b m e
s
b m e
'b'e
'm'
Here in both cases b==m at last step and the value end is the index. It is to be noted that whatever the input is the algorithm takes log(n) time.
The code works for cases like 9 9 9 9 0 0 5 also and 9 9 9 9 0 1 9 or even all elements same value.
But for worst case and best case it takes O(logn). And it does take care of repetiton too.
it does work!!
if '1' is mid it returns by normal condition since a[beg]>a[mid]
so assuming in the case u r stating '1' is not the mid element.. which means the '1' has to lie on one of the sides of the mid. so as per the code that part of the array is recursively checked for the index. at the final step it'd return the index.
No it does not.
You check for a[beg] == a[mid] will return end. There won't be any recursion...
int FindPointOfRotation(int a[], int len)
{
if(!a || (len < 0))
return -9999;
if(len == 1)
return 0;
int low = 0; int high = len - 1;
while(low < high)
{
int mid = (low + high) / 2;
if(a[mid] <= a[high])
{
if((mid == 0) || (a[mid - 1] > a[mid]))
return mid;
else
high = mid - 1;
}
else
{
if(a[mid + 1] < a[mid])
return mid + 1;
else
low = mid + 1;
}
}
return 0;
}
Here is another one:
int findRotation(int *array, int length)
{
if (!length || 1 == length) return 0;
int start = 0;
int end = length - 1;
if (array[start] < array[end])
return 0;
int middle;
while (start != end)
{
middle = (start + end) / 2;
if (array[start] > array[middle])
{
if (array[middle + 1] > array[end])
start = middle + 1;
else if (array[middle] > array[middle + 1])
return middle + 1;
else
end = middle;
}
else
return middle + 1;
}
}
Can be done in O(log n).
- yeah December 01, 2008int find_index(int *a,int start,int end)
{
int index=(start+end)/2;
if(a[start]<a[index]<a[end])
return start;
else if(a[start]>a[index])
return find_index(a,start,index);
else if(a[index]>a[end])
return find_index(a,index,end);
}
But I don't understand the use of 'million' numbers here.
Can somebody explain me what all should we look for in general when questions involving large arrays are given.