Amazon Interview Question
Software Engineer / DevelopersThanks :)
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]
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
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.
<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>
#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<<"****";
}
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<<"****";
}
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.
- AK July 02, 2011We 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.