Exercises

The following exercises provide you with the opportunity to practice with randomization algorithms. The solutions to these exercises are found in the section .

1. Write a function that randomly chooses 3 different values from an array, and returns a brand-new array that contains those 3 values. Ensure that the values appear in the same order as they appeared in the original array.

   For example, if the original array is [7, 1, 5, 2, 9, 0, 3, 6, 4], and the computer selects the 9, 6, and 5 (in that order), we should return [5, 9, 6] since that’s the order in which those three integers appear in the original array.

2. Write a function that randomly chooses a single key from a hash table (in other words, a dictionary, if you’re using Python).

3. Puzzle: There are several simple ways to randomly select a single item from an array, such as using Python’s built-in random.choice method, for example. Another basic approach is to use random.randint to randomly select one index from the array, and return the value at that index.

   However, there’s a clever but more involved approach that can be handy in certain scenarios. I’m only going to describe part of the algorithm, and your challenge is to fill in the rest. The algorithm goes like this:

   We run a loop that iterates over each value in the array. Within each iteration of the loop, we perform a certain computation (which I will not reveal here) to decide whether the value we’re currently pointing to should be the value we’re selecting. If the computation decides to select the current value, we return that value and we’re done. If the computation decides to not select the current value, we simply continue with the next iteration of the loop. If the loop reaches the final item of the array, then that final item becomes the value we’re choosing.

   Your job is to figure out what this certain computation is. The tricky (but tantalizing!) part is to figure out how to ensure that each item has an equal chance of being selected.

4. Puzzle: Devise an algorithm that chooses a random node from a binary search tree. You can assume that the tree is complete (that is, a tree whose levels are entirely full), like this one:

   

   To make this exercise more challenging, make sure that the function runs in O(log N) time and doesn’t consume any extra space.