Problem: Build a Bag

We will build a bag, which is a collection you can add things to and draw things from, but order does not matter. A bag is like a dynamic array, but it does not have a first or last element. You can add items to it, and you can draw an item out at random. The bag does not guarantee which item you will get when you draw, only that it will be one of the items in the bag.

This is the structure behind the urn from probability, a jar of colored balls that you draw from without looking. (See Wikipedia’s entry for “Urn problem” if you are curious.) The mix of balls in the urn determines the odds, so if the urn is mostly blue, you are more likely to draw blue. You can add more balls of either color, and that changes the odds.

The Bag has the following three operations:

• add(ball) — put a ball in, growing the backing array if it is full.
• remove() — draw a ball out at random and return it.
• size() — report how many balls are in the bag.

A working solution is provided in the accompanying code for this practice problem. It includes a demo that fills the bag with a known mix of balls, then draws a ball and puts it back thousands of times. The fraction of blue balls drawn comes out close to the true fraction of blue balls in the bag. That is a check that the random draw really is uniform over the balls.