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.
Answer

Interview Answer

3 Answers

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] > a[i + 1] ==> 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.