Amazon Interview Question for Software Engineer / Developers


Team: Kindle-Periodicals
Country: India
Interview Type: In-Person




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

use binary search till you get 1 and even after getting 1 continue your searching until you find NO 1 , and return the last position of 1 you saw. This will give the position of first 1 in the sorted array. using binary search.

- harish_venkat March 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Find the position of first '1' in a sorted array that contains only 0-s and 1-s
*/
#include<stdio.h>
#include<stdlib.h>
int BST(int a[],int i,int j)
{

if(i<=j)
{
int mid=(i+j)/2;
if((a[mid]==1&&mid==0)||(a[mid]==1&&a[mid-1]==0))
return mid;

else if(a[mid]==0)
return BST(a,mid+1,j);
else
return BST(a,i,mid-1);

}
return -1;
}

int main()
{

int a[]={0,0,0,0,0,0,1,1,1,1,1,1,1,1};
int n=sizeof(a)/sizeof(a[0]);
printf("%d",BST(a,0,n-1));
return 0;

}

- NaiveCoder March 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can provide a linear solution to this, I am not sure about the advantage we achieve by using a BST.
{
main()
{
int i = 0, ar[]={0,0,0,0,1,1,1,1,0,0}, arr_length = 0;
int start_1, end_1;
bool start_is_set = false, end_is_set = false;
arr_length = sizeof(a)/sizeof(a[0]);
for(i = 0; i < arr_length; i++)
{
if(start_is_set == false)
{
if(a[i] ==1)
{
start_1 = i;
start_is_set = true;
}
}
if(end_is_set == false)
{
if(a[length - i]==1)
{
end_1 = length-i;
end_is_set = true;
}
}
if(end_is_set && start_is_set)
{
break;
}
}
}
}

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

bst makes ur search logn in above code if input is 00000111001100011000 then the answer obtained is unexpected .and also the root question says it is sorted ,in linear search O(n).correct me if i am wrong

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

int findFirstOne(int *arr, int len)
{
if ( arr == NULL || len < 1 )
return -1;

if ( arr[0] == 1 ) // if array order is decreese, first item is answer.
return 0;

//binary search.
int i=0;
int j = len - 1;
while ( i < j)
{
int mid = i + (j-i)/2;
if ( arr[mid] == 1)
{
j = mid;
}
else
{
i = mid+1;
}
}

return arr[j] ? j : -1; // if this array don't have 1, return -1.
}

- Ethan March 27, 2012 | 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