Amazon Interview Question for Software Engineer / Developers






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

Since the array is infinitly increasing i.e. we don't know arrry size in advance, we can't directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach). We can apply reverse of BinarySearch approach.

We can think of sorted infinite 0 and 1 array as infinite size bit stream on disk with 0 set bits followed by 1 bits.

Approach:
Start with first bit, if it is 1 we are lucky and got the switch index, else if it is 0 check the 2,4,8,16,32,64.... 2^n bits till we get first 1 set bit index say its 'i'. Now we have to find between index i/2 to i where the swich happened and this can be done by simple binary search (size of the array to look into is i/2).

Time Complexity: log(N), N is index at which switch happened.

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

Is this some standard algorithm?

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

Thanks :)
Very nice explenation.
Instead of doing binary search on a range of [i/2,i].

we can try to find the first 0 index(x) in a simmiler reverse exponential fasion and keep that as the lower end of the binar search range. [x,i]

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

Really good solution by AK.

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

How is the complexity log(n) ?
shouldn't it be log(n) + log(n/2) .
log(n) - for locating the Nth index and log(n/2) for binary search on n/2 elements?

- sumit March 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If transition exists at position N then it can be found in log(N). Use the strategy of binary search.

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

Why are we jumping using 2^n. We can take any number like 10 or 100 to do this.

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

The answer to your question is: 10 or 100 is just a constant. if the transition point is happening at say 10^10 index, it will take 10^9 operations. too much time complexity.
the best method is the exponential search.

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

yup anonymous we can take a jump of 10 or even 1000
but we have to maintain the two pointers here previos and and current
and if we find 1 in current position just do binary searching between these two pointers

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

the complexity of this solution is O(N/K) where N is the transition point and K is what you said. like 10 or 100 or 1000 or whatever.

Fails when N is much larger than K.

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

do a Ctr + F on 01, you get to the transition position.

:D

- Melvin Gualberto July 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like this one lol.

The actual solution is exponential search with 2 pointers. Say you're searching by 10^i where i = 1,2,3,... and once you hit the first '1' you do a binary search between the two pointers.

The time complexity is as follows:
First you're doing exponential search, so that's ceil(log_10(N)) if you're searching by 10^i where N is actual index of transition. It's ceiling because you're doing 1 search extra that made it hit a '1'. Then the binary search takes log_2(L) where L equals the length between the two pointers. The second pointer is then at ceil(log_10(N)) and the first pointer is at floor(log_10(N)), so the length is the difference between those two. So the overall time complexity is this binary search plus the exponential search.

O(ceil(log_10(N) + log_2(ceil(log_10(N)) - floor(log_10(N)))))

where N is the index of transition.

- alchu July 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey38922" class="run-this"> class Mid0and1
{
static int GetMid0and1(int[] array,int startIndex, int endIndex)
{

if (startIndex == endIndex)
return -1;
if (startIndex+1 == endIndex && array[startIndex] == 0 && array[endIndex] == 1)
return startIndex;
int mid = (startIndex + endIndex) / 2;

if (array[mid] == 0)
return GetMid0and1(array, mid, endIndex);
else
return GetMid0and1(array, startIndex, mid);

}
}</pre><pre title="CodeMonkey38922" input="yes">
</pre>

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

#include<iostream>
using namespace std;
int index=0;
void findtransitionindex(int a[],int min,int max)
{
index+=min;
for(int i=1;i<=max-min;i*=2)
{
if(a[i+index]==1)
{
if(index==i+index-1)
{
index=i+index;
break;
}
min=i/2;
max=i;
findtransitionindex(a,min,max);

}
}
}
int main()
{
int a[10001];
for(int i=1;i<=550;i++)
a[i]=0;
for(int j=551;j<=10000;j++)
a[j]=1;
findtransitionindex(a,0,10000);
cout<<index<<"****";
}

- Anonymous August 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

solution to this problem you can change the values and verify for the same.

#include<iostream>
using namespace std;
int index=0;
void findtransitionindex(int a[],int min,int max)
{
index+=min;
for(int i=1;i<=max-min;i*=2)
{
if(a[i+index]==1)
{
if(index==i+index-1)
{
index=i+index;
break;
}
min=i/2;
max=i;
findtransitionindex(a,min,max);

}
}
}
int main()
{
int a[10001];
for(int i=1;i<=550;i++)
a[i]=0;
for(int j=551;j<=10000;j++)
a[j]=1;
findtransitionindex(a,0,10000);
cout<<index<<"****";
}

- hitesh saini August 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

return 0;

- Anonymous December 27, 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