O(1) random set

Questions 1 to 5 of 7

1. 1. What does this program print? ``python values = [5, 6, 7, 8] positions = {} for i, v in enumerate(values): positions[v] = i index = positions[6] last_index = len(values) - 1 last_value = values[last_index] values[index] = last_value positions[last_value] = index values.pop() del positions[6] print(values, positions[8]) ``

   [5, 6, 7] 1[5, 8, 7] 1[5, 7, 8] 3[8, 5, 7] 0
2. 2. What does this program print? ``python rs = RandomizedSet() rs.insert(10) rs.insert(20) rs.insert(30) rs.remove(10) print(rs.values, rs.positions[30]) ` The RandomizedSet class uses the swap-with-last removal from the lesson, with values as the list and positions` as the dict.

   [20, 30] 1[30, 20, 30] 0[10, 20, 30] 2[30, 20] 0
3. 3. The remove method swaps the removed value with the last item. Which statements about that swap are true? Pick all that apply.

   Pick every answer that is true.

   It copies the last value into the removed value's slotIt shifts every later item one place to the leftIt updates the dict entry of the value that movedIt keeps the list in the same order as before
4. 4. Which operations take constant time on average? Pick all that apply.

   Pick every answer that is true.

   insert, which appends to the list and stores the new index in the dictremove, which swaps with the last item and pops the last slotget_random, which picks a random index and reads that positionrandom.choice on a plain set, which reads a random position from the set
5. 5. Why does get_random() pick a random index into the list instead of a random key from the dict?

   The dict stores its keys in random order, so its first key is a random pickrandom.randrange works only on listsA list lets values[i] jump to any position in constant time, and each index is equally likely, so each value is equally likelyThe list is sorted, so the middle value is the best random pick