## Amazon Interview Question for Software Engineer / Developers

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

This can be done by modified binary search.....
1.At first check the 2^i the index i=0,1,2,....
2.If '1' occurs at some point of index [example say 32 i.e. 2^5]
3.Apply binary search between 2^4 and 2^5 [in infinite array the problem is we ill not have the info of high to apply binary search....]

correct me if i am wrong ,thanks in advance..

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

yours is right I think

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

The idea is to find upper bound for 1 by exponentially increasing the index in power of 2 and then finding the transition index by exponentially decreasing the index.
Similar to binary search.
Complexity 2*log(N+1) where N is the transition index.

``````A is the input array
1.  start=0, end=1, mid=0
2.  if((A[start]==0)&&(A[end]==1)) return start;
3.	while(A[end] != 1)
start=end;
end=end<<1;
4.	while(A[start+1] != 1)
mid=(start+end)/2;
if(A[mid]==0)
start=mid;
else
end=mid;
5. return start;``````

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

how can you find end value. its infinite stream. good idea is to take some proper offset value and keep increasing till stream of 1 encounters. You can use your algo afterwards

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

there is nothing like end value. the idea is to find two indexes where at first index there is a 0 and at second index there is a 1.
I m increasing the index "end" in power of 2 but one can increment in any manner though the basic idea is same "find two indexes where at first index there is a 0 and at second index there is a 1"

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

Perfect.! and how are you handling the array-out-of-bounds case ???

say a[2^8]=0
and a[2^16] is out-of-bounds.
the transition is happening somewhere in between.!

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

i didn't consider array out of bound intentionally because question says array is infinite(a hypothetical assumption).

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

nice. its an exponential probe+bin search combo. I don't think u need to handle the case of out of bounds cuz the array is infinite.

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

Statement 4 in the above code , need an additional check
start < end

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

Statement 4 in the above code , need an additional check
start < end

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

I don't think so a check of start<end will be required, as no where we are going to hit a code where start can exceed end.

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

can somebody explain the question more clearly. no. of zeros are followed by number of 1s or we can have something like 01010101010101 in this case what would be the trasition index

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

its a sorted array. which means it can only be this way: 000000.........11111..........

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

pseudo code:

Assuming array a[1....inf]

low=1;
value=a[low];
while(value==a[2*low])
low*=2;

high=low*2;

return binarySearch(a, value, low, high);

correct if wrong..

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

when you binary search how do you know that the search result is the one at transition point?

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

Sry...my mistake

we can go for sequential search in that interval to find out the transition point

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

our array is like [0000....000....1..1....1111]
we'll take two variables
1.midZero = start point"0"
2.midOne

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

our array is like [0000....000....1..1....1111]
{{ we'll take two variables
1.midZero = start point"0"
2.midOne = endpoint "n-1"
now compute mid = midZero+(midOne-midZero)/2;
if a[mid] == 0
set midZero = mid
else set midOne = mid
repeat the loop while (midZero + 1) == midOne}}

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

this won't work...because we dont know the length of an array and hence won't be able to calculate midone...
it has to be done sequentially...with some jumps

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

since this is sorted...
then...
n: size of array..
l=0; u=n-1

while(l<u)
{
m=(l+u)/2;
if(u==(l+1))
{ found
break;
}
if(a[m]==0)
l=m;
else
u=m;
}

therefor position u will be the transition of 0 to 1;

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

y dont we XOR and then at the point where the result is 1, thats the transition point

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

i think in case of XOR you have to scan the array sequentially which means o(n) but if we do some kind of binary search then we can do it in less than o(n)

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

I guess this code should work, return the first position of '1'....

``````int	TransitionPoint( int *input )
{
int beg, end = 1;

while( input[end] == 0)
{
end <<= 2;
}

beg = end>>2;

return BinarySearch(input, beg, end );
}

int BinarySearch(int *input, int beg, int end )
{
int mid = (beg+end)>>2	;

if (input[mid] == 0)
return BinarySearch(input, mid+1, end);
else
{
if(input[mid-1] == 0)
return mid;
else
return BinarySearch(input, beg, mid-1);
}
}``````

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

I guess this code should work, return the first position of '1'....

``````int	TransitionPoint( int *input )
{
int beg, end = 1;

while( input[end] == 0)
{
end <<= 2;
}

beg = end>>2;

return BinarySearch(input, beg, end );
}

int BinarySearch(int *input, int beg, int end )
{
int mid = (beg+end)>>2	;

if (input[mid] == 0)
return BinarySearch(input, mid+1, end);
else
{
if(input[mid-1] == 0)
return mid;
else
return BinarySearch(input, beg, mid-1);
}
}``````

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

I guess this code should work, return the first position of '1'....

``````int	TransitionPoint( int *input )
{
int beg, end = 1;

while( input[end] == 0)
{
end <<= 2;
}

beg = end>>2;

return BinarySearch(input, beg, end );
}

int BinarySearch(int *input, int beg, int end )
{
int mid = (beg+end)>>2	;

if (input[mid] == 0)
return BinarySearch(input, mid+1, end);
else
{
if(input[mid-1] == 0)
return mid;
else
return BinarySearch(input, beg, mid-1);
}
}``````

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

I guess this code should work, return the first position of '1'....

``````int	TransitionPoint( int *input )
{
int beg, end = 1;

while( input[end] == 0)
{
end <<= 2;
}

beg = end>>2;

return BinarySearch(input, beg, end );
}

int BinarySearch(int *input, int beg, int end )
{
int mid = (beg+end)>>2	;

if (input[mid] == 0)
return BinarySearch(input, mid+1, end);
else
{
if(input[mid-1] == 0)
return mid;
else
return BinarySearch(input, beg, mid-1);
}
}``````

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

take k window of data from stream of numbers..
1. find starting index of 1 in that window
2. now search for 1 in this new smaller range

``````public int findOne(int[] A, int startIndex, int endIndex) {
int start = startIndex;
int end = startIndex + 1;
int mid;
while (end < endIndex && A[end] != 1) {
start = end;
end *= 2;
}
if (end > endIndex && A[endIndex - 1] != 1)
return -1;

while (start < end && A[start + 1] != 1) {
mid = (start + end) / 2;
if (A[mid] == 0)
start = mid;
else
end = mid;
}
if (start == end)
return -1;
return start + 1;
}``````

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.