In an interview on the phone, the interviewer began the interview with a probability question. The question was
" In an contest between persons A & B, consisting of an infinite successive tosses of a two-sided unbiased coin, A bets that his chosen outcomes of Tails, Tails & Heads (TTH) will prevail whereas B bets that his outcomes of Tails, Heads & Heads (THH) will prevail. The outcomes need to be in order for either person to win but does not have to be contiguous. What is the probability that A wins?"
Getting this question across the phone itself took 2 minutes of cross questioning from me the candidate.
I attempted the question and came close to giving my verdict but the interviewer thought we should move on. The next question was a standard producer consumer synchronization question followed by cache design for zeroing in on word search and a few more system design related questions. Quite in the air.
At the end, the interviewer & I spoke about the group and were about to sign off when I asked if the interviewer had a few seconds to discuss the probability question that we had passed on from.
We discussed the answer and I explained that the probability of A winning is 75% vs the probability of B winning is 50% therefor P(A & B winning) is 25%. The guy seemed impressed. All this was at 10:00 pm through 11:00 pm.
I was sure of my answer. 100% sure! I just wanted the interviewer to know that I knew how to solve probability questions.
To prove my answer, I drew a simple possibilities tree (see image) . My thought process was that in an infinite coin toss, the probability of getting at least one Tail is 100% . Mathematically, the probability of encountering at least one tail is [ 1 - lim n -> inf (0.5)^n ] = 1.
That said I began with a Tail at my root node. Infinite heads before that are pointless since both A's wager and B's wager begin with a Tail(T). Then I took the two routes independently. If a Tail follows the first Tail (with probability 50%) A is bound to win. You on the 2nd coin toss after the root Tail, if we see a Head, A wins. If we see a Tail we toss the coin again. One will argue what if you get infinite Tails (TTT....T....T) and the answer is: somewhere down the line you will get a Head(TTH encountered). So A's chances so far are at least 50%.
Now for the case of Head(TH so far) following the root Tail occurs with probability 50%. We cant make conclusive decisions at this stage so we have to toss the coin again. If a Head comes in the coin toss after seeing a Tail(root) followed by Head(right subtree), B wins. Thus so far B has the chance of winning 25% (because H after T is 50% , and H again would be another 50% therefor by multiplicative law 0.5 * 0.5 = 0.25 = 25%.
Now we are left with the case THT. In this case if an H comes, both A & B win. If T comes, we try again. The probability of getting a Head in infinite unbiased coin's toss is 1 (same limit argument). So THTH, THTTH, THTTTH etc.. means that A & B win. This part of the tree follows the THT already occurred which gives it a probability of 25% (multiplicative law 0.5 * 0.5 = 0.25 = 25%.)
Thus A wins a probability of 50% + 25% = 75%. It follows that B wins with probability 25% + 25% = 50%.
So I am all convinced and now ready to brag to a good friend of mine who was a manager of a big internet company himself in an online ad serving team. This buddy has worked in the best of positions at Microsoft, Yahoo and other big companies.
On hearing the problem, my friend pointed me to http://www.qbyte.org/puzzles/p013s.html page saying that this was a well known problem. Obviously my friend had not comprehended the problem that was asked to me. After hours of heated argument and a code proof (Snippet at the very bottom in java) he was shown how I proved my answer using simple programmatic enumeration.
The program compiled as javac enumerator.java and then run as
% java enumerator 2 10
spits out
myMachine 21:00:26 ~ $ java enumerator 2 10
Enumerating 2 to the power of 10
Total Count = 1024
probabilityOfA= 0.7314453125
probabilityOfB= 0.490234375
probabilityOfAandB= 0.2412109375
probabilityOfNeitherANorB= 0.01953125
and when run with 2^20 gives out
myMachine 21:00:34 ~ $ java enumerator 2 15
Enumerating 2 to the power of 15
Total Count = 32768
probabilityOfA= 0.749114990234375
probabilityOfB= 0.499542236328125
probabilityOfAandB= 0.24957275390625
probabilityOfNeitherANorB= 9.1552734375E-4
This code can be run for 2^30 as 21:00:34 ~ $ java enumerator 2 30
You will see that the answer asymptotically tends to p(A) = 0.75 = 75%
I did not get the job but the problem was interesting. I also recently decided to "prove to myself my own worth" by completing a moderate level test in game playing evaluation. The coding site is https://www.hackerrank.com/challenges/permutation-game . I started out with just plain min-max with the hope to later transform this into Alpha-Beta Pruning but later realized something even better. Many states of the game were being re-evaluated. So a simple HAshMap with stored states and outcomes as well as usage of Arrays.hashCode() proved very handy.
A wise man once said "If the interviewer wants to give you a job, he will ask your dad's name whereas if he does not want to give you a job, he will ask you his dad's name which you dont know."
With this I promise that when I am in a position to interview, I will
1. Focus on the candidate's strengths more than weaknesses.
2. Listen to the candidate clearly.
3. Allow the candidate to ask me a puzzle or programming question.
4. Not judge candidature on triviality.
class enumerator {
private static int firstNum = 0;
private static int secondNum = 0;
private static int countA = 0;
private static int countB = 0;
private static int countAIntersectB = 0;
private static int countNotAOrB = 0;
private static int totalCount = 0;
private static void usage() {
System.out.println("Exiting... ");
System.exit(-1);
}
public static void main(String[] args) {
if (args.length < 2) {
usage();
}
try {
firstNum = Integer.parseInt(args[0]);
secondNum = Integer.parseInt(args[1]);
System.out.println("Enumerating " + firstNum + " to the power of " + secondNum);
} catch (NumberFormatException e) {
e.printStackTrace();
usage();
}
int fNum = firstNum;
int sNum = secondNum;
doEnumerate(fNum,sNum, new String());
double f = (double)countA/(double)totalCount;
System.out.println("Total Count = " + totalCount);
System.out.println("probabilityOfA= " + f);
f = (double)countB/(double)totalCount;
System.out.println("probabilityOfB= " + f);
f = (double)countAIntersectB/(double)totalCount;
System.out.println("probabilityOfAandB= " + f);
f = (double)countNotAOrB/(double)totalCount;
System.out.println("probabilityOfNeitherANorB= " + f);
}
private static void doEnumerate(int n, int p, String s) {
if (p == 0) {
totalCount++;
//System.out.println(s);
collectProbabilityForTrial(s);
s = new String();
return;
}
for (int i = 0; i < n; i++) {
String ss = s + i;
doEnumerate(n,p-1, ss);
}
}
private static int doesAMatch(String trial) {
String betA = "110";
int count = 0;
for (int i = 0; i < trial.length(); i++) {
if (trial.charAt(i) == betA.charAt(count)) {
count++;
}
if (count == betA.length()) {
return i;
}
}
return -1; //nomatch
}
private static int doesBMatch(String trial) {
String betB = "100";
int count = 0;
for (int i = 0; i < trial.length(); i++) {
if (trial.charAt(i) == betB.charAt(count)) {
count++;
}
if (count == betB.length()) {
return i;
}
}
return -1; //nomatch
}
private static void collectProbabilityForTrial(String trial) {
int aMatch = doesAMatch(trial);
int bMatch = doesBMatch(trial);
if ((aMatch < 0) && (bMatch < 0)) {
countNotAOrB++;
} else {
if (aMatch < bMatch){
countA++;
} else if (aMatch > bMatch) {
countB++;
} else { //equal
countAIntersectB++;
countA++;
countB++;
}
}
}
}
