Microsoft Interview Question Software Engineer in Tests
#
int FindSortedArrayRotationIterative(int *array, int length)
#
{
#
int start = 0;
#
int end = length-1;
#
if(array[start] < array [end])
#
return start;
#
while(start != end)
#
{
#
int middle = (start+end)/2;
#
if(array[start] < array[middle])
#
start = middle;
#
else
#
end = middle;
#
}
#
return start+1;
#
}
But this algorithm only works if the numbers are unique in the array. The example where the numbers are repeated is actually a O(n) at worst.
This questions was for a contraction position. He wanted me to write a recursive function that will scan both the partitions of the array and would work in O(n) time.
If you have a sorted array as:
1 2 3 4 5 6 7
Now if you rotate it say 3 times it becomes:
5 6 7 1 2 3 4.
So given this array {5,6,7,1,2,3,4} return the number of times this array has been rotated.
This problem is trivial in O(logN) in unique number case but O(n) for repeated numbers.
We can give a general solution which includes for both unique and repeated numbers:
int findNumberOfRotations( int array[], int n)
{
int i;
for(i=0;i<(n-1);i++)
{
if(array[i]>array[i+1))
return i;
}
return 0;
}
This program will work for both the cases and maximum runtine of this is n. It will be lower than in average cases.
Do you agree with it?
Hi Shruthi,
Your solution surely works. The main idea is to find a recursive solution that would run in O(logN) when given unique numbers and switch to O(n) during repeated numbers.
Not sure about Daniel's answer. The spec didn't mention if it is a ascending or descending list, so we should consider both.
The spec didn't mention this list contains unique elements or not, so the return value could be "don't know".
This is a O(n) question to me.
If this case of ascending and descending, Shrthi's solution also may not work as expected.
int FindSortedArrayRotationIterative(int *array, int length)
{
int start = 0;
int end = length-1;
if(array[start] < array [end])
return start;
while(start != end)
{
int middle = (start+end)/2;
if(array[start] < array[middle])
start = middle;
else if(array[start] > array[middle])
end = middle;
else
start++;
}
return start+1;
}
It doesn't Hemant. And you posted the same solution that I did.
Your solution does not account for the case when the two numbers you check are equal. Check for 1 1 1 1 1 1 2 1 1 1.
its working just one correction. What you did wrong is extra pruning.
#include<iostream>
using namespace std;
int FindSortedArrayRotationIterative(int *array, int length);
int main()
{
int arr[]={1,1,1,1,1,1,2,1,1,1};
cout<<FindSortedArrayRotationIterative(arr,10);
}
int FindSortedArrayRotationIterative(int *array, int length)
{
int start = 0;
int end = length-1;
if(array[start] < array [end])
return start;
while(start != end)
{
int middle = (start+end)/2;
if(array[start] < array[middle])
start = middle;
else if(array[start] > array[middle])
end = middle;
else
start++;
}
return start;
}
First of all, It seems that the question was not clear because it was not mentioned whether the list of integers are in sorted order (whether it is ascending or descending), and second is it was not that there are duplicate number(s) in the list... So that we have to assume many cases here to write code.
enum rel {gt,lt,eq} relation, lastRelation;
relation = eq;
do
{
if(arr[i]>arr[i+1])
{ lastRelation = relation;
relation = gt;
}
else if(arr[i]<arr[i+1])
{ lastRelation = relation;
relation = lt;
}
else
continue;
if(relation!= lastRelation && lastRelation != eq)
return i-1;
++i;
}while(i<arrSize);
does divide and conquer help here ? i have implemented it in 'C' . i am not good at recursion. comments are welcome .
#include<stdio.h>
int posit(int[],int,int);
int posit(int in[],int sta,int end)
{
int mid=0;
static int val;
if(sta==end)
{
return val;
}
else
{
mid=(sta+end)/2;
if(in[mid]<in[mid+1] || in[mid]==in[mid+1])
{
posit(in,sta,mid);
posit(in,mid+1,end);
}
else
{
val=mid+1;
}
}
}
void main()
{
int in[]={1,2,1,1,1,1,1};
int i=0,pos=0;
clrscr();
for(i=0;i<7;i++)
printf("%d\t",in[i]);
pos=posit(in,0,6);
printf("\nRotation is %d\n",pos);
getch();
}
int FindMax(int array[],int left,int right){
if (left==right){
return left ;
}
int center=(left+right)/2;
int leftMax=FindMax(array,left,center);
int rightMax=FindMax(array,center+1,right);
if (array[leftMax]>array[rightMax]){
return leftMax;
}
else
{
return rightMax;
}
}
int Max(int array[],int n){
return FindMax(array,0,n-1);
}
#include<stdio.h>
int find_place(int *a,int p,int r)
{
if(p<r)
{
int x,y,q;
q=(p+r)/2;
x=find_place(a,p,q);
y=find_place(a,q+1,r);
if(x==0&&y==0)
{
if(a[q]<=a[q+1])
return 0;
else
return q+1;
}
else
return (x?x:y);
}
return 0;
}
main()
{
int a[10];
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("%d",find_place(a,0,n-1));
}
Since the order asked for is less than O(n), the only option i can think of is binary search which would give us O(logn). Here is the pseudo code.
--> Keep doing binary search till u find the max number in the array.
--> On each iteration of binary search, look at left and right immediate numbers of the number u reach, and do the next iteration 'towards the right if left and right are equal or if right > left' And 'towards the left otherwise'.
--> Keep track of the location of the number u reach on each iteration.
--> Stop when the current number is greater than the left and right
--> subtract the location of the max number in the end, with the length of the array to find the solution.
Assuming the sorting order is ascending and all the values are unique the following can be a solution:
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;
}
}
Here is my code. The problem can be solved recursively.
void FindRotatedElements(int *array,int l_idx,int r_idx,int *rotated_elts)
{
int mid_idx = (l_idx + r_idx)/2;
int num_elts = r_idx - l_idx + 1;
if(num_elts == 1)
return;
if(num_elts == 2)
{
if(array[l_idx] > array[r_idx])
(*rotated_elts)++;
return;
}
if(array[mid_idx + 1] > array[r_idx]) //Right component has rotated elements
{
*rotated_elts += mid_idx + 1; //Everything in left half is rotated
FindRotatedElements(array,mid_idx+1,r_idx,rotated_elts);
}
else //Right is perfectly sorted, left is mixed so find elements on left as long as there is one non-rotated element
{
if(array[mid_idx] > array[mid_idx + 1]) //Left is completely rotated
*rotated_elts += mid_idx + 1;
else
FindRotatedElements(array,l_idx,mid_idx,rotated_elts);
}
}
int FindSortedArrayRotationIterative(int *array, int length) { int start = 0; int end = length-1; if(array[start] < array [end]) return start; while(start != end) { int middle = (start+end)/2; if(array[start] < array[middle]) start = middle; else end = middle; } return start+1;}
- Daniel Johnson February 04, 2009The above code was messed up because of indentation.