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

- wy_nojob March 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

test cases above failed

- Anonymous April 02, 2012 | Flag
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.

- Jhunter March 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Mau February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mau February 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mau February 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain your logic?

- Anonymous June 03, 2012 | Flag
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;

- Anonymous February 17, 2012 | Flag Reply
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;

- Anonymous February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Mau February 17, 2012 | Flag
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')

- LatiosWang March 25, 2012 | Flag Reply
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;

- Manohar Singh May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- Anonymous May 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please explain second test case given in question?

- Abhishek July 16, 2012 | Flag
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?

- Srikanth May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- abh007 July 29, 2012 | Flag
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";
}
}

- monty June 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dadakhalandhar May 01, 2013 | Flag
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));
}

- Anonymous July 18, 2012 | Flag Reply
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;
}

- Anonymous May 01, 2013 | Flag Reply
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;
}

- sunilkumar kunapareddy and Rahul Voruganti May 01, 2013 | Flag Reply
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) {
        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);
        }
    }
}

- Vinoth Kumar Kannan December 31, 2013 | Flag Reply
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.

- Anonymous September 22, 2017 | Flag Reply
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);
}

- Mau February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous June 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 06, 2012 | Flag
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++;
}

- Anonymous February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction:
return min_wBalls;

- Anil February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- chris February 21, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More