Quiz — Combining Data Structures

A set keeps its items in an array and each item's index in a hash map, so that it can pick a random item in O(1). How does it delete an item in O(1)?

Mark its slot as empty and leave the gap

Move the last item into the slot and remove the last slot, leaving the map as it is

Move the last item into the deleted item's slot, update that item's index in the map, and remove the last slot

Remove it from the array and shift every later item left