Facebook Interview Question
Software Engineer / DevelopersCountry: 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;
}