## Facebook Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Written Test

How about this?

```
int minNumberOfBalls(int c,int b, int p){
double targetprob=(double)p/100;
double containerprob=(double)1/c;
int min=0;
if(b<c)
min=c-b;
int w=(int)(targetprob/containerprob);
return Math.max(w, min);
}
```

Fix to consider the number of white balls in the box that will have all black balls. The operations may be further simplified.

```
int minNumberOfBalls(int c,int b, int p){
double targetprob=(double)p/100;
double containerprob=(double)1/c;
int min=0;
if(b<c)
min=c-b;
int w1=(int)(targetprob/containerprob);
double remainingprob=targetprob-containerprob*w1;
int w2=(int)(Math.ceil(remainingprob*b/(1-remainingprob)/containerprob));
return Math.max(w1+w2, min);
}
```

still output some wrong answer

for this input

10

70 70 70

65 50 58

51 51 60

47 47 61

50 51 69

55 61 66

42 39 63

45 46 58

55 62 60

63 68 62

the o/p must be

49

38

31

29

35

37

27

27

33

40

your code produce some wrong results

Thanks for the data set for testing. I had the feeling there were some mistakes but didn't have time to check it carefully.

```
int minNumberOfBalls(int c,int b, int p){
if(p==100)
return Integer.MAX_VALUE;
double targetprob=(double)p/100;
double containerprob=(double)1/c;
int min=0;
if(b<c)
min=c-b;
int w1=(int)(targetprob/containerprob);
double remainingprob=(targetprob-containerprob*w1)*containerprob;
int w2=(int)(Math.ceil(remainingprob*b/(1-remainingprob)));
return Math.max(w1+w2, min);
}
```

I could not understand why do you have following condition

:

if(p==100)

return Integer.MAX_VALUE;

ideally it should be

if(p=100) return C;

I hadn't noticed they could give you zero black balls.

Actually it should be:

```
if(p==100)
if(b==0)
return c;
else
return Integer.MAX_VALUE;
```

If they give you at least a single black ball and expect 100% of probability to get a white ball then that scenario is not possible; there will be always a possibility to get the black ball. That's why it returns the MAX_VALUE (like stating infinite number of white balls); you could throw an exception if you want too.

worked against examples provided above.

This should be a bin search and greed problem.

given W white balls. The best solution is to make the num of containers have one and only on white ball maxmized. see code:

```
def bestRatio(C,B,W):
if (B+W<C) :return -1
singleWhite=min(W,C-1)
singleBlack=C-1-singleWhite
firstBlack=B-singleBlack
firstWhite = W-singleWhite
return 1.0/C*firstWhite/(firstWhite+firstBlack)+ \
1.0/C * singleWhite
def minWhite(C,B,P):
left=1
right=B*100
P=P*0.01
while (left<right):
mid=(left+right)/2
best = bestRatio(C,B,mid)
if best >= P-1e-6:
right=mid
elif best < P:
left=mid+1
return left
n=10
cases=map(lambda x:int(x),'''
70 70 70
65 50 58
51 51 60
47 47 61
50 51 69
55 61 66
42 39 63
45 46 58
55 62 60
63 68 62'''.split()
)
for i in range(n):
print minWhite(cases[i*3],cases[i*3+1],cases[i*3+2])
raw_input('ps')
```

This code works fine:

W=0;

if(C==1)

{

while(W*100<P*(B+W))W++;

}

else

{

W=C*P%100;

if(C*P%100==1)W++;

}

if(W+B<C)W+=C-(W+B);

return W;

correction:

W=0;

if(B==0)W=1;

else if(C==1)

{

while(W*100<P*(B+W))W++;

}

else

{

W=C*P%100;

if(C*P%100!=0)W++;

}

if(W+B<C)W+=C-(W+B);

return W;

For the third test case 10 2 50.

Can't we put 10Black balls + 1 white ball in first container and 1 white ball in second container

So the probability of selecting a white ball is

(1/2)*(1/11) + (1/2)*(1/1)

=0.045 + 0.5

=0.545

which is greater than 0.5

Did i understand the question properly?

/* Enter your code here. Read input from STDIN. Print output to STDOUT */

#include<iostream>

#include<math.h>

#include <stdio.h>

#include <limits.h>

using namespace std;

int minNumberOfBalls(int c,int b, int p){

if(p==100)

return INT_MAX;

double targetprob=(double)p/100;

double containerprob=(double)1.0/c;

int min=0;

if(b<c)

min=c-b;

double w1=(targetprob/containerprob);

double remainingprob=(targetprob-containerprob*(int)w1)*containerprob;

double w2=((double)remainingprob*b/(double)(1.0-remainingprob));

return max((int)(ceil(w1)+(w2)), min);

}

int main()

{

int N;

cin>>N;

int c,b,p;

while(N--)

{

cin>>c>>b>>p;

cout<<minNumberOfBalls(c,b,p)<<"\n";

}

}

```
#include<math.h>
#include<stdio.h>
int minBalls( int containers, int bBalls, int prob )
{
int min_wBalls = 0;
if ( containers == 0 || bBalls == 0 ) {
return containers;
}
if(containers > bBalls)
{
min_wBalls = containers - bBalls;
}
double dprob = (double)prob/100;
int wBalls = ceil (((min_wBalls*(dprob - 1)) + (bBalls * dprob))/(1 - dprob));
wBalls = min_wBalls + wBalls;
if((wBalls + bBalls) < containers)
{
wBalls = wBalls + (containers - (wBalls + bBalls));
}
return wBalls;
}
int main()
{
printf("\t%d", minBalls(1,1,60));
printf("\t%d",minBalls(2,1,60));
printf("\t%d",minBalls(10,2,50));
}
```

#include<stdio.h>

#include<math.h>

int main()

{

float diff,c,b,p,w=0,p1;//b=blackball,c=container,w=whiteball

printf("enter containers , black ball and probability");

scanf("%f%f%f",&c,&b,&p);

if(c>b)

w=c-b;

p1=(1/c)*w;

if(p1<p)

{

diff=p-p1;

w=c-1+((b*diff)/(1-diff));

w= ceil(w);

printf("Number of white balls required====%f",w);

}

else

printf("Number of white balls required====%f",w);

return 0;

}

#include<stdio.h>

#include<math.h>

int main()

{

float diff,c,b,p,w=0,p1;//b=blackball,c=container,w=whiteball

printf("enter containers , black ball and probability");

scanf("%f%f%f",&c,&b,&p);

if(c>b)

w=c-b;

p1=(1/c)*w;

if(p1<p)

{

diff=p-p1;

w=c-1+((b*diff)/(1-diff));

w= ceil(w);

printf("Number of white balls required====%f",w);

}

else

printf("Number of white balls required====%f",w);

return 0;

}

This works for all the test cases.

```
import java.io.*;
public class Solution {
public static void main(String[] args) {
BufferedReader reader;
int t, c, b;
double p;
int[] result = null;
try {
reader = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(reader.readLine());
result = new int[t];
// input
for(int i=0; i<t; i++) {
String[] input = reader.readLine().split(" ");
c = Integer.parseInt(input[0]);
b = Integer.parseInt(input[1]);
p = Double.parseDouble(input[2]) / 100;
// compute result
result[i] = (int)(c == 1 ? Math.ceil((p * b) / (1 - p)) : Math.max((c - b), Math.ceil(c * p)));
}
// output
for(int i=0; i<t; i++)
System.out.println(result[i]);
reader.close();
} catch (IOException ioex) {
System.err.println(ioex);
}
}
}
```

Try this:

```
int minNumberOfBalls(int c,int b, int p){
double dp=(double)p/100;
int min=0;
if(b<c)
min=c-b;
int w=(int)Math.ceil((dp*b)/(1-dp));
return Math.max(w, min);
}
```

How did you get 49?

Starting with P<= W/(B+W), where P and B are given, it is easy to solve for W >= (P*B)/(1-P), as above. Which gives you the bare min number for W...so now if B+W < C, then W is increased so that B+W = C to make sure each container has at least one ball, which is a slight change to the above.

I think the only case in which you need to increase W is if the total number of balls is less than the number of containers. As long as the total ratio between B & W balls hold, doesn't matter which containers hold what - each container gets selected with probability of 1/C, so over many trials it is the total ratio that matters. Or am I missing something?

int minBalls( int containers, int bBalls, int pct ) {

if ( containers == 0 || bBalls == 0 ) {

return containers;

}

double dbl_pct = (double) pct /100;

int min_wBalls = ceil ( ( double ) containers * pct / 100 );

while ( min_wBalls + bBalls < containers ) {

min_wBalls++;

}

return min_wBalls++;

}

You don't need to do the last while. You can just do the difference containers - bBalls.

//test cases above passed

- wy_nojob March 02, 2012#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

int main()

{

int T;

long long C,B,P;

scanf("%d",&T);

while(T--)

{

scanf("%lld %lld %lld",&C,&B,&P);

if(100==P)

{

if(0==B)cout << C << endl;

continue;

}

if(100*(C-1)<=P*C)

cout << (C-B-1+(int ((double(100*B))/(double((100-P)*C))))) << endl;

else

cout << int (ceil((double(C*P)/100))) << endl;

}

return 0;

}