## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

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

//test cases above passed
#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;
}

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

test cases above failed

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

Are you sure this question was asked in an onsite interview ?
This looks like a Facebook programming contest question.

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

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

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

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

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

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

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

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

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

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

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;

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

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;

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

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.

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

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

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

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;

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

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;

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

can you please explain second test case given in question?

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

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?

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

10,2,50 --> C,B,P

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

/* 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";
}
}

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

That seems to work perfectly, but I'm not sure that I understand the math.

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

Dear Monty,
I didn't understand the following part of the code

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

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

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

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

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

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

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

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

This works for all the test cases.

``````import java.io.*;

public class Solution {
public static void main(String[] args) {
int t, c, b;
double p;
int[] result = null;

try {
result = new int[t];

// input
for(int i=0; i<t; i++) {
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]);

} catch (IOException ioex) {
System.err.println(ioex);
}
}
}``````

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

the number of minimal required white balls is simply ceil(P*C/100)

Notice here P is percentage.

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

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

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

in this case
70 70 70
your output is 164 but the correct or the minimum is 49

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

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?

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

Sorry, that is exactly what the above code does...

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

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

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

Correction:
return min_wBalls;

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

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

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

This doesn't seem to work when there are more than enough black balls per cup. Try C=1, B=10, P=50

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.