|
|
Implement the following function, FindSortedArrayRotation.....
Microsoft Interview Questions and Answers
(Continued from previous question...)
13. Implement the following function, FindSortedArrayRotation.....
Question:
Implement the following function, FindSortedArrayRotation,
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]. FindSortedArrayRotation discovers and returns X by examining the array.
Consider performance, memory utilization and code clarity and elegance
of the solution when implementing the function.
C++ Prototype
int FindSortedArrayRotation( int
array[], unsigned length )
{
}
C# Prototype
static int FindSortedArrayRotation(
int[] array )
{
}
maybe an answer:
answer1:
scan the array, comparing every element with its pr eceding element to verify that it is greater than the preceding element.Increment a count variable.
scan until you find a number which is smaller than its preceding number.break from the loop.Count variable gives you the rotation amount.
Will post the code soon.
answer2:
using System;
using System.Collections.Generic;
using System.Text;
namespace raj
{
public class parent
{
int FindSortedArrayRotation(int[] rotatedarray, int[] array)
{
int i=0,j=0,count=0;
while (j array[i + 1])
{
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
last_exchange = i;
}
}
right_border = last_exchange;
}
while (right_border > 0);
Console.WriteLine(”sorted array is: “);
for (int i = 0; i
answer2:
using System;
using System.Collections.Generic;
using System.Text;
namespace raj
{
public class parent
{
int FindSortedArrayRotation(int[] rotatedarray, int[] array)
{
int i=0,j=0,count=0;
while (j array[i + 1])
{
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
last_exchange = i;
}
}
right_border = last_exchange;
}
while (right_border > 0);
Console.WriteLine(”sorted array is: “);
for (int i = 0; i
answer3:
While I agree that these solutions are correct, I think a much faster running time exists by taking advantage of the fact that the numbers were at one point in time sorted. The proposed solutions above all run by scanning through the array and finding the first unsorted element. Let N = length of array. In the worst case (X=0) it would make N compares to come to this conclusion. We’re all imagining solutions to an array of length 10 or less, but this could very well be used to find the solution a array with length 100 million.
The above solutions are fine, but I think a Divide and Conquer solution is better. We can take advantage of the fact that the array is actually made up of two subsets sorted in ascending order. This means that if we take any two numbers in the list, say the first and the last, if the first is greater than the second then we know the point of discontinuity (the point that divides the two subsets) is between those two numbers. Otherwise, that subset is sorted. We can use this to divide and conquer and reduce the running time from O(n) to O(lgn).
I’ll give an example…
Consider the following array…
9 10 1 2 3 4 5 6 7 8
Compare the first number to the last to determine if the list is already sorted (that is, if X=0)
9x is always false.
So… on to the code! Here is the solution by itself:
int FindSortedAmount(int array[],unsigned begin, unsigned end)
{
if(begin>=(end-1) || array[begin]
int middle=(end+begin)/2;
int sol = FindSortedAmount(array,begin, middle);
if(sol>0) return sol;
sol = FindSortedAmount(array,middle,end);
if(sol>0) return sol;
return middle;
}
int FindSortedArrayRotation( int array[], unsigned length )
{
return FindSortedAmount(array,0,length);
}
You can use the following code to test it…
#include >stdlib.h>
#include >stdio.h>
#define LENGTH 1000000
int main(){
int array[LENGTH];
array[0]=2;
for(int i=1;i<LENGTH-1;i++){
array[i]=array[i-1]+rand()%50+1;
}
array[LENGTH-1]=1;
int x = FindSortedArrayRotation(array,LENGTH);
printf("Solution: %dn",x);
}
Its important to note that this is an asymptotically better performing solution. For very large cases it will perform on average way better than the other solutions. However, for length 10 it actually requires the same or more comparisons to find the answer. But for an array of length 1000000 with a solution of 999999, it takes 81 comparisons as opposed to 999999 needed by the above algorithm
answer4:
public class NumArray {
int cnt=0;
public static void main(String[] args) {
NumArray num = new NumArray();
int[] arr = { 5,6,7,8,1,2,3,4 };
int r= num.findRotation(arr, 0, arr.length-1);
System.out.println(”Rot=” + r + “, iter=” + num.cnt);
}
private int findRotation(int[] arr, int begin, int end) {
cnt++;
if (arr[begin] arr [mid])
return findRotation(arr,begin, mid);
return findRotation(arr, mid, end);
}
}
answer5:
public class NumArray {
int cnt=0;
public static void main(String[] args) {
NumArray num = new NumArray();
int[] arr = { 5,6,7,8,1,2,3,4 };
int r= num.findRotation(arr, 0, arr.length-1);
System.out.println(”Rot=” + r + “, iter=” + num.cnt);
}
private int findRotation(int[] arr, int begin, int end) {
cnt++;
if (arr[begin] &lb; arr[end])
return 0;
if ((end - begin) == 1)
return end;
int mid = (begin + end)/2;
if (arr[begin] &lb; arr [mid])
return findRotation(arr,begin, mid);
return findRotation(arr, mid, end);
}
}
(Continued on next question...)
Other Interview Questions
|
