Microsoft

www.microsoft.com

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

1 Answer

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 < arraylength - 1 ; i++)
{
if(a[i] < a[i+1] ) ==> 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.