Microsoft Interview Question: If a sorted array is rotated,... | Glassdoor

## Interview Question

Software Development Engineer Intern Interview Redmond, WA

# If a sorted array is rotated, how to find how many times it

has been rotated.

1

Two steps

1- comparing 1st two elements you can probably say if it's ascending or descending. Or you could ask your interviewer.
2. Once you know the sorting order you can use below logic
public int HowManyRotation(int input)
{
countRotation = 0;

for(int i = 0; i ascending order. reverse this for desceding order
{
countRotation = countRotation + 1;
}
if(a[i] &gt; a[i + 1] ==&gt; id change in sorting. reverse this for descending order.
{
countRotation = countRoration + 1;
break;
}
}
}
}

return countRotation;
}

Praveen Chettypally on Jan 25, 2011
0

Suppose there is sorted array
i/p: 1234, Rotation: 3412, o/p: 2 time rotation.

{
A =new Array('1,2,3,4');
B=new Array('3,4,1,2');
int i=A[1];
int index=indexof(A[i],B); ------- --- - - - - - - - -- - - - - -- just find the location of '1' from A, in array B

return index-1; - - - - - -- - - index=3 and so, return will 3-1=2. 2 rotations

}

Vidhi on Sep 24, 2015
0

This is a very interesting question that has been asked so many times. I found a very insightful post about it here: https://goo.gl/CBXmkS

charles on Jan 13, 2017