Amazon Interview Question for SDE1s


Country: United States
Interview Type: In-Person




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

public class Practice6 {

	public static void main(String args[])throws IOException{
		int arr[] = {4,5,6,7,8,1,2,3};
		
		int num = 7;
		int last = arr.length-1;
		int first = 0;
		performSearch(arr,first,last,num);
		
		
	}
	
	public static void performSearch(int arr[],int first,int last,int num){
		int mid = (first + last)/2;
		
		if(arr[mid] == num){
			System.out.println("Index is :: "+mid);
			return;
		}
		else if(arr[first]<arr[mid]){
			if(num >= arr[first] && num<arr[mid])
				binarySearch(arr,first,mid-1,num);
			else	
				performSearch(arr,mid+1,last,num);
		}else{
			if(num>arr[mid] && num <= arr[last]){
				binarySearch(arr,mid+1,last,num);
			}else{ 
				performSearch(arr,mid+1,last,num);
			}
		}
}
	
	public static void binarySearch(int arr[],int first,int last,int num){
		if(first<last){
		int mid = (first+last)/2;
		if(arr[mid] == num){
			System.out.println("Index is :: "+mid);
			return;
		}
		binarySearch(arr,first,mid-1,num);
		binarySearch(arr,mid+1,last,num);
		}else
			return;
	}
}

- Coder January 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Modification of binary search. I assume there is no duplicates in array.

int rotatedBinarySearch(int A[], int N, int key) {
	int L = 0;
	int R = N - 1;

	while (L <= R) {
		int M = L + ((R - L) / 2);
		if (A[M] == key)
			return M;

		if (A[L] <= A[M]) {
			if (A[L] <= key && key < A[M])
				R = M - 1;
			else
				L = M + 1;
		}
		else {
			if (A[M] < key && key <= A[R])
				L = M + 1;
			else
				R = M - 1;
		}
	}
	return -1;
}

Refer to leetcode.

- thelineofcode January 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

do binary search.
I think there is one same problem in leetcode.

- Kk January 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There shouldn't be any duplicates in the array.
The below java code would work fine

public static int findElement(int[] a, int low, int high, int x)
{
while(low<=high)
{

int mid=(low+high)/2;
if(a[mid]==x)
return mid;

else if(a[mid]<=a[high]){
if(x>a[mid]&&x<a[high])
low=mid+1;
else
high=mid-1;
}
else
{
if(x<a[mid]&&x>a[low])
high=mid-1;
else
low=mid+1;
}
}
return -1;

}

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

There shouldn't be any duplicates in the array.
The below java code would work fine

public static int findElement(int[] a, int low, int high, int x)
{
while(low<=high)
{

int mid=(low+high)/2;
if(a[mid]==x)
return mid;

else if(a[mid]<=a[high]){
if(x>a[mid]&&x<a[high])
low=mid+1;
else
high=mid-1;
}
else
{
if(x<a[mid]&&x>a[low])
high=mid-1;
else
low=mid+1;
}
}
return -1;

}

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

public static int search(int arr[],int first,int last,int key)
{
while((last>0)&&(first<=last))
{
int mid=(first+last)/2;

if(arr[mid]==key)
{
return mid;
}
else if(arr[mid]>key)
{
last=mid-1;
return(search(arr,first,last,key);
}
else
{
return(search(arr,mid+1,last,key);
}
}

- shashi kumar January 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

int testarray[20]={26,27,28,29,30,32,36,40,45,50,4,5,7,9,10,15,18,20,22,25};

int binary_search(int x, int start, int last)
{
	if(testarray[start]==x)return start;
	
	else if(testarray[last]==x)return last;
	
	
	
	else
	{
		int middle =(start+last)/2;
		if(start==middle) return -1;
		
		if(x>testarray[middle])
		return binary_search(x,middle,last);
		else
		return binary_search(x,start,middle);
	}
}

int find(int x,int start, int last)
{
	if(testarray[start]!=x && testarray[last]!=x)
	{
		int middle=(start+last)/2;
		
		if(testarray[middle]==x)
		return middle;
		
		if(testarray[middle]<testarray[start] && testarray[middle]<x)
		return binary_search(x,middle,last);
		
		else if(testarray[middle]>testarray[start] && testarray[start]<x)
		return binary_search(x,start,middle);
		
		else if(testarray[middle]<testarray[start] && testarray[middle]>x)
		return find(x,start,middle);
		
		else if(testarray[middle]>testarray[start])
		return find(x,middle,last);
		
		else
		cout<<"not found";
		return -1;
		
	}
	
	else 
	{
		if(testarray[start]==x)return start;
		else return last;
	}
		
		
}




int main() {
	// your code goes here
	int x,start=0,last=19;
	cout<<"enter element you wanna search \n ";
	cin>>x;
	int pos=find(x,start,last);
	cout<<pos;
	cin>>x;
	return 0;
}

- Mahendra Sengar January 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use custom Binary Search
Find the mid element and then compare
a. if the search value is less that left_start & current_pos then proceed with left subtree.
b. Else go for right sub tree.

- Ricky January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Modification of binary search

int checkKey (int s, int e, int mid, int a[], int key)
{
        if (a[s] == key)
                return s;
        if (a[e] == key)
                return e;
        if (a[mid] == key)
                return mid;
        return -1;
}

int find (int a[], int s, int e, int k)
{
        if (s > e)
                return -1;
        int mid = s + (e -s)/2;
        int i = checkKey (s, e, mid, a, k);
        if (i != -1)
                return i;

        if (s == e || mid == s)
                return -1;

        if (k > a[mid])
                s = mid+1;
        else
                e = mid-1;
        return find (a,s,e,k);
}

- SK January 14, 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