Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

Binary Search (sorta)

Start in the middle of the array, since this is sorter and rotated one half of the array MUST be completely sorted; the other half we have no clue. To test which half is the sorted half, check if the beginning of the array is less than the middle value; if so then this is the sorted half, and check if the search value is between the first element and the middle element. If so, recurse on this half of the array, else recurse on the the other half.


Now if it turns out the second half is the sorted half, test if the value to are looking for is between the middle value and the last value. If it is, recurse on this half, else the other. Continue until you find what you are looking for.

Now since at every step you are tossing half the array you are doing a binary search aka O(log N)

int finder(int arr[], int start, int end, int val)
{
	int mid=(end-start)/2;
	
	if(start==end)
	{
		if(arr[start]==val)
			return start;
		else
			return -1;
	}
	
	//is first half sorted?
	if(arr[start]<= arr[mid])
	{
		if(arr[start]< val && val<arr[mid])
			return finder(arr, start, mid, val);
		else
			return finder(arr, mid+1, end, val);
	}
	else	   //the second half of array is sorted
	{
		if(arr[mid+1]< val && val<arr[end])
			return finder(arr, mid+1, end, val);
		else
			return finder(arr, start, mid, val);
	}	
}

Now I didn't take time to debug this...but it gives my general approach

- Anonymous August 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about val == arr[mid] case? You can't cut either 1st or 2nd half, e.g. {0,1,2,2,2,2,2,2,3} and locate 2.

- Anonymous August 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That is correct, but it can be easily fixed with a <= instead of < in the checks.

- Anonymous August 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

fails at {3, 4, 5, 6, 1, 3, 3, 3, 3, 3, 3} when searching for 6 (even with <= )

- engzizo October 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this should solve it

int finder(int arr[], int start, int end, int val)
{
	int mid=(end-start)/2+start;
	
	if(start==end)
	{
		if(arr[start]==val)
			return start;
		else
			return -1;
	}
	
	//is first half sorted?
	if(arr[start]<= arr[mid]){
		if(arr[start]<= val && val<=arr[mid])
			return finder(arr, start, mid, val);
		else{
			int x = finder(arr, mid+1, end, val);
			if(x>-1)
				return x;
			else
				return finder(arr, start, mid, val);
		}
	}
	else	   //the second half of array is sorted
	{
		if(arr[mid+1]<= val && val<=arr[end])
			return finder(arr, mid+1, end, val);
		else{
			int x = finder(arr, start, mid, val);
			if(x>-1)
				return x;
			else
				return finder(arr, mid+1, end, val);
		} 
	}	
}

- engzizo October 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static int findIndexB(int arr[] ,int start,int end,int val){
		int mid = (end + start)/2;
		
		if(start == end){
			if (arr[start] == val ) 
				return start;
			else
				return -1;
		}
		if( val <= arr[mid])
			return findIndexB(arr,start,mid,val);
		else	
			return findIndexB(arr,mid+1,end,val);
	}
	
	public static  int findIndex(int arr[], int start, int end, int val)
{
	int mid=(end+start)/2;
	
	if(start==end)
	{
		if(arr[start]==val)
			return start;
		else
			return -1;
	}
	
	//is first half sorted?
	if(arr[start]<= arr[mid])
	{
		if(arr[start]<= val && val<=arr[mid])
			return findIndexB(arr,start,mid,val);
		else
			return findIndex(arr, mid+1, end, val);
	}
	else	   //the second half of array is sorted
	{
		if(arr[mid+1]<= val && val<=arr[end])
			return findIndexB(arr, mid+1, end, val);
		else
			return findIndex(arr, start, mid, val);
	}	
}

- Max August 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

9, 9, 9, 8, 10, << input you posted is not sorted.
Can we assume that array was already sorted and then this was rotated to the right by a certain distance?

- soodongStudying August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is. Originally you have an array {1,2,3,3,9,9,9,8,10,12,13}, and it's then rotated right by 9, so it becomes {3, 9, 9, 9, 8, 10, 12, 13, 1, 2, 3} (the first element from the original array, is moved to index 9, generally new_index = (original_index + 9) % array_size.

- joe kidd August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, remove 8. My bad.

- joe kidd August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
{{{ In this problem sometime we not able to judge we search in left subarray or right subarray Like this case Original Array 0 1 2 2 2 2 2 2 2 2 2 2 Rotate it 2 2 0 1 2 2 2 2 2 2 2 2 Now if i ask what is index of 0/1 then middle element is 2 and start also and end also 2 for these cases we should search in both side and return the index which is not -1 if(arr[low] == arr[mid] == arr[high]) { int index1 = FindIndex(low,mid-1, item); int index2 = FindIndex(mid+1,high,item); //out of these two index one be -1 so return other one } // remain steps will be same like normal sorted rotated case just we need to case special case..... - kavita August 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, indeed. This the solution I provided:
- find the pivot place O(N) = log N
- run two binary searches O(N) = log N

- joe kidd August 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a single pass through to find both the rotation point (assume non-zero rotation) and the first index of the value, and the total length.

If the first index is after the rotation point, subtract the rotation point.

If the first index is before the rotation point, add the index to the total length minus the rotation.

#!/usr/bin/env python


def find_index(elements, value):
    rotation = 0
    first = -1
    max = 0
    length = 0
    for i, val in enumerate(elements):
        length += 1
        if rotation == 0 and max > val:
            rotation = i
        else:
            max = val
        if first == -1 and value == val:
            first = i
        elif rotation != -1 and value == val:
            return i - rotation
    return length - rotation + first


if __name__ == '__main__':
    print find_index([3,8,9,9,9,10,12,13,1,2,3], 3)

This prints out 2 (0-indexed).

- Dan August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.  FindIndexes(A, number)
2.  if number > A[0]
3.      for i=0 to n - 1 && number > A[i] 
4.            if A[i] == number
5.               print i break;
5.  else if number < A[0] 
6.      for i = n-1 down to 0 && number < A[i]
7.           if A[i] == number
8.                print i break;
9. else
10.   print 0

- dirishkumar August 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think this handles, say, finding 4 in the list [3, 4, 5, 6, 1, 2, 3] properly. It would return 1, I think, and the correct answer is 4 (original list is [1, 2, 3, 3, 4, 5, 6]. What languages is this btw?

- Dan August 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if i am not wrong, question was to find the index after rotation. do we need to find the index before rotation. if that is the case my program doesnt handle. It is not any programming language i just wrote down the algorithm

- dirishkumar August 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The point is to find the value anywherein the array.

- Anonymous August 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

First - Bring back the original array (un-rotate)
1. find the initial offset (the point of rotation, or first instance of min value) at index, say I - this takes O(n)
2. Divide the array in place - from 0 to I-1 and I to length -1
3. Rotate both arrays (swap first and last) - this takes O(n/2) so O(n)
4. Rotate the final array - still O(n)

Search -
1. Use Binary search to find index of any item on the array in step 4 above - O(logn) - say j
2. Add initial offset (I) , this is your final answer - I+j

Time - O(n)
Space - O(1)

- Ghost August 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If we're going for O(n) time, can't we just iterate through the array and return the first instance that array[i] == element?

- Rick March 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findIndexB(int arr[] ,int start,int end,int val){
int mid = (end + start)/2;

if(start == end){
if (arr[start] == val )
return start;
else
return -1;
}
if( val <= arr[mid])
return findIndexB(arr,start,mid,val);
else
return findIndexB(arr,mid+1,end,val);
}

public static int findIndex(int arr[], int start, int end, int val)
{
int mid=(end+start)/2;

if(start==end)
{
if(arr[start]==val)
return start;
else
return -1;
}

//is first half sorted?
if(arr[start]<= arr[mid])
{
if(arr[start]<= val && val<=arr[mid])
return findIndexB(arr,start,mid,val);
else
return findIndex(arr, mid+1, end, val);
}
else //the second half of array is sorted
{
if(arr[mid+1]<= val && val<=arr[end])
return findIndexB(arr, mid+1, end, val);
else
return findIndex(arr, start, mid, val);
}
}

- Max August 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the array now becomes two sorted array, find the index from which the sorting order changes, which is o(n), then use binary search in both arrays to find the given element O(lgn). time complexity is O(n)+O(lgn) so it's O(n)

- Jackie August 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[] = {3, 8, 9, 9, 9, 10, 12, 13, 1, 2, 3};
    int cA = (sizeof(a)/sizeof(*a)), e = 3, ct = 0, ct2 = 0;
    int st = -1, st2 = -1;
    int k = 0;
    
    for (int i = 0; i < cA; i ++){
        if (a[i] == e){
            st = i;
            break;
        }
    }

    if (st >= 0){
        int i = st;
        while (a[i] == e){
            ct ++;
            i ++;
        }
        if (st == 0){
            i = cA - 1;
            while (a[i] == e && i > st + ct){
                ct2 ++;
                st2 = i;
                i --;
            }
        }
    }
    k = ct + ct2;
    int r[k];
    for (int i = 0; i < ct; i ++){
        r[i] = st + i;
    }
    for (int i = 0; i < ct2; i ++){
        r[ct + i] = st2 + i;
    }
    
    for (int i = 0; i < k; i ++){
        printf("%d, ", r[i]);
    }

- OV August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[] = {3, 8, 9, 9, 9, 10, 12, 13, 1, 2, 3};
    int cA = (sizeof(a)/sizeof(*a)), e = 3, ct = 0, ct2 = 0;
    int st = -1, st2 = -1;
    int k = 0;
    
    for (int i = 0; i < cA; i ++){
        if (a[i] == e){
            st = i;
            break;
        }
    }

    if (st >= 0){
        int i = st;
        while (a[i] == e){
            ct ++;
            i ++;
        }
        if (st == 0){
            i = cA - 1;
            while (a[i] == e && i > st + ct){
                ct2 ++;
                st2 = i;
                i --;
            }
        }
    }
    k = ct + ct2;
    int r[k];
    for (int i = 0; i < ct; i ++){
        r[i] = st + i;
    }
    for (int i = 0; i < ct2; i ++){
        r[ct + i] = st2 + i;
    }
    
    for (int i = 0; i < k; i ++){
        printf("%d, ", r[i]);
    }

- OV August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int FindElement(int[] A, int s, int e, int elem)
        {
            if (s > e)
                return -1;

            int mid = s + (e - s) / 2;
            if (elem == A[mid])
                return mid;

            if ((elem < A[mid] && elem >= A[s]) || (elem > A[mid] && elem > A[e]))
                return FindElement(A, s, mid - 1, elem);

            if ((elem > A[mid] && elem <= A[e]) || (elem < A[mid] && elem < A[s]))
                return FindElement(A, mid + 1, e, elem);

            return -1;
        }

- Anonymous August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

find(start,end,Array,x){
	int mid= (start+end)/2;
	if(A[start]==x) return start;
	if (A[end]==x) return end;
	if(end-start <=1) return -1;
	if( (A[start]<x && A[mid]<x) || (A[start]>x && A[mid]<x) ) return find(mid,end,A,x);
	if( (A[start]<x && A[mid]>=x) || (A[start]>x && A[mid]>=x) ) return find(start,mid,A,x);
}

- SecretAgent August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>

int bs(int input[],int data,int low,int high)
{
	int mid;
	
	if(low > high)
		return -1;
	if (low==high && input[low]==data)
		return low;
	mid = low+ (high-low)/2;
	
	if( input[mid]==data)
		return mid;
	else if( input[low] <= input[mid-1] )
	{
		
		if(data >= input[low] && data <= input[mid-1])
			return bs(input,data,low,mid-1);
		else
			return bs(input,data,mid+1,high);
	}
	else
	{
	
		if(data >= input[mid+1] && data <= input[high])
			return bs(input,data,mid+1,high);
		else
			return bs(input,data,low,mid-1);
	}
}

int main()
{
	
	int input[]={3, 9, 9, 9, 10, 10, 12, 13, 1, 2, 3};
    int no;
	int searchData;
	no = sizeof(input)/sizeof(int);
	printf("Enter data : ");
	scanf("%d",&searchData);
	
	printf("Found at %d",bs(input,searchData,0,no-1));
	getch();
}

- Shankar August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

CTCI 10.3

- Anonymous August 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

CTCI 10.3

- Anonymous August 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To handle all cases correctly, it need loop all elements

{2,2,2,2,2,2,2,2,1,2}
Find the index 1

arr[start] = arr[end] = arr[mid] = 2

- Nick August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm: As the pattern of array is Increasing sorted Order and at any point there will be small element and again it starts Increasing in Sorted Order.

We could find the break in Sorted array pattern using Custom Binary Search with logic as comparing 3 number pattern if increasing sorted order is maintained.

Now once the break is found we could check in both halves using Binary Search.

- srikawnth August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm: As the pattern of array is Increasing sorted Order and at any point there will be small element and again it starts Increasing in Sorted Order.

We could find the break in Sorted array pattern using Custom Binary Search with logic as comparing 3 number pattern if increasing sorted order is maintained.

Now once the break is found we could check in both halves using Binary Search.

- srikawnth August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I found a very interesting solution to this problem. I guess its the logic that matters :

int getMidBSearch(int[] arr,int lb,int ub,int oldMid) {
if(lb>=ub)
{
System.out.println("returning : "+(lb));
return lb+1;
}
else
{
int newMid=(lb+ub)/2;
if(arr[lb]<arr[newMid] && arr[oldMid]<arr[newMid])
{
lb=newMid;
}
else
{
ub=newMid;

}
getMidBSearch(arr, lb, ub,newMid);
}

}

Call the above method like : int n = getMidBSearch(a, lb, ub,0);
This will divide the array into two non-equal parts and we will get the two sorted lists, one goes from 0..n and another from n+1...arr.length-1. Then,
1. Check if element to be searched lies in list one or 2nd
2. Based on point#1, call a binary search again (Since we have two sorted lists now)

A binary search is performed twice - once to find the index from where the two lists are divided, and another time to find the element in the list.

Please let me know your comments on this.

- Ankit Vij August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Binary Search O(lg(N)) solution:

int BinarySearch(vector<long> source, int toSearch)
{
	int lower, middle, upper;
	lower = 0;
	upper = source.size() - 1;
	while (lower <= upper) {
		middle = lower + (upper - lower) / 2 + (upper - lower) % 2;
		if (toSearch == source[middle])
			return middle;
		else if (toSearch == source[lower])
			return lower;
		else if (toSearch == source[upper])
			return upper;
		else if (source[lower] <= source[middle]) {
			// 15 16 19 20 25 30 1 3 4 5 7 10 14
			// L              M               U
			// 4 8 9 9 9 10 12 13 1 2 2 3
			// L            M           U
			if (toSearch > source[middle])     // Ex: toSearch>30; toSearch=13
				lower = middle + 1;
			else if (toSearch > source[lower]) // Ex: toSearch=20; toSearch=9
				upper = middle - 1;
			else							   // Ex: toSearch=5; toSearch=2
				lower = middle + 1;
		} else { // Middle < Lower
			// 15 16 19 20 25 30 1 3 4 5 7 10 11 14
			// L			  	   M		      U
			// 4 8 9 9 9 10 12 13 1 2 2 3
			// L                  M     U
			if (toSearch < source[middle])     // Ex: toSearch=1
				upper = middle - 1;
			else if (toSearch < source[upper]) // Ex: toSearch=10; toSearch=2
				lower = middle + 1;
			else				// Ex: toSearch=20; toSearch=12
				upper = middle - 1;
		}
	}
	return -1;
}

- Teh Kok How September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

forget the first two lines
you are left with what actually is the question
You just have have index the element in array
Probably be it with a quick sort search

- chikku August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think that it is sorted and rotated is important...

- Dan August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Better solution is to find index first element (after it has been rotated) meaning how many times it has been rotated. When that is known we can find the index by modified binary search. where new_mid = (index_of_firstelement + mid)% (last + 1).

- Green Lantern August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public int indexFun(int[] arr, int start, int end, int number)
	{
		if(arr[start] == number)
		{
			return start;
		}
		if(arr[end] == number)
		{
			return end;
		}
		if(start == end)
		{
			return -1;
		}
		int mid = ( start + end ) / 2;
		if((arr[mid]<=arr[start] && (number<=arr[mid]|| number>=arr[start]))||
				(arr[mid]>=arr[start] && number>=arr[start] && number <=arr[mid]))
		{
			return indexFun(arr, start, mid, number);
		}
		else
		{
			return indexFun(arr, mid+1, end, number);
		}
	}

- sp!de? August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How does this account for rotation?

I tried it with input 3,4,5,1,2,3,3,3,3. The correct answer is 2. I tried this code and it returned 0.

- Dan August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good catch Dan.
I updated the if condition. I guess now it works fine.
Please check.

- sp!de? August 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Still returns 0 when I compiled and tested the update. I understand how you might do a quick-sort style solution, but only after unshifting the sorted array. See my Python example of making a single linear pass for what I think solves it in O(n). O(log N) might be possible but only after unshifting, I think, so I suspect O(n) is the most efficient.

- Dan August 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

case 1:
5555123555555555
case 2
5555555551235555

- Nick August 10, 2014 | 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