Amazon Interview Question
Software Engineer / DevelopersTeam: Kindle-Periodicals
Country: India
Interview Type: In-Person
/*
Find the position of first '1' in a sorted array that contains only 0-s and 1-s
*/
#include<stdio.h>
#include<stdlib.h>
int BST(int a[],int i,int j)
{
if(i<=j)
{
int mid=(i+j)/2;
if((a[mid]==1&&mid==0)||(a[mid]==1&&a[mid-1]==0))
return mid;
else if(a[mid]==0)
return BST(a,mid+1,j);
else
return BST(a,i,mid-1);
}
return -1;
}
int main()
{
int a[]={0,0,0,0,0,0,1,1,1,1,1,1,1,1};
int n=sizeof(a)/sizeof(a[0]);
printf("%d",BST(a,0,n-1));
return 0;
}
We can provide a linear solution to this, I am not sure about the advantage we achieve by using a BST.
{
main()
{
int i = 0, ar[]={0,0,0,0,1,1,1,1,0,0}, arr_length = 0;
int start_1, end_1;
bool start_is_set = false, end_is_set = false;
arr_length = sizeof(a)/sizeof(a[0]);
for(i = 0; i < arr_length; i++)
{
if(start_is_set == false)
{
if(a[i] ==1)
{
start_1 = i;
start_is_set = true;
}
}
if(end_is_set == false)
{
if(a[length - i]==1)
{
end_1 = length-i;
end_is_set = true;
}
}
if(end_is_set && start_is_set)
{
break;
}
}
}
}
int findFirstOne(int *arr, int len)
{
if ( arr == NULL || len < 1 )
return -1;
if ( arr[0] == 1 ) // if array order is decreese, first item is answer.
return 0;
//binary search.
int i=0;
int j = len - 1;
while ( i < j)
{
int mid = i + (j-i)/2;
if ( arr[mid] == 1)
{
j = mid;
}
else
{
i = mid+1;
}
}
return arr[j] ? j : -1; // if this array don't have 1, return -1.
}
use binary search till you get 1 and even after getting 1 continue your searching until you find NO 1 , and return the last position of 1 you saw. This will give the position of first 1 in the sorted array. using binary search.
- harish_venkat March 18, 2012