Facebook interview questions?

Question

I have a phone screening with Facebook scheduled next week. What kind of questions might they ask?

Answer 1

Here is a pretty detailed Facebook interview breakdown.

Answer 2

Was asked this phone interview question:

S=max score

individual points p1,p2,...,pn

how many permutations of p1,...,pn (multiple occurences of px allowed) give us total score S.

This is essentially based on American football, where each drive can end in 2 points (safety), 3 points (field goal), 6 points (td) or 7 points (td+fg).

Example:

S=47

p1=2,p2=4,p3=7

Answer: 226234 permutations

3,3,3,3,7,7,7,7,7,:(126 permutations)

3,3,3,3,3,3,3,3,3,3,3,7,7,:(78 permutations)

2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,:(16 permutations)

2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,:(2380 permutations)

2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,:(31824 permutations)

2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,:(92378 permutations)

2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,:(77520 permutations)

2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,:(20349 permutations)

2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,:(1540 permutations)

2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,:(23 permutations)

Count = 226234

High Level Solution:

Assume p1,...,pm is sorted with p1 min and pm max. Let p0=0

Let:

Rmax = S/p1

Rmin = S/pm

Let: T be a number in radix n with up to Rmax digits.

Initialize T With Rmin rightmost digits each set to 1.

Max = A number with Rmax rightmost digits each set to m.

While T <= Max

Compute sum += p[Ti], where Ti corresponds to value of digit at position i in T

if sum == S

    subPermutationCount = D!/(D1!*D2!*...*Dn!)

                        Where D= number of non-zero digits in T

                              D1=Number of 1's in T

                              D2=Number of 2's in T

                              ....

                              Dn=Number of n's in T

   Add subPermutationCount to Overall Perm Count

Increment T as follows:

If T has any 1s, set rightmost 1 to 2

    else

  If T has any 2s, set rightmost 2 to 3

else

  ...

 If T has any (n-1)s, set rightmost n-1 to n

   else

      Set rightmost 0 to 1

      Set all digits to the right following this 1 to 1

EndLoop

Here is the full program in C code: Enjoy!:

static int
max_compare(int *t, int l, int r){
 int i;
 for(i=0; i < l ; i++)
        if(t[i] != r-1)
                return 0;
return 1;
}

static void
increment(int *t, int l, int r) {
int carry=0;
int sum;
int i,j,re;
for(re=1;re<r-1;re++){
for(i=l-1; i>= 0; i--) {
        if(t[i]==0)
                break;

        if(t[i] == re){
                t[i]++;
                return;
                }
}
}
out:
for(j=i;j<l;j++)
                t[j] = 1;
return;
}

static unsigned long long
factorial(int n, int c) {
int i;
unsigned long long fac=1;
for(i=n;i>c;i--)
        fac*=i;
return fac;
}

static unsigned long long
permut(int *t, int l, int r) {
int max=0;
int maxc=0;
int *counts;
int i;
unsigned long long perm;
counts = (int *)malloc(r*sizeof(int));
for(i=0;i<r;i++)
        counts[i]=0;
for(i=l-1;i>=0;i--){
        if(t[i]==0)
                break;
        //printf("%d", t[i]);
        counts[t[i]]++;
        if(counts[t[i]] > maxc)
                maxc=counts[t[i]];
}
max=l-i-1;
perm = factorial(max, maxc);
//printf("\nmax=%d maxc=%d perm=%lld\n", max, maxc,perm);
for(i=1;i<r;i++) {
        //printf("counts[%d]=%d\n", i,counts[i]);
        if(counts[i] != maxc)
        perm /= factorial(counts[i],1);
}
free(counts);
//printf("Actual perm = %lld\n", perm);
return perm;
}

int
main(int argc, char **argv){

int *t;
int p[4] = {0,2,3,7};
int nonzero = 0;
int i,k,sum;
int N=47;
int kmax=3;
int kmin=1;
int radix=4;
unsigned long long count = 0;
int rmax;
int rmin;
for(rmin=1;rmin<47;rmin++)
        if(rmin*p[kmax] > N)
                break;
for(rmax=1;rmax<47;rmax++)
        if(rmax*p[kmin] > N)
                break;
//printf("Max digits needed = %d\n", rmax);
//printf("Min digits needed = %d\n", rmin);
t = (int *)malloc(rmax*sizeof(int));

for(i=0;i<rmax;i++) {
        t[i]=0;
}

for(i=rmax-1;i>rmax-rmin-1;i--) {
        t[i]=kmin;
}

while(!max_compare(t, rmax, radix)) {
        sum=0;
        nonzero = 0;
        for(i=0;i<rmax;i++){
        if(nonzero && t[i] == 0)
                        break;

        if(t[i])
                nonzero=1;
        else
                continue;
        sum+=p[t[i]];
        }
        if(sum == N) {
                count+=permut(t,rmax,radix);
                for(k=0;k<rmax;k++)
                        if(t[k])
                        printf("%d,",p[t[k]]);
                printf(":(%lld permutations)\n", permut(t,rmax,radix));
                }
        increment(t,rmax,radix);
}
printf("Count = %lld\n", count);
}

Answer 3

s=47 p1=2,p2=4,p3=7 my result is 271405. I can not tell where is wrong of mine, and I've test it with small numbers that I can verified by hands.

Answer 4

As an undergrad student, one of the questions I was asked in a phone interview was how to find whether two events with start and end times and dates overlapped. They provided a real time place to type on their website, where both the reviewer and I could see what I was writing. I made commented notes as I went along, and the reviewer seemed satisfied.

This question actually came up again during the on-campus interviews. (Stupidly?) I told them I already had answered that question.

A good one they asked another candidate was, given two (maybe three?) bowling balls and a 100 story building, what is the fewest number of drops to the ground that you can find the floor that the bowling ball will break on? That's a good thinker of a problem, and they're not so much looking for a specific answer as how you think about the question.

Answer 5

Answer to the question below: 15 Drop balls from levels 10,24,37,49,60,70,79,87,94 and 100 levels. If ball breaks at any level out of these, go to the previous level in the list and drop the other ball from previous+1, previous+2 and so on until it breaks. The level so obtained is the required level.

Answer 6

Answer for 2 balls is 14

Answer 7

For the ball problem (I posted as a separate answer since it doesn't give me enough comment space as a reply):

The answer is 14 drops:

The idea is that you start at a low floor and continue dropping from higher and higher floors (maybe jumping 10 floors at a time), until it breaks. Then you can go back 10, and try each floor progressively until you find the one that it is on. What you must consider, however, is that with each jump of 10 floors, you are losing guesses. So you will have to jump 10 floors, then 9 floors, then 8 floors, etc... all the way down to 1 in order to make up for that loss. You need that sum to be able to reach all of the floors up to 100. So essentially, you must find the lowest number, k, such that sum(1 to k) >= 100. It is generally known that the sum(1 to k) = (k^2 + k) / 2. So if we set: (k^2 + k) / 2 = 100, we get that k is about 14.

Now let's verify the answer of 14:

So the answer we arrived at is this: you drop the ball at floor 14. If it breaks, you try floor 1, 2, 3... etc. Leaving at most 14 attempts. If it doesn't break, you drop the ball at 14 + one less (13) = 27. If it breaks, you drop the ball from 15, 16, 17... etc up to 26. So if it can be dropped from a max of, say, 26, then you'd have to guess: 14, 27, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26. That's still 14 guesses. If it didn't break at 27, you'd move on to 27 + 12 = 39. You should be able to see how this idea will hold throughout all of the jump floors: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99. And if it doesn't break at 99, then it either breaks at 100 or doesn't break at all, so you'd test that.

Answer 8

I'm getting 271405 as well with this code:

#include <iostream>
using namespace std;

int size = 3;
int score = 47;
int p[3] = { 2, 4, 7 };
int n[3] = { 0, 0, 0 };
int x[3] = { 0, 0, 0 };
int total_permutations = 0;

unsigned long long factorial(int n, int m)
{
    unsigned long long r = 1;
    for (int i = m + 1; i <= n; i++)
        r *= i;
    return r;
}

void eval_permutation(int index)
{
    if (index < size)
    {
        for (int i = 0; i < n[index]; i++)
        {
            x[index] = i;
            eval_permutation(index + 1);
        }
    }
    else
    {
        // check if p1*x1+p2*x2+p3*x3=score.
        int y = 0;
        for (int i = 0; i < size; i++)
            y += p[i] * x[i];
        if (y == score)
        {
            // x! / x1! * x2! * x3! ... numbers get large so compute x!/xn! for largest xn first.
            int count = 0;
            int max_count_index = 0;
            for (int i = 0; i < size; i++)
            {
                count += x[i];
                if (x[max_count_index] < x[i])
                    max_count_index = i;
            }
            unsigned long long permutations = factorial(count, x[max_count_index]);
            for (int i = 0; i < size; i++)
                if (max_count_index != i)
                    permutations /= factorial(x[i], 1);

            for (int i = 0; i < size; i++)
                cout << x[i] << " ";
            cout << " = " << permutations << endl;

            total_permutations += permutations;
        }
    }
}

int main()
{
    for (int i = 0; i < size; i++)
        n[i] = score / p[i];
    eval_permutation(0);
        cout << total_permutations << endl;
    return 0;
}

output:

0 3 5  = 56
0 10 1  = 11
1 6 3  = 840
2 2 5  = 756
2 9 1  = 660
3 5 3  = 9240
4 1 5  = 1260
4 8 1  = 6435
5 4 3  = 27720
6 0 5  = 462
6 7 1  = 24024
7 3 3  = 34320
8 6 1  = 45045
9 2 3  = 20020
10 5 1  = 48048
11 1 3  = 5460
12 4 1  = 30940
13 0 3  = 560
14 3 1  = 12240
16 2 1  = 2907
18 1 1  = 380
20 0 1  = 21
271405

Answer 9

Single while loop:

#include <iostream>
using namespace std;

unsigned long long factorial(int n, int m)
{
    unsigned long long r = 1;
    for (int i = m + 1; i <= n; i++)
        r *= i;
    return r;
}

int main()
{
    int size = 3;
    int score = 47;
    int p[3] = { 2, 4, 7 };
    int max[3] = { 0, 0, 0 };
    int x[3] = { 0, 0, 0 };
    int total_permutations = 0;

    for (int i = 0; i < size; i++)
        max[i] = score / p[i];

    while (x[0] < max[0])
    {
        // next permutation.
        for (int i = size - 1; i >= 0; i--)
        {
            x[i]++;
            if ((i == 0) || (x[i] < max[i]))
                break;
            x[i] = 0;
        }

        // check if p1*x1+p2*x2+p3*x3=score.
        int y = 0;
        for (int i = 0; i < size; i++)
            y += p[i] * x[i];
        if (y == score)
        {
            // x! / x1! * x2! * x3! ... numbers get large so compute x!/xn! for largest xn first.
            int count = 0;
            int max_count_index = 0;
            for (int i = 0; i < size; i++)
            {
                count += x[i];
                if (x[max_count_index] < x[i])
                    max_count_index = i;
            }
            unsigned long long permutations = factorial(count, x[max_count_index]);
            for (int i = 0; i < size; i++)
                if (max_count_index != i)
                    permutations /= factorial(x[i], 1);

            // print permutation.
            for (int i = 0; i < size; i++) 
                cout << x[i] << " ";
            cout << "= " << permutations << endl;

            total_permutations += permutations;
        }
    }

    cout << total_permutations << endl;
    return 0;
}

Answer 10

As far as the question about the permutation, I think all answers given above are wrong. I think you are counting the cases where only two scores are allowed, but unless I missed it, I don't think this restriction applies.

For exapmle, the following sequence would work as well: 7, 7, 7, 7, 7, 7, 3, 2 (which has 56 permutations) All in all, I counted 1,540,427

My algorithm is much simpler. I'll show below the specific case of 2, 3, 7:

Let: phi(x) = number of permutations that gives a total scores of N with Two, Three and Seven.

For x>0 the following recursion rules apply:

phi(x) = phi(x-2) + phi(x-3)

Here is the program in C++. Note the print line is just for the demonstration of the algorithm.

#include <iostream>

int Phi[48];

void wmain( )
{
    for( int i=0; i<=47; ++i ) {
        Phi[i] = -1;
    }
    phi( 47 );
}

int phi( int x )
{
    if( x < 0 ) {
        return 0;
    } else if( x == 0 ) {
        return 1;
    } else if( Phi[x] != -1 ) {
        return Phi[x];
    } else {
        int r = phi(x-2) + phi(x-3) + phi(x-7);
        cout << "phi(" << x << ") = " << r << endl;
        Phi[x] = r;
        return r;
    }
}

The output of this program is:

phi(1) = 0
phi(3) = 1
phi(2) = 1
phi(5) = 2
phi(4) = 1
phi(7) = 4
phi(6) = 2
phi(9) = 7
phi(8) = 4
phi(11) = 12
phi(10) = 9
phi(13) = 23
phi(12) = 18
phi(15) = 45
phi(14) = 34
phi(17) = 88
phi(16) = 64
phi(19) = 170
phi(18) = 121
phi(21) = 325
phi(20) = 232
phi(23) = 621
phi(22) = 447
phi(25) = 1189
phi(24) = 860
phi(27) = 2281
phi(26) = 1651
phi(29) = 4379
phi(28) = 3165
phi(31) = 8404
phi(30) = 6067
phi(33) = 16122
phi(32) = 11635
phi(35) = 30922
phi(34) = 22320
phi(37) = 59309
phi(36) = 42821
phi(39) = 113765
phi(38) = 82147
phi(41) = 218232
phi(40) = 157578
phi(43) = 418631
phi(42) = 302265
phi(45) = 803043
phi(44) = 579806
phi(47) = 1540427