Amazon Interview Question Software Engineer / Developers
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;
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
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"
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.!
i didn't consider array out of bound intentionally because question says array is infinite(a hypothetical assumption).
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.
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
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..
when you binary search how do you know that the search result is the one at transition point?
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}}
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);
}
}
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);
}
}
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);
}
}
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);
}
}
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;
}
Applying Binary search, we can easily find the answer.
#include <iostream>
using namespace std;
int main()
{
int hi,low,mid,ans;
int arr[] = {1,1,1,1,1,1,1,1,1,1,1};
low = 0;
hi = 10;
while(low<=hi)
{
mid = low + (hi-low)/2;
if(arr[mid] == 1)
{
ans = mid-1;
hi = mid-1;
}
else{
ans = mid;
low = mid+1;
}
}
cout << ans << "\n";
return 0;
}
This can be done by modified binary search.....
- n20084753 July 21, 20111.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..