tag:blogger.com,1999:blog-76216756426906955442016-06-06T12:53:09.910-07:00Software Engineering interviewsEager Learnerhttp://www.blogger.com/profile/03172303137005153620noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-7621675642690695544.post-21670882590429044882011-06-14T19:12:00.000-07:002014-12-08T02:42:14.883-08:00Software Engineering puzzles<div dir="ltr" style="text-align: left;" trbidi="on"><a href="http://3.bp.blogspot.com/-UV0WHKNxM3U/TfgZu4L1UII/AAAAAAAAEUk/wwhiY0qwdBE/s1600/explanation.JPG" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img alt="" border="0" src="http://3.bp.blogspot.com/-UV0WHKNxM3U/TfgZu4L1UII/AAAAAAAAEUk/wwhiY0qwdBE/s320/explanation.JPG" id="BLOGGER_PHOTO_ID_5618268828291387522" style="cursor: hand; cursor: pointer; display: block; height: 198px; margin: 0px auto 10px; text-align: center; width: 320px;" /></a><br />Yes I am out there again. Looking to convince the right people and groups to hire me. I already work for a big internet company but after 15 years of experience I still have to prove to others (some lesser experienced folks) that I am good enough.<br /><br />In one such interview on the phone, a gentleman began the interview with a probability question. The question was<br />" In an contest between persons <span style="font-weight: bold;">A</span> & <span style="font-weight: bold;">B</span>, consisting of an infinite successive tosses of a two-sided unbiased coin, A bets that his chosen outcomes of Tails, Tails & Heads (<span style="font-weight: bold;">TTH</span>) will prevail whereas B bets that his outcomes of Tails, Heads & Heads (<span style="font-weight: bold;">THH</span>) 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?"<br /><br />Getting this question across the phone itself took 2 minutes of cross questioning from me the candidate.<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />I was sure of my answer. 100% sure! I just wanted the interviewer to know that I knew how to solve probability questions.<br /><br />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<span style="font-style: italic;"> n -> inf </span>(0.5)^n ] = 1.<br /><br />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%.<br /><br />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%.<br /><br />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%.)<br /><br />Thus A wins a probability of 50% + 25% = 75%. It follows that B wins with probability 25% + 25% = 50%.<br /><br />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.<br /><br />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.<br /><br />The program compiled as javac enumerator.java and then run as<br />% java enumerator 2 10<br />spits out<br /><span style="font-weight: bold;"> myMachine 21:00:26 ~ $ java enumerator 2 10</span><br />Enumerating 2 to the power of 10<br />Total Count = 1024<br /><span style="font-weight: bold;">probabilityOfA= 0.7314453125</span><br />probabilityOfB= 0.490234375<br />probabilityOfAandB= 0.2412109375<br />probabilityOfNeitherANorB= 0.01953125<br /><br /><br />and when run with 2^20 gives out<br /><span style="font-weight: bold;">myMachine 21:00:34 ~ $ java enumerator 2 15</span><br />Enumerating 2 to the power of 15<br />Total Count = 32768<br /><span style="font-weight: bold;">probabilityOfA= 0.749114990234375</span><br />probabilityOfB= 0.499542236328125<br />probabilityOfAandB= 0.24957275390625<br />probabilityOfNeitherANorB= 9.1552734375E-4<br /><br />This code can be run for 2^30 as 21:00:34 ~ $ java enumerator 2 30<br />You will see that the answer asymptotically tends to p(A) = 0.75 = 75%<br /><br />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.<br /><br />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."<br /><br />With this I promise that when I am in a position to interview, I will<br />1. Focus on the candidate's strengths more than weaknesses.<br />2. Listen to the candidate clearly.<br />3. Allow the candidate to ask me a puzzle or programming question.<br />4. Not judge candidature on triviality.<br /><br /><br /><pre>class enumerator {<br /> private static int firstNum = 0;<br /> private static int secondNum = 0;<br /> private static int countA = 0;<br /> private static int countB = 0;<br /> private static int countAIntersectB = 0;<br /> private static int countNotAOrB = 0;<br /> private static int totalCount = 0;<br /><br /><br /> private static void usage() { <br /> System.out.println("Exiting... ");<br /> System.exit(-1);<br /> }<br /><br /> public static void main(String[] args) {<br /> if (args.length < 2) {<br /> usage();<br /> }<br /> try {<br /> firstNum = Integer.parseInt(args[0]);<br /> secondNum = Integer.parseInt(args[1]);<br /> System.out.println("Enumerating " + firstNum + " to the power of " + secondNum);<br /> } catch (NumberFormatException e) {<br /> e.printStackTrace();<br /> usage();<br /> }<br /> int fNum = firstNum;<br /> int sNum = secondNum;<br /> doEnumerate(fNum,sNum, new String());<br /> double f = (double)countA/(double)totalCount;<br /> System.out.println("Total Count = " + totalCount);<br /> System.out.println("probabilityOfA= " + f);<br /> f = (double)countB/(double)totalCount;<br /> System.out.println("probabilityOfB= " + f);<br /> f = (double)countAIntersectB/(double)totalCount;<br /> System.out.println("probabilityOfAandB= " + f);<br /> f = (double)countNotAOrB/(double)totalCount;<br /> System.out.println("probabilityOfNeitherANorB= " + f);<br /> }<br /><br /> private static void doEnumerate(int n, int p, String s) {<br /> if (p == 0) {<br /> totalCount++;<br /> //System.out.println(s);<br /> collectProbabilityForTrial(s);<br /> s = new String();<br /> return;<br /> }<br /> for (int i = 0; i < n; i++) {<br /> String ss = s + i;<br /> doEnumerate(n,p-1, ss);<br /> }<br /> }<br /><br /><br /> private static int doesAMatch(String trial) {<br /> String betA = "110";<br /> int count = 0;<br /> for (int i = 0; i < trial.length(); i++) {<br /> if (trial.charAt(i) == betA.charAt(count)) {<br /> count++;<br /> }<br /> if (count == betA.length()) {<br /> return i;<br /> }<br /> }<br /> return -1; //nomatch<br /> }<br /><br /> private static int doesBMatch(String trial) {<br /> String betB = "100";<br /> int count = 0;<br /> for (int i = 0; i < trial.length(); i++) {<br /> if (trial.charAt(i) == betB.charAt(count)) {<br /> count++;<br /> }<br /> if (count == betB.length()) {<br /> return i;<br /> }<br /> }<br /> return -1; //nomatch<br /> }<br /><br /> private static void collectProbabilityForTrial(String trial) {<br /> int aMatch = doesAMatch(trial);<br /> int bMatch = doesBMatch(trial);<br /> <br /> if ((aMatch < 0) && (bMatch < 0)) {<br /> countNotAOrB++;<br /> } else {<br /> if (aMatch < bMatch){<br /> countA++;<br /> } else if (aMatch > bMatch) {<br /> countB++;<br /> } else { //equal<br /> countAIntersectB++;<br /> countA++;<br /> countB++;<br /> }<br /> }<br /> }<br />}</pre></div>Eager Learnerhttp://www.blogger.com/profile/03172303137005153620noreply@blogger.com0