Probability Interview Questions

Apr 17, 2022 • 2 min read

Basic probability. Counting. Generating random numbers.

#basic-probability

Problem #1.1

How can you generate random numbers 1 to 7 with a single die?

Or more formally, you're given a random integer generator that outputs integers 1 2 3 4 5 6. Describe a procedure that uses this generator to generate a random number between 1 and 7.

Problem #1.2

You're given a procedure random01 that outputs 0 or 1 with equal probability. How can you use it to generate random numbers between 0 and 9?

Problem #1.3

Given a biased coin (ie. heads and tails don't have the same probability), how can you use it to simulate a fair coin toss?

Problem #1.4

There are two balls in a bag. I tell you that at least one of them is red. What is the probability that both are red? (Solution)

Problem #1.5

In how many ways can you divide 12 people into 3 groups of 4?

Problem #1.6

Take 2 random chords of a circle. What is the probability that they intersect?

Laws of probability. Random variables.

Problem #2.1

You have N locks, labeled 1 to N each with a corresponding key. Unfortunately, you lost all the labels from the keys, so you decide to relabel the keys with unique random labels from 1 to N.

What is the expected number of keys that end up with a correct label?

Problem #2.2

You're given an array A of real numbers, sampled from $Uniform(0, 1)$.

Let's consider the following algorithm for finding the maximum of the array:

max := -1
for i in 0 .. length(A) {
	if A[i] > max {
		max := A[i]
   	}
}

What is the expected number of times the max variable will be updated? That is, what is the expected number of times the line max := A[i] is executed?

Problem #2.3

A disease has a base rate of 1 in 1000 (ie. 1 in 1000 people in a population will have the disease). Let's say you take a test that has 97% true positive rate, and 3% false positive rate.

You just tested positive - what is the probability that you actually have the disease?

Problem #2.4

You're drawing cards from a shuffled deck. How many cards do you expect to draw before drawing the first ace?

Probability flavoured algorithms

Problem #3.1

Given a function F(x) returning the value of a cumulative distribution function of a continuous random variable $X$, implement a function sample(F) that returns a sample of $X$.

Problem #3.2

Given a circle centered at $(x, y)$ with radius $r$, implement a function random_point(x, y, r) that returns a random point inside this circle.

Problem #3.4

Given a function Bernoulli() that returns 0 or 1 with equal probability, write a function Normal(mean, std) that returns a random sample from a Normal distribution with mean mean and standard deviation std.