Amazon Interview Question for Interns

Country: India
Interview Type: In-Person

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

``````package careercup;

public class CC5716548811489280 {

public static int findZeros(int[] input,int count,int start,int end){
//System.out.println("Start"+ start);
//System.out.println("End"+ end);
if(start>end){
return count+1;
}
int mid = (end + start)/2;
//System.out.println("mid" + mid);
if(input[mid] == 0){
count = mid;
return findZeros(input,count, mid+1, end);
}else{
return findZeros(input, count,start, mid-1);
}

}

public static void main(String[] args){
int[] array = {0,0,0,0,0,0,1,1,1,1,1};
System.out.println(findZeros(array, 0,0, array.length - 1));
}
}``````

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

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)
}

}
\\\

Comment hidden because of low score. Click to expand.
0

``````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)
}
}``````

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

public int returnZero(int[] arr,int num,int i,int count)
{
if (i >= num) return count;
if (arr[i] == 0) count++;
else
i = num;
return returnZero(arr, num, ++i, count);
}

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

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;
}
}``````

Comment hidden because of low score. Click to expand.
0

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);

Comment hidden because of low score. Click to expand.
0

this will correct.

``````if (array[start] == 0)
{
return start + 1;
}
else
{
return start ;
}``````

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

Just use a binary search technique to find the first index of 1 in the array. Then return this index as the number of zeroes in the array

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

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)

Comment hidden because of low score. Click to expand.
0

Its inefficient algo if an array has max no of 0's than 1's.
ex:- array contains all 0's except the last number?

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

``````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);
}
}``````

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

public int numberOfOsInArray(int[] arrA){

return numberOf0(arrA, arrA.length-1);
}

private int numberOf0(int[] arrA, int i) {
if(arrA[i]==0){
return i+1;
}else{
return numberOf0(arrA,i-1);
}
}

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

``````#include<stdio.h>
#include<stdlib.h>

int count(int a[],int n)
{
int i;
int count=0;
if(a[0]==0)
{
while(a[i++]!=1)
{
count++;
}
return count;
}
else
{
while(a[i++]!=0)
{
count++;
}
return n-count;
}

}

main()
{
int a[10]={0,0,0,0,1,1,1,1,1,1};
printf("%d",count(a,10));
}``````

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

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;
}``````

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

O(n) recursive solution:

numzero(0 to n)= 1+numzero(1 to n)

int zerocount(array, startindex)
{
if(array[startindex]==1) return 0;
else
return 1+zerocount(array,startindex+1);
}

}

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

``````public static void findNo1s(Integer[] array) {
Integer sum = 0;
for(int i =0; i<array.length && array[i] != 0;i++) {
sum += array[i];
}
System.out.println(" No of 1s = "+sum+ " no od 0s ="+(array.length-sum));
}``````

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

``````// 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;
}``````

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

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.

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

``````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;
}``````

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

``````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);
}``````

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.

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.