Prompt and applicable context
The set must test membership, insert, delete, and return a current element uniformly at random. A hash map provides lookup while a dynamic array provides random indexing; deleting a middle element is the conflict.
What the interviewer evaluates
- Combining a hash map and an array instead of forcing one structure to do everything.
- Maintaining a value-to-array-index map and updating it after every swap.
- Understanding average O(1) and amortized array growth.
- Defining uniform getRandom and duplicate-value semantics.
- Handling empty sets, missing deletes, and concurrency boundaries.
Clarifying questions before answering
- Are values unique? Duplicates require mapping a value to a set of indices.
- Must getRandom be uniform, or may it return any random member? The acceptance test changes.
- Is O(1) amortized average or strict worst case? Hash collision policy changes the promise.
- Does the API return values or handles? Mutable objects need equality and hashing rules.
- Are thread safety, fixed memory, or reproducible randomness required?
30-second answer framework
“I keep an items array and an indexOf hash map. Insert appends a new value and records its index; getRandom samples a uniform array index. Remove finds the target index, moves the last element into that slot, updates the moved element’s index, pops the array, and deletes the target mapping. That avoids an O(n) shift. Hash operations and dynamic-array growth are average amortized O(1); an empty set returns the agreed error, and duplicates require an index-set mapping.”
Step-by-step deep dive
Step 1: Establish the invariant. For every value v, indexOf[v] points to its unique location in items; the array has no holes and every index is in range.
Step 2: Implement insert. If the map already contains the value, return false as specified. Otherwise append it and store the new index in average O(1).
Step 3: Implement remove. Read target index i and last index last. If i !== last, write the last value to items[i] and change its map entry to i; then pop the last slot and delete the target entry.
Step 4: Implement getRandom. Sample a uniform index from a non-empty array. Python’s choice documentation defines equal-probability sequence selection; hash iteration order is not a randomness guarantee.
Step 5: State complexity. Hash lookup, append, swap, and pop are average amortized O(1); array and map space are O(n). Worst-case hash collisions or resize pauses need separate SLO discussion.
Step 6: Handle duplicates. Change indexOf[v] to a set of indices. When removing one instance, remove its index and apply the same tail swap while updating both index sets.
Step 7: Verify boundaries. Test an empty set, one item, repeated deletes, deleting the tail, repeated growth, and a fixed seed. Run many getRandom calls to check frequencies, not only membership.
Model answer
“I store current values in an array and each value’s array index in a hash map. To delete a middle item, I move the tail item into its slot, update that item’s index, and pop the tail, so no elements shift. getRandom reads a uniformly selected array index, making each unique value equally likely. The O(1) claim is average amortized for hash operations and dynamic-array growth; if duplicates are allowed, I replace the single index with an index set and define deletion as removing one instance.”
Common mistakes
- Using only a hash map → getRandom scans every key → add a compact array.
- Shifting after deletion → delete becomes O(n) → swap with the tail.
- Forgetting the moved value’s index → later deletes target the wrong slot → treat the map update as part of the swap.
- Sampling a hash iterator → iteration order is not a uniform guarantee → sample an array index.
- Calling average O(1) worst-case O(1) → collisions and resize costs are ignored → state the amortized assumptions.
Follow-up questions and responses
Follow-up 1: What happens when deleting the last array element?
The target index equals the tail index, so pop it and delete its map entry without a swap.
Follow-up 2: How do you support duplicates?
Map each value to an index set. After moving the tail, remove its old index, add the new index, and remove one index from the target set.
Follow-up 3: How do you prove getRandom is uniform?
Each current instance occupies one array position, and the index is uniform over 0..n-1; unique values therefore occupy one equally likely position each.
Follow-up 4: Can hash collisions break O(1)?
Average complexity depends on load factor and hash quality. Strict worst-case guarantees need treeified buckets, randomized hashing, or another structure.
Follow-up 5: How do you handle concurrent reads and deletes?
Protect random-index reads and delete swaps with one lock or a version check; otherwise a reader can observe a popped index.
Follow-up 6: How do you test the distribution?
Run many trials on a fixed set, count each value, set a statistical tolerance, and also assert every returned value remains present.