Google's test conducted at IIT-Bombay consisted of 20 objective questions, which were of moderate difficulty level. It also had a subjective question which goes as follows.
You are given a number of dices n, each with a number of faces m. You roll all the n dices and note the sum of all the throws you get from rolling each dice. If you get a sum >= x, you win, otherwise you lose. Find the probability that you win.
Google's shortlist for final rounds of interviews consisted of only those people who had done relatively well on the test, and fortunately I was one of them. So now you know how important it is to do well on the test.
You are given a number of dices n, each with a number of faces m. You roll all the n dices and note the sum of all the throws you get from rolling each dice. If you get a sum >= x, you win, otherwise you lose. Find the probability that you win.
Google's shortlist for final rounds of interviews consisted of only those people who had done relatively well on the test, and fortunately I was one of them. So now you know how important it is to do well on the test.
Hello, my friend, I can solve this problem with O(N*X) running time and O(N*X) spaces.I believe there must be a better solution. Do you mind to provide your solution?
ReplyDeleteAn approximate solution would be
ReplyDelete0.5*[1-2*(x-n(m+1)/2)/sqrt(2*n*(m^3-1))]
Note that is not the exact solution. The exact solution cannot be computed by hand, but the approximate solution can, and should be accurate to within a few percent.
@waterloonian I was able to do it using O(m*n*x) space in O(n*x) time. How did you arrive at a solution with O(n*x) complexity?
ReplyDelete