Amazon Interview Question for SDE-2s


Team: Bangalore
Country: India
Interview Type: In-Person




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

It doesn't seem possible to search the element in o(logn) without calculating the pivot
suppose case 1: arr[]={1,2,3,22,23,25,30,27,21,11,10}
case 2: arr[]={1,2,3,21,23,25,30,27,22,11,10}
and suppose key is 22
in both the arrays middle element is 25,and arr[low]=1,arr[high]=10,arr[mid-1]=23,arr[mid+1]=30.
so,it seems impossible to decide whether to look in left subarray or right..In 1st example 22 lies in left subarray while in 2nd it lies in right subarray. Correct me if I am wrong

- Amit July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is possible! You need to apply binary search twice in that case. See my algorithm below.

- Murali Mohan July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@avahuasca-if you search in both the subarrays for many cases,its o(n) not o(logn).
binary search is O(logn) search because in each iteration if reduce length by half.

will you say the following prog is also o(logn)?
int search(int a[],int low,int high,int key)
{
if(high<=low)
return 0;
int mid=(low+high)/2;
if(a[mid]==key)
return mid;
return search(a,low,mid-1,key) || search(a,mid+1,high,key);
}
no this is o(n) only..correct me if I am wrong

- Amit July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@amit

You are right! My solution below does not work - I missed thinking about some fundamental use-cases before proposing a solution. Sorry about that!

- Murali Mohan July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I believe time complexity of Amit's Solution is O(logn/2) + O(logn/2) not O(n) as binary search is performed on half of original array 2 times.

int search(int a[],int low,int high,int key)
{
if(high<=low)
return 0;
int mid=(low+high)/2;
if(a[mid]==key)
return mid;
return search(a,low,mid-1,key) || search(a,mid+1,high,key);
}

- Anonymous July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anonymous--this is normal search(although not linear),not binary search..you may try in an unsorted array

- Amit July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Optimization:

int search(int a[],int low,int high,int key)
{
if(high<=low)
return 0;
int mid=(low+high)/2;
if(a[mid]==key)
return mid;

	if((a[mid]<a[high]) && key > a[mid])// in this case 
	//our pivot and key will always occur after  a[mid] 
	//searching in left subArray is waste
	return search(a,mid+1,high,key);

	if((a[mid]<a[high]) && key < a[mid])// in this case 
	//our pivot will always occur after  a[mid] 
	//key will occur before a[mid]
	//a[low] to a[mid] is just increasing subArray
	return search(a,low,mid-1,key);

return search(a,low,mid-1,key) || search(a,mid+1,high,key);
}

- PKT July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

same as two more cases:

if((a[mid]<a[low]) && key > a[mid])// in this case
//our pivot and key will always occur before a[mid]
//searching in right subArray is waste
return search(a,low.mid,key);

if((a[mid]<a[low]) && key < a[mid])// in this case
//our pivot will always occur before a[mid]
//key will occur after a[mid]
//a[mid] to a[high] is uniform decreasing order

- PKT July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Regarding complexity even in worst case we are not touching all elements n...... 
As we are using binary search two times it looks like complexity is:

O(log [n / constant1] ) + O(log [n / constant2] )

in case pure increasing or decreasing order array
 	O(log n)

in all other cases:
O(log [n / constant1] ) + O(log [n / constant2] )
	where
 	constant1 = 2+ {2,3,4....}
 	constant2 = 2+ {2,3,4....}

- PKT July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

find (a,l,u,n)
{
if(l>=u)
return 0;
else
i=(l+u)/2;
if(a[i]==n)
return i;
else if(a[i-1]<n&&a[i]>a[i-1])
find(a,i+1,u);
else if(a[i+1]<n&&a[i]>a[i+1]
find(a,l,i-1);
else
{
find(a,l,i-1);
find(a,i+1,u);
}

- Anonymous July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

let us consider the reading as reading of some curve.. according to the given data first part has +ve slop and second part has negative slop.(i.e a[i+1]-a[i] is +ve for first half and -ve for second half) to find the pivot in log(n) complexity first consider start_point and end_point element then find mid_point (start_point+end_point)/2 find its slop if it is +ve replace start_point with mid element if -ve replace end_point with mid_point repeat the procedure updating start_point and end_point finally you end up with a pivot point(with log(n) complexity). once pivot is found perform binary search again worst case complexity is log(n). overall complexity is 2log(n) or O(log(n))

- Anonymous July 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question clearly says NOT to use the pivot element.

- Murali Mohan July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

k... i thought without using previously found pivot...

- Anonymous July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

by making some modification in above method we can search for an element. that is once the slop of mid_point is checked if that is + ve check whether key is between start_point and mid_point if it is in between then key found if not we found that key is not in increasing part... it should be in decreasing part... same applies for decreasing part also... once the key not found we can repeat the dividing part till we get the key in between other part of the list... the complexity is still O(log(n))...

- Anonymous July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can try with this one.
1) First check the element that joins both increasing and decreasing array using binary search(logn).
2) then search the key in the left subarray using binary search(logn).
3) If it is not present in left subarray, search it in right subarray using binary search(logn).
We will have to use different methods for these operations.
Correct me if I am wrong.

- tln July 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We need to determine the inversion first ...
This can be done in o(log n) and decide from there which side array we must search.


Eg. {1,7,10,12,25,30,27,20)

The inversion is 30,27 position is 5 . It can be found in O(log(n))
Do a binary search (which has conditions reversed ) on the right side to determine the position of the key O(log(n))
if not found
Do a binary search on the left side of the key to determine the position of the key O(log(n)).

Pivot is different from locating inversion. I think , please correct me if i m wrong

- pras July 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

en. wikipedia. org/ wiki/ Ternary_search

Hope you guys will find this new algorithm coooool :)

- YeJu July 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static bool searchElement(int[] array, int first, int end, int start, int finish, int element)
{
if (first <= end)
{
int mid = (first + end) / 2;
int midright = mid + 1;
int midleft = mid - 1;
if (midleft < first)
midleft = first;
if (midright > end)
midright = end;

if (array[midleft] <= array[mid] && array[mid] <= array[midright])
{
if (element < array[mid])
{
if (mid - 1 >= first)

return searchElement(array, first, mid - 1, start, finish, element);
else
return searchElement(array, (start + finish) / 2, finish, (start + finish) / 2, finish, element);

}
else
{
if (element > array[mid])
{
if (mid + 1 <= end)
return searchElement(array, mid + 1, end, start, finish, element);
else
return searchElement(array, (start + finish) / 2, finish, (start + finish) / 2, finish, element);
}
else
{
if (array[mid] == element)
return true;
else
return false;
}
}
}
else
{
if (array[midleft] >= array[mid] && array[mid] >= array[midright])
{
if (element < array[mid])
{
if (mid + 1 <= end)
return searchElement(array, mid + 1, end, start, finish, element);
else
return searchElement(array, start, (start + finish) / 2, start, (start + finish) / 2, element);
}
else
{
if (element > array[mid])
{
if (mid - 1 >= first)
return searchElement(array, start, mid - 1, start, finish, element);
else
return searchElement(array, start, (start + finish) / 2, start, (start + finish) / 2, element);
}
else
{
if (array[mid] == element)
return true;
else
return false;
}
}
}
else
{
if (element == array[mid])
return true;
else
return (searchElement(array, first, mid - 1, start, finish, element) ||
searchElement(array,mid+1,end,start,finish,element));

}
}
}

return false;
}

- Anonymous December 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.io.*;

public class RotatedArray {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        for(int i = 0; i < N; ++i)
            A[i] = Integer.parseInt(br.readLine());

        int K = Integer.parseInt(br.readLine());

        int start = 0;
        int end = N-1;

        while(start <= end) {
            int mid = start+(end-start)/2;

            if(A[mid] == K) {
                System.out.println(mid);
                break;
            }
            else {
                if(A[end] < A[mid]) {
                    if(K < A[mid]) {
                        start = mid+1;
                    }
                    else {
                        end = mid-1;
                    }
                }
                else if(A[end] > A[mid]) {
                    if(K < A[mid]) {
                        end = mid-1;
                    }
                    else if(K > A[mid]) {
                        start = mid+1;
                    }
                }
                else {
                    System.out.println(-1);
                    break;
                }
            }
        }

        System.exit(0);
    }
}

- Srikant Aggarwal July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Found my mistake sorry....

- srikantaggarwal July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int findindex(int arr[],int size,int key)
{
int i;
int num=size/4;
for(i=0;i<num;i++)
{
if(arr[i]==key)
printf("%d",i);

}

}

- manish27.p July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@Srikant: It's not a rotated sorted array.

- sayannayak July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think we just need to find the key is in an increasing pattern or decreasing pattern and then apply binary search on it.

- Sibendu Dey July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static int getKeyIndex(int[] A, int p, int r, int key) 
	{
		// invalid input indices, return -1
		if (p > r)
			return -1;
		// if array if only one entry, if equals to key return index else return -1;
		if (p == r) 
		{
			if (A[p] == key)
				return p;
			else
				return -1;
		}
			
		// if array has only two entries, if either of indices value equals key return index, else -1
		if (p+1 == r)
		{
			if (A[p] == key || A[r] == key)
			{
				if (A[p] == key)
					return p;
				else
					return r;
			}
			else
				return -1;
		}
		
		// get middle index
		int mid = (p + r)/2;
		// if value at mid index, return mid
		if (A[mid] == key)
			return mid;
		
		//checking for increasing sequence, that is A[mid-1] < A[mid] < A[mid+1] and key less than A[mid]
		// search for key left part
		else if (A[mid-1] < A[mid] &&  A[mid] < A[mid+1] && key < A[mid])
			return getKeyIndex(A, p, mid-1, key);
		// else search in right part of the array.
		else 
			return getKeyIndex(A, mid+1, r, key);
	}

Please point out, if you find any error.
Time complexity : O(logn)

- Anonymous July 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's incorrect. key < A[mid] does NOT guarantee that the key lies in left part.

- __xy__ July 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

Use a modified binary search.

1. Check if the pivot element is equal to the given element. If yes, return the index.

2. If the pivot element != given element, compare the pivot element with it's adjacent elements that are to the left and to the right

Here 3 cases arise:

3a. The pivot element is the boundary element between the monotonically increasing and monotonically decreasing subarrays.
.  i. Apply this modified binary search in the left subarray
   ii. If the given element is not found in the left subarray apply this modified binary search AGAIN in the right subarray

3b. The pivot element lies completely in the monotonically increasing subarray.
   i. if the given element < pivot element, look up in the left subarray
   ii. if the given element > pivot element look up in the right subarray.

3c. The pivot element lies completely in the monotonically decreasing subarray.
   i. if the given element < pivot element, look up in the right subarray
   ii. if the given element > pivot element look up in the left subarray

if the given element is not found, return -1.

Even after applying binary search twice for case 3a, the complexity is still O(lgn), because it is at most once that the binary search is applied twice and each application of binary search has time complexity O(lgn)

- Murali Mohan July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Will not work!
Example:
array =1, 3, 5, 7, 9, 6, 4
key = 6

first iteration:
pivot = 7, in increasing part.
key<pivot, so you will search left subarray and not find 6

- __xy__ July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@__xy__

It will work!

Read point #3a
>> ii. If the given element is not found in the left subarray apply this modified binary search AGAIN in the right subarray

- Murali Mohan July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't work!

For the example that I gave, 3b applies. (not 3a)
The pivot element (=7) is not at the boundary of increasing and decreasing parts. It lies completely in the increasing part.

- __xy__ July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@__xy__

I am sorry. You are right! My solution does not work, deserves a down-vote.

- Murali Mohan July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

__xy__ is right. This wont' work!

- Anonymous July 20, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More