Briefly discuss the approach you would take to the following programming scenarios. Make any assumptions you need to. There are no “right” answers for any of these questions.

1. The data structure grabbag is similar to a stack or a queue, but instead of the first or last element being removed on a pop or dequeue, a random element is removed on a grab. Grabbags are very useful for simulating random draws without repetition, like drawing cards from a deck or numbers in a bingo game. Consider the following ADT:

Grabbag:

Insert(item e): e is inserted into the grabbag

Grab(): if the grabbag is not empty, return a random element from the grabbag

Size(): return how many items are in the grabbag

List(): return a list of all items in the grabbag

Describe how you would implement a grabbag. Discuss the time complexities of each of the operations.

Ideas Presented:

Unsorted Stretchy Array:

- Insert item at end of array, stretching array if necessary. O(1) amortized cost.

- Grab item by picking a random slot in the array. Fill slot by moving the end element to the empty spot. O(1) time.

- Uses a small amount of memory. Very fast inserts.

- Grab requires call to random number generator which could be bad.

Circular linked list

- With each insert, move the current pointer ahead some amount of nodes and insert there.

- With each grab, move the current pointer ahead some amount of nodes and grab that item.

- These amounts could be part of a previously generated random list that you just cycle through.

- For a fixed insert and grab pattern, there is little randomness. However, if inserts and grabs are intermeshed in varying patterns, the result will be strongly pseudorandom.

- Inserts and grabs are still constant time without a call to the number generator.

- Extra memory needed for pointers.