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

- n20084753 July 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yours is right I think

- Anonymous July 26, 2011 | Flag
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;

- Anonymous July 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- xyz July 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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"

- @xyz July 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Avinash Ega July 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- slimboy July 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aj July 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aj July 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gabbar August 05, 2014 | Flag
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

- Anonymous July 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Avinash Ega July 04, 2011 | Flag
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..

- Sonal July 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Myth July 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sry...my mistake

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

- Sonal July 04, 2011 | Flag
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

- Anonymous July 06, 2011 | Flag Reply
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}}

- tg July 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- job_hunter July 07, 2011 | Flag
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;

- praveen0raj July 20, 2011 | Flag Reply
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

- Anonymous August 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- raja roy September 27, 2011 | Flag
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);
	}
}

- iatbst January 29, 2012 | Flag Reply
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);
	}
}

- iatbst January 29, 2012 | Flag Reply
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);
	}
}

- iatbst January 29, 2012 | Flag Reply
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);
	}
}

- iatbst January 29, 2012 | Flag Reply
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;
	}

- shashi December 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