amazon set 1 answer

amazon set 1

Q1: a sorted array, left rotation r times, find the r in least possible times.

sol 1. scan the array, find the min—o(n)
sol 2. binary search

int findR( int[] arr, int left, int right )
{
int newLeft = left;
int newRight = right;
int mid = left + ( right – left ) >> 1;

// 4 5 1 2 3
if( arr[mid] < arr[mid-1] && arr[mid] arr[mid-1] && arr[mid] > arr[mid+1] )
{
return arr.length – mid – 1;
}

// 2 3 4 5 1  and 5 1 2 3 4
else if( arr[mid] > arr[mid-1] && arr[mid] < arr[mid+1] )
{
return findR(…..  // basicall don't know how to continue, this is wrong
}

}

=====

int findR( int[] arr, int left, int right )
{
if( right – left {


if( arr[right] >= arr[left] )


{


return right;


}


else


{


return left;


}


}





int mid = left + ( right – left ) >> 2;


// decreasing should happend on the second half


if( arr[mid] > arr[left] )


{


left = mid + 1;


return findR( arr, left, right );


}


else if( arr[mid] > arr[right] )


{


right = mid – 1;


return findR( arr, left, right );


}





return -1;


}

amazon set 1

Q1: a sorted array, left rotation r times, find the r in least possible times.

sol 1. scan the array, find the min—o(n)
sol 2. binary search



int findR( int[] arr, int left, int right )


{


int newLeft = left;


int newRight = right;


int mid = left + ( right - left ) >> 1;





// 4 5 1 2 3


if( arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1] )


{


return arr.length - mid;


}





// 3 4 5 1 2


else if( arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1] )


{


return arr.length - mid - 1;


}





// 2 3 4 5 1  and 5 1 2 3 4


else if( arr[mid] > arr[mid-1] && arr[mid] < arr[mid+1] )


{


return findR(.....  // basicall don't know how to continue, this is wrong


}








}


=====



int findR( int[] arr, int left, int right )


{


if( right - left {


if( arr[right] >= arr[left] )


{


return right;


}


else


{


return left;


}


}





int mid = left + ( right - left ) >> 2;


// decreasing should happend on the second half


if( arr[mid] > arr[left] )


{


left = mid + 1;


return findR( arr, left, right );


}


else if( arr[mid] > arr[right] )


{


right = mid - 1;


return findR( arr, left, right );


}





return -1;


}

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s