Interview Question for Software Engineer at Facebook:

Permutation + probability, not difficult.

@interview Candidate:
Very smart answer dude! very very smart... :P

public static void calculatePossibility(int n) {
    long total = (int)Math.pow(2, n);

    System.out.printf("%d facing up, possiblity=%3.2f%%\n",0,
      (100.0*1/total));
    double p = 1;

    for (int i=1;i<=n;i++) {
      p = p*(n-i+1)/i;
      System.out.printf("%d facing up, possiblity=%3.2f%%\n",i,100*p/total);
    }

#include<iostream>
#include<vector>
#include<map>
using namespace std;

map<int, vector<vector<bool> > > dp;
double total = 0.0;
int cnt = 0;

vector<vector<bool> > get_prob(vector<double> prob, int indx) {
    if(indx >= prob.size()) return vector<vector<bool> >(1);
    else if(dp[indx].size() != 0) return dp[indx];

    cnt ++;

    vector<vector<bool> > nxt = get_prob(prob, indx+1);
    vector<vector<bool> > cur;

    cout << indx << " " << nxt.size() << endl;

    for(int i = 0; i < nxt.size(); i++) {
        nxt[i].push_back(0);
        cur.push_back(nxt[i]);
        nxt[i][nxt[i].size()-1] = 1;
        cur.push_back(nxt[i]);
    }

    return (dp[indx] = cur);
}

int main() {
    vector<double> prob;

    for(int i = 0; i < 5; i++)
    prob.push_back(0.2);

    vector<vector<bool> > vec = get_prob(prob, 0);

    long double p = 1.0, total = 0.0;
    for(int i = 0; i < vec.size(); i++) {
        p = 1.0;
        for(int j = 0; j < vec[i].size(); j++) {
            cout << vec[i][j] << " ";
            p *= vec[i][j] ? prob[j] : (1-prob[j]);
        }
        total += p;
        cout << " Prob = " << p << endl;
    }

    cout << "Total prob should be 1 : " << total << endl;
}