## Amazon Interview Question for Software Engineer / Developers

• 1
of 1 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

//
int countrot(int a[], int low, int high)
{
int mid = (low+high)/2;

if (a[mid] > a[low]) {
return countrot(a, mid, high);
}
if (a[mid] < a[high]) {
return countrot(a, low, mid);
}
if (a[mid] > a[mid+1]) {
return (mid+1);
}
return 0;
}//

Comment hidden because of low score. Click to expand.
0
of 0 vote

//
int countrot(int a[], int low, int high)
{
int mid = (low+high)/2;

if (a[mid] > a[low]) {
return countrot(a, mid, high);
}
if (a[mid] < a[high]) {
return countrot(a, low, mid);
}
if (a[mid] > a[mid+1]) {
return (mid+1);
}
return 0;
}//

Comment hidden because of low score. Click to expand.
0
of 0 vote

As the array currently is not sorted ,a direct Binary search will not give us the desired result. we know that sorted array is rotated based on a position of a element
1234567 after rotation on 3 becomes 3456712 . we calculate the distance from mid element to the rotation element , in our case its 1(Let it be X) .
so after rotation we increment/decrement by X to get the pivot element , form a binary tree from by choosing this element as pivot element.
Then we can search any node Log(n) order.

Comment hidden because of low score. Click to expand.
0

can u please elaborate it, especially "we calculate the distance from mid element to the rotation element , in our case its 1(Let it be X)." part.
thnq...

Comment hidden because of low score. Click to expand.
0

"we calculate the distance from mid element to the rotation element , in our case its 1(Let it be X)." - In this step how can you be sure that the complexity remains O(log n)?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Let len be the length of the array. When array is rotated at position n the resulting elements ar[0..(len-n)] and ar[(len-n)..len] are still sorted. Do a binary search among these sorted arrays to find the element.

Comment hidden because of low score. Click to expand.
0

Do we know 'n'? (The position at which the array is rotated)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void searchRotate()
{
int a[]={6,7,8,1,2,3,4,5};
int lt=0,rt=a.length-1,mid=0;
int find = 3;
boolean found =false;
while(lt<=rt)
{
mid = (lt+rt)/2;
if(a[mid] == find)
{
System.out.println("Found at index:"+mid);
found =true;
break;
}
if(a[mid] <= a[rt])
{
if(find>a[mid] && find<=a[rt])
{
lt = mid+1;
} else {
rt = mid -1;
}
} else if(a[lt] <= a[mid] )
{
if(find>a[lt] && find <=a[mid])
{
rt = mid -1;
} else {
lt = mid +1;
}
}
}
if(!found)
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do two binary searches. One to find the smallest element in the array, that is the actual starting point of the sorted array. Second to find the element that is required. Two binary searches is lg n + lg n = lg n

Comment hidden because of low score. Click to expand.
0
of 0 vote

As per "ap on January 19, 2011"

``````/**
* * @author hmm :  To find the rotation point in O(log n)
*
*/
public class Main {

public static int array[]={6,7,8,9,10,1,2,3,4,5};
public static void main(String[] args)
{
int low = 0;
int high = array.length;
int mid = 0;

while(low<high)
{
System.out.println("low = "+low +" high " + high);

mid = (low + high)/2;
if(array[mid] > array[low])
//Turning point is towards the left
low=mid;
else
//Turning point is towards the right
high=mid;

}

System.out.println("Rotated around "+ array[low]);
/* Binary Search */
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

First- for "ap on January 19, 2011"
You can't find the smallest in a cyclically sorted array in Binary search
Consider {20, 50, 2, 4, 7, 9, 11, 19}
half-point is {4} and then {50} and then what- {20}?

Second- for everyone
Is this solution O(lg n) ?
findOffset(array A)
//Recursive stops
if A's size equals 1 return 0
if A's size equals 2 return 0 if A[0]<A[1] and 1 otherwise

set rightSideVal = findOffset(right side of A)
//if the right size is cyclic then all the left side is part of that shift
if rightSideVal > 0 then rightSideVal += A's size / 2
return findOffset(left half of A) + rightSideVal

Comment hidden because of low score. Click to expand.
0
of 0 vote

For solving the above algorithm we will need to use the binary search in the sorted and rotated array we will first find the mid using (high + low) / 2 and we will check for the condition that the mid element must be greater then the lower index element and then, if yes we will again check for the element being between the low and the mid index if found then traverse the low to mid - 1 else we will traverse the mid + 1 to high subarray, and the next condition will be the opposite of the first.

Implementation:

``````int findlement(int arr[], int low, int high, int key){
if(low > high)
return -1;
int mid = (high + low) / 2;
if(arr[mid] == key)
return mid;
if(arr[mid] > arr[low]){
if(key >= arr[low] && key <= arr[mid])
return findelement(arr, low , mid - 1, key);
return findelement(arr, mid + 1, high, key);
}
if(arr[mid] >= key && key <= arr[high])
return findelement(arr, mid + 1, high, key);
return findelement(arr, low , mid - 1, key);
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.