We’ve a solution for following frequently asked interview question. Here’s problem statement “Implement the following function, RotateArray, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength - 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. RotateArray discovers and returns X by examining the array. You should be able to do this in less than linear time."
Signature of method would be:
public int[] RotateArray(int[] a, int X); |
Here’s implementation:
/// <summary> /// Rotates sorted array. /// </summary> /// <param name="a">integer array</param> /// <param name="X">rotation index</param> /// <returns></returns> public int[] RotateArray(int[] a, int X) { int[] output = new int[a.Length]; int j; for (int i = 0; i < a.Length; i++) { j = (i + X) % a.Length; if (j < 0) { j += a.Length; } output[j] = a[i]; } return output; } |
Testing this method:
static void Main(string[] args) { int[] a = RotateArray(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, 3); foreach (int i in a) { Console.Write(i + " "); } } |
OUTPUT:
7 8 9 1 2 3 4 5 6 //input: 1 2 3 4 5 6 7 8 9 |
January 26th, 2010 at 2:34 pm
More Efficient Algorithms for this:
Input: 1 2 3 4 5 6 7 8 9 (arr)
Output: 7 8 9 1 2 3 4 5 6
rotate by: 6 (n)
public int[] RotateArray(int[] arr, int X)
{
Reverse(arr, 0, n);
Reverse(arr, n+1, arr.Length-1);
Reverse(arr, 0, arr.Length-1);
return arr;
}
//Implement the method to reverse the array
public int[] Reverse(int[] a, int lower, int upper)
{
for(int i= lower; i<upper; i++;upper–)
{
int temp = a[i];
a[i] = a[upper];
a[upper] = temp;
return a;
}
}