Amazon Interview Question
InternsCountry: India
Interview Type: In-Person
Assuming given array is sorted which means there will be series of 0's followed by 1's.
Recursive solution :
///
find_Zero_count(A,i,j)
{
if(i==j)
{
if(A[i] == 0)
return 1
else
return 0
mid = i+(j-i)/2;
if(A[mid]==0)
{
return (j-i)/2+1+find_zero_count(A, mid+1, j)
}
else
{
return find_zero_count(A,i, mid-1)
}
}
\\\
Simple binary search.
Recursive solution:
int zero_count(array, start, end)
{
if (start == end)
{
if (array[start] == 0)
{
return start;
}
else
{
return start - 1;
}
}
else
{
mid = (start + end) / 2;
if (array[mid] == 0)
{
return zero_count(array, mid + 1, end);
}
else
{
return zero_count(array, start, mid);
}
}
}
Iterative solution:
int zero_count(array, len)
{
start = 0;
end = len - 1;
while (start < end)
{
mid = (start + end) / 2;
if (array[mid] == 0)
{
start = mid + 1;
}
else
{
end = mid;
}
}
if (array[start] == 0)
{
return start;
}
else
{
return start - 1;
}
}
Not sure if your code is right.. Try out
zero_count(new int[] { 0 }, 0, 0);
zero_count(new int[] { 0, 1 }, 0, 1);
zero_count(new int[] { 0, 1, 1 }, 0, 2);
zero_count(new int[] { 0, 0, 1 }, 0, 2);
zero_count(new int[] { 0, 0, 0, 0, 0, 1 }, 0, 5);
zero_count(new int[] { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 }, 0, 9);
zero_count(new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1 }, 0, 12);
If the array is very large (e.g. stream) then binary search is not efficient. Use the following:
1) Check the value at the following points 1,2,4,8,16,32,64..... till you encounter 1
2) Now the first 1 would be in the last block e.g if A[64] is 1 then the first 1 will lie between 32 and 64
3) Perform binary search in the block (or repeat the same procedure till block size is 1)
public static int FindNumberOfZeroes(int[] array, int s, int e)
{
if (s > e)
return 0;
if (s == e)
return array[s] == 0 ? 1 : 0;
int m = s + (e - s) / 2;
if (array[m] == 1)
{
if (m > 1 && array[m - 1] == 0)
return m;
return FindNumberOfZeroes(array, s, m - 1);
}
else
{
if (m < array.Length - 1 && array[m + 1] == 1)
return m + 1;
return FindNumberOfZeroes(array, m + 1, e);
}
}
I think, following will work too.
#Recusive
public int CountZerosRecursive(int[] input, int start, int end)
{
if (input.Length <= 0 || (start > end)) return 0;
int mid = (start + end) / 2;
if (input[mid] == 0)
return (mid-start +1) + CountZerosRecursive(input, mid + 1, end);
else
return CountZerosRecursive(input, start, mid - 1);
}
#Iterative
public int CountZerosIterative(int[] input)
{
if (input.Length <= 0) return -1;
int start = 0;
int end = input.Length - 1;
int mid = 0;
int count = 0;
while(start < end)
{
mid = start + end / 2;
if (input[mid] == 0)
{
count = count + (mid - start + 1);
start = mid + 1;
}
else
{
end = mid - 1;
}
}
return count;
}
// recursive solution
public static int zeros(int[] array, int min, int max){
int mid = (min+max)/2;
if(mid == 0){
return array[mid]== 0 ? 1 : 0;
}
if(array[mid] == 1){
if(array[mid-1]==0)
return mid;
return zeros(array,min, mid-1);
}
else {
return zeros(array, mid+1, max);
}
}
// iterative solution
public static int zeros(int[] array){
int len = array.length;
int start = 0;
int end = len-1;
int mid;
do{
mid = (start + end)/2;
if(mid==0){
return array[mid]==0 ? 1 : 0;
}
if(array[mid]==1){
if(array[mid-1]==0)
return mid;
end = mid -1;
}else{
start = mid +1;
}
}while(mid > 0);
return 0;
}
Using Recursion:
This is a pretty straightforward way to get to the solution.
I am exploiting two very important facts. #1 It is sorted zeros than ones. #2 You'll need to study it figure it out.
I ran a few different test cases and it passed all.
This is my first post so please prove me wrong.
int zero_count_recursive(int array[], int low, int high){
int mid = (low+high)/2;
if(array[mid] == 0){
low = mid;
return zero_count_recursive(array, mid, high);
}
else {
if(array[mid-1] == 0){
return mid;}
else{
high = mid;
return zero_count_recursive(array,low, high);
}
}
}
..If you can't figure some ghetto way to solve this problem using iteration...I can't help you. Sorry.
public static int countZeroRecursion (int[] arr, int i) {
if(i >= arr.length) return 0;
if(arr[i] == 1) return 0;
return 1 + countZeroRecursion(arr, ++i);
}
public static int countZeroIterative (int[] arr) {
int sum = 0;
for(int i=0; i<arr.length; i++) {
if(arr[i] == 0) ++sum;
else
break;
}
return sum;
}
static void wrapperSortedArray0s1s(int a[]) {
int k = sortedArray0s1s(a, 0, a.length - 1);
System.out.println(k);
if (k == 0) {
System.out.println("0's = 0");
System.out.println("1's = " + a.length);
} else if (k == a.length - 1) {
System.out.println("0's = " + a.length);
System.out.println("1's = 0");
} else {
System.out.println("0's = " + (k + 1));
System.out.println("1's = " + (a.length - k - 1));
}
}
static int sortedArray0s1s(int a[], int l, int u) {
int m = (l + u) / 2;
if (m >= a.length - 1 || m <= 0)
return m;
if (a[m] == 0 && a[m + 1] > 0)
return m;
else if (a[m] > 0)
return sortedArray0s1s(a, l, m - 1);
else
return sortedArray0s1s(a, m + 1, u);
}
- varun.me15 January 17, 2015