Random

Problem Assume you have access to a function toss_biased() which returns 0 or 1 with a probability that’s not 50-50 (but also not 0-100 or 100-0). You do not know the bias of the coin. Write a function to simulate an unbiased coin toss. Solution Method 1 - Using Probability To simulate an unbiased coin toss using a biased coin, we can use a clever trick that leverages pairs of results. Specifically, we can use the pair (0, 1) and (1, 0) to generate unbiased results. The idea is that these pairs are equally likely to occur, regardless of the bias of the original coin. ...

Problem Write a method to shuffle a deck of cards. It must be a perfect shuffle – in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect. OR How can you shuffle an array in O(n) time and O(1) space? For example, if input is an array of (1, 2, 3, 4, 5), one of the output can be (5, 4, 3, 2, 1) or (4, 2, 3, 1, 5). ...

Problem Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. (i.e., implement rand7() using rand5()). OR Using a function rand5() that returns an integer from 1 to 5 (inclusive) with uniform probability, implement a function rand7() that returns an integer from 1 to 7 (inclusive). Solution This appear to be one of those probabilistic analysis questions. You should be familiar with the concept of expected value, as it could be extremely helpful in probabilistic analysis. ...

Problem Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability. Solution This is a classic problem known as Reservoir Sampling. The goal is to randomly select an element from a large stream of data with uniform probability, even when the entire stream cannot be stored in memory. Introduction to Problem Reservoir sampling, often referred to as Algorithm R as described by Jeffrey Vitter in Random Sampling with a Reservoir, is a widely used technique in data processing. It allows for the random selection of k samples from a set S containing n items, where n is very large or unknown. Each of the chosen k items forms a “reservoir,” ensuring that every item is selected with an equal probability of 1/n. ...