Interview Questions And Answers 
-
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 ){
}
5,327 Views |
(11 votes, avg: 3.64)
Loading ...
Answers »
Our Sponsors
Our Sponsors
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.
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
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
C# Prototype
class Ball
{
public enum BallColor { RED, BLUE };
public BallColor Color() { return _color; }
public uint Partition( Ball[] aBalls )
{
int r=0;
int b=aBalls.Length()-1; ////// Sorting in array where red balls come first
while(r
Array before rotating: { 1, 2, 3, 4, 5 }
Array after rotating X=2: { 4, 5, 1, 2, 3 }
All that we have to do is to find a place where an element[i+1] will be greater an element[i].
static int FindSortedArrayRotation(int[] array)
{
for (int i = 0; i array[i + 1])
return i + 1;
}
return 0;
}
Looks like < in comment is considered as a starting HTML tag and my previous post is not shown correctly
Correct code:
static int FindSortedArrayRotation(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
if (array[i] > array[i + 1])
return i + 1;
}
return 0;
}
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]<array[end-1]) return 0; 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 algorithms.
int FindSortedArrayRotation( int array[], unsigned length )
{
int min=array[0];
int j=1;
int index=0;
while(jarray[j])
{
min=array[j];
index=j;
}
j++;
}
return index
}
Java version of David’s basic alg:
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);
}
}
ooops wrong formatting.. here again:
Amitabh Gupta
Amitabh Gupta
1
0
2008-01-20T23:30:00Z
2008-01-20T23:30:00Z
1
102
585
ag
4
1
686
11.5606
false
false
false
MicrosoftInternetExplorer4
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:”Table Normal”;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:”";
mso-padding-alt:0in 5.4pt 0in 5.4pt;
mso-para-margin:0in;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:”Times New Roman”;
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
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[end])
return 0;
if ((end -
begin) == 1)
return end;
int mid =
(begin + end)/2;
if (arr[begin]
> arr [mid])
return
findRotation(arr,begin, mid);
return
findRotation(arr, mid, end);
}
}
ok, this time :
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);
}
}
The smallest and easiest solution…
i=0;
while(a[i]>a[i+1])
{
i++;
}
The following code uses the divide and conquer approach but in an iterative way similar to binary search. In this algo we end up at the last element which has the index equal to “start” hence the result will be start+1. Initially I have checked that the last element cannot be at length-1 index hence no overflow error.
int findRotation(array,length){
start=0;
end=length-1;
if(array[start]
-lt = lessthan
int findRotation(array,length){
start=0;
end=length-1;
if(array[start] -lt array[end])
return start;
while(start!=end){
middle=(start+end)/2;
if(array[start] -lt array[middle])
start=middle;
else
end=middle;
}
return start+1;
}
int findRotation(array,length){ start=0; end=length-1; if(array[start]1. Find the index of the min element from the array O(n) time
2. if index found is zero then this is not at all rotated
3. if index is not zero then subract index from len+1 and it will give u the rotation amount.
public static int findRotation(int[] arr)
{
for (int i = 0; i arr[i + 1])
return i + 1;
}
return 0;
}
Leave an Answer/Comment