Probability shortlist

Cosmin Negruseri
18 iunie 2014

Here's a set of probability problems. Try to solve them in the comments section.

  1. (von Neumann’s biased coin) You’re given a biased coin. It falls heads with an unknown probability p and tails with the probability 1 - p. Can you come up with a way to generate fair 0 and 1 results?
  2. A rand5() function gives uniform integer results between 1 and 5. How can you use it to build a rand7() function? (microsoft interview)
  3. Build a function rand(x, y, r) that returns a uniformly random point in the circle given by the (x,y) center and the r radius. (dropbox interview)
  4. Build an algorithm that returns a uniform random permutation of numbers 1 to n. (google interview)
  5. (Reservoir sampling) Given a stream of integers build an algorithm that returns a uniform random sample of size k using O(k) memory. (google interview)
  6. (Coupon collector’s problem) Suppose a kid wants to collect all the cartoon characters in a kinder surprise series. Given that there are n different characters in total and they are distributed uniformly random. What's the average number of kinder eggs he has to buy so that the selection is complete. (twitter interview)
  7. (Balls and bins problem) m balls are thrown into n bins. Each ball has 1/n probability of falling into each bin. What’s the expected number of empty bins? (twitter interview)
  8. What’s the average number of times line 4 is executed if p is a random permutation of numbers 1 to n. (pinterest interview)
min = p[0]
 for x in p:
   if min > x:
     min = x
remote content