Randomized Multiset

What's being tested

This tests the array-plus-hash-map pattern for supporting duplicate values with expected O(1) insert, remove, and random selection. You must maintain index bookkeeping correctly so deleting an arbitrary occurrence does not break uniform sampling or leave stale references.

Patterns & templates

• Store every occurrence in a dynamic array; choose randomIndex = randomInt(0, len(items) - 1) for uniform O(1) sampling.

• Map each value to a set of indices; duplicates therefore remain distinct while insert and lookup stay expected O(1).

• Remove in O(1) by swapping the target with the final array element, updating both values’ index sets, then popping.

• For frequency-weighted sampling, sample array positions rather than distinct keys; a value appearing k times receives probability k / n.

• Use a stored index from the value’s index set; avoid scanning for an occurrence, which silently changes removal to O(n).

• Handle the swapped element carefully when removing the final element itself; update its index only after determining whether indices coincide.

• State complexity precisely: expected O(1) operations, O(n) space, with hash-table worst cases depending on collision behavior.

Common pitfalls

Pitfall: Sampling from distinct keys makes values equally likely instead of making each stored occurrence equally likely.

Pitfall: Removing from the array without deleting and relocating index metadata leaves stale indices and causes later operations to corrupt state.

Pitfall: Assuming deterministic O(1) hash-map performance; describe expected complexity and mention resizing or adversarial-collision considerations when relevant.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.