Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

Goal: to preserve O(log n) running time for searching an element in a rotated array.

If we somehow figure out by how many indexes has the array been rotated then we can use a slightly modified version of binary search:

/**
	 * 
	 * @param arr - array to be searched
	 * @param num - number to search for in the array
	 * @param start - starting index
	 * @param end - ending index
	 * @param offset - amount of rotation
	 * @return
	 */
    public static int search(int[] arr, int num, int start, int end, int offset) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end)/2;
        int actualMid = (mid + offset) % arr.length;
        
        if (arr[actualMid] == num) {
            return actualMid;
        } else if (arr[actualMid] > num) {
            return search(arr, num, start, mid - 1, offset);
        } else {
            return search(arr, num, mid + 1, end, offset);
        } 
    }

The real trick is to come up with an algo to search for the amount of rotation with a running time not worse than O(log n). This will result in a total complexity ( find the amount of rotation + search) of 2*O(log n) which is in-fact just O(log n).
The algo to search for the amount of rotation is quite similar to binary search. Here's the code:

public static int findRotationIndex(int[] arr, int start, int end) {
        int mid = (start + end)/2;
        if (start == end || arr[start] < arr[mid] && arr[end] > arr[mid]) {
        	// in this case either there is no rotation in the array or there
        	// is just one element left in the passed range
            return start;
        } else if (arr[start] > arr[mid]) {
        	// in this case the rotation starts in the left half of the array
            return findRotationIndex(arr, start, mid);
        } else {
        	// in this case the rotation starts in the right half of the array
            return findRotationIndex(arr, mid + 1, end);
        }
    }

- Vivek Thakyal March 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use binary search, simple :D

- mohit March 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Binary search as it is will not work here. You need to tweak it a bit as the array is rotated.

- Vijay March 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah Vijay, I agree with your answer. What I wanted to convey at that time was that the idea is similar to binary search.

It was intuitive obviously due to the 'sorted' array.

The following Algorithm (as explained in the program)
For further queries:- comment plz

#include<stdio.h>
/*
*A[] is the array in which we have to search
*no is the number to be searched
*start is the starting index to search in the array
*end is th terminating index to search in the array
*/
int indexSearch(int A[], int no, int start, int end)
{
/*similar to binary search we have to compare with the middle element*/
int mid=(start+end)/2 ;
// printf("Start = %d End = %d \n",start,end);

/* Base Case if not found, or originally the limits were inserted in wrong order*/
if(start>end)
return -1;

/*If the middle element matches the number, we are done, base case if found*/
if(no==A[mid])
return mid;
else
/*If the middle element is smaller then number, the answer may be in right or left*/
if(no>A[mid])
{
/*if the number is smaller then the rightmost end then recursively search for the number in the right sided array*/
if(no<=A[end])
return indexSearch(A,no, mid+1,end);
/*otherwise recursively search in the left side*/
return indexSearch(A,no, start,mid-1);
}
else
/*If the middle element is greater then number, the answer may be in right or left*/
if(no<A[mid])
{
/*if the number is greater then the leftmost end then recursively search for the number in the left sided array*/
if(no>=A[start])
return indexSearch(A,no,start,mid-1);
/*otherwise recursively search in the right side*/
return indexSearch(A,no,mid+1,end);
}
}
int main()
{
int A[]={7,-1,6};
int toSearch=6;
int start=0;
int end=sizeof(A)/sizeof(A[0])-1;
int index;
index=indexSearch(A,toSearch,start,end);
printf("%d is at index %d\n",toSearch,index);
}

- Mohit Ahuja March 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

mohit wat's d time complexity in this algo..?

- abhishek March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Pls correct me if I am wrong ...

But it won't work for 6 7 8 9 11 1 2 3 ??

- Anonymous April 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

As we hv rotated array (consider it as s1=xy).....first create s2=s1s1(by concatation(if space is not problem))......then apply binary search..........

s2-->678123456712345
like search for 4 (4<5)

left half-->67812345
(4>1)
right half-->2345

then u got again right half finally 4......(time compO(logn) ..and space compO(n))

45

- saurabh March 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

input - 67812345
check for the min number in the array, capture the location and also note the last digit in the array eg. A[n] =5 or A[7]=5 .
Now if the element to search is 4, then check with last digit and set the array value to 3 i.e A[3] or min value position. else
if the element to search is 7, then check with last digit check and set the array value to 0 i.e A[0].

- barath K S March 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

what's bt in the question?

- pdgetrf March 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

bt = binary tree

- Anuj March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

actually, this person just uses an incredible amount of shortening on sentences. bt = but! he saved one letter, but confuses everyone :)

- Riaan April 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

write the code for binary search,
let left = index of smallest element
right = index of largest element + n.
replace all the places where you are using array index, say m with m%n,
where n = number of elements.
you're done.

- gautam142857 March 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int search(int key , int * a , int l , int r , int n ){
  r+=n;
  int m;
  while ( l<=r ){
    m=(l+r)/2;
    if ( key == a[m%n] )
      return m%n;
    else if ( key > a[m%n] )
      l=m+1;
    else
      r=m-1;
  }
}

- gautam142857 March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Kya yaar!
s: start
e: end
if [s]<[input]<[mid] || [mid]< [s]<[input]

s=mid+1

else

e=mid-1;

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

#include<stdio.h>

void intput(int *a, int n)
{
    int i;
    for(i=0; i<n; i++)
        scanf("%d", &a[i]);
}

void print(int *a, int n)
{
    int i;
    printf("\nThe elements in the array are:\n");
    for(i=0; i<n; i++)
        printf("%d\t", a[i]);
}

int search(int *a, int lb, int ub, int data)
{
    int mid;
    if(lb>ub)
        return 0;
    mid = (lb+ub)/2;
    if(a[mid] == data)
        return mid;
    else if(a[lb]<=a[mid])
    {
        if( (a[lb]<=data) && (data<a[mid]) )
            search(a, lb, mid-1, data);
        else
            search(a, mid+1, ub, data);
    }
    else
    {
        if( (a[mid]<data) && (data<=a[ub]) )
            search(a, mid+1, ub, data);
        else
            search(a, lb, mid-1, data);
    }
}

int main()
{
    int n, s, indx, *arr;
    printf("Enter the size of array. ");
    scanf("%d", &n);
    arr = (int*)malloc(n*sizeof(int));
    intput(arr, n);
    print(arr, n);
    printf("\nEnter the element to search. ");
    scanf("%d", &s);
    indx = search(arr, 0, n, s);//  Time Complexity = O(log n)
    if(indx)
        printf("\nThe element is found at location: %d.", indx);
    else
        printf("\nThe element is not found.");
    return 0;
}

- Abhijeet Muneshwar January 17, 2014 | Flag Reply


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