## Amazon Interview Question for Software Engineer / Developers

Country: -

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

I think u guys have nt understood the qns properly. The end of the string is nt specicifed. Its an infinite string, so calculating MID and applying BST wont be possible. The soln ofcourse will require BST, but to calculate the end we need to either go for random number generation and then testing whether the value at this index is one or not or by taking a value and incrementing it exponentially to chk whether the value at this no as index is 1. If one is found thru any of the mtds above then use it as the end and then apply the concept of bst.

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

This needs a one-sided binary search.

Let's say the Array is A. Start at position i=0 of the array. I assume the Array is large enough so that there won't be errors.

int prev = -1
while(A[i] == 0) {
prev = i;
i*=2;
}

This will get us a range of prev+1 to i in between which the transition would have happened.

Now we can apply a specialized binary search to find the first location of 1 in this range.

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

I think you are assuming "i = 1" here, else the loop will never terminate.

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

I think you need to understand that amount of specifics implicitly...

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

Binary Search.

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

Binary search , with increasing index as 2^k each time with k++.... O(log n)

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

Brijesh,
Can you explain a bit about the use of increasing index 2^k?
How is binary search initiated (with what values) here?

Thanks.

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

Take it in an array.then compare A[mid]>=1.Accordingly do binary search...

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

``````int firstonepos(int* a,int i,int j){
if(i==j) return i;
else if(a[(i+j)/2]==1){
return firstonepos(a,i,(i+j)/2);
}
else{
return firstonepos(a,(i+j)/2+1,j);
}
}

int main(){
int a={0,0,0,0,0,0,0,0,1};
printf("%d\n",firstonepos(a,0,8));
return 0;
}``````

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

The binary search will not work. Suppose the sequence is 01111. Here the median is 1. When 1 is compared with median (i.e. 1) it returns the index 3 which is the second one.

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

@Sam :binary search will surely works here just check condition this
a[i]==1 && a[i-1]==0 ok and accoredingly make the base conditions :)
code for this---
int INDEXRETURN(int arr[],int n)
{
int start=0;
int end=n-1;
int mid;
while(start<end)
{
if(a[start]==1)
return start;
if(a[end]==0)
return -1;// not any index

mid=(start+end)/2;
if(a[mid]==1&&a[mid-1]==0)
return mid;
else if(a[mid]==0)
start=mid+1;
else
end=mid-1;
}
return -1;// not available
}

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

@geeks it doesn't work for i/p 01111. I think while loop should be (start<=end).

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

The question is the input is a string or a number. If it is number than bitshift can be used. Else, underlying concept of binary search can be used.

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

Well, I realized that if it is an integer, then the first one be MSB. So that option should not be considered. But it is a question worth asking. :)

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

``````#include <cstdlib>
#include <iostream>

using namespace std;

//TASK locate index of first 1 in an 0*1* string

// supposing full string is an in-memory char*
int SearchFirstOne(char *s, int *result){
if (!s){ *result=-1; return -1; }// could not find '1'
int min = 0;
int max = strlen(s)-1;
int mid = -1;
*result = -1;
int retval = -1;
while (min < max){
mid = (min+max)/2;
printf(" min:%d, mid:%d, max:%d\n", min, mid, max);
if (s[mid]== '1') {
max = mid-1;
*result = mid;//so far this is a valid starting location
retval = 0;
}
else
{min = mid+1;}

}
if (s[min] == '1'){ *result = min; return 0;}

return retval;
}

int main(int argc, char *argv[])
{
char *s = "011111111";
// one solution using simplest tool:
printf("%d\n", strchr(s,'1') - s);
// also can use :%s/0*1 or awk/sed to find in a file, or a FSM if the string is coming through "the wire" one byte at a time
// also, opening the file in notepad then ctrl+f to find the first 1 also works to find the column number

//supposing we want a general-purpose search through an in-memory char*, use the binary search from above:
int result = -1;
int errcode = SearchFirstOne(s, &result);
if (errcode == 0)
{
printf("%d\n\n", result);
}
else
{printf("Error trying to find '1'\n");}
//I ignore the error code from here on to the end:
SearchFirstOne("111111", &result);
printf("%d\n", result);
SearchFirstOne("11111", &result);
printf("%d\n", result);
SearchFirstOne("0", &result);
printf("%d\n", result);
SearchFirstOne("1", &result);
printf("%d\n", result);
SearchFirstOne("001111", &result);
printf("%d\n", result);
SearchFirstOne("01111", &result);
printf("%d\n", result);
SearchFirstOne("000111", &result);
printf("%d\n", result);
SearchFirstOne("000011111111111111111111", &result);
printf("%d\n", result);
SearchFirstOne("111111111111111111111111111111111111111111111111111", &result);
printf("%d\n", result);
SearchFirstOne("0000000000000000000000000000000000000000000000000000000000000000000000000000000000", &result);
printf("%d\n", result);
SearchFirstOne("000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111", &result);
printf("%d\n", result);

system("PAUSE");
return EXIT_SUCCESS;
}``````

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

int a[]={0,1,1,1,1,1,1,1,1};
int min=0,mid;
int max=(a.length)-1;

while(min<max)
{
mid=(min+max)/2;
if(a[mid]==1)
max=mid;
else
min=mid+1;

if(a[min]==1)
{
System.out.print(min);
break;
}

}

}

}

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

Most of the solutions present here are kind of assuming that length of array is provided.

But it looks like inteviewer is looking for an solution which does not take care of the length of the string.

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.

### 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.