Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Pair dense storage with direct lookup: The Random Vault.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Randomized set matches the clues
- 2Keep this true after every move: the map index of every stored value matches its array position
- 3Reach the result within O(1) average insert, remove, and pick
Rules and pressure
- Target cost: O(1) average insert, remove, and pick
- State rule: the map index of every stored value matches its array position
Lesson 1 of 3
Live algorithm trace
Randomized set
Complete execution1 of 5
0
insert 1
op
1
insert 2
2
remove 1
3
pick
4
remove 2
Insert 1 at dense index zero.
1
array stores every value densely2
map value to array index3
insert only when absent4
remove by swapping with the last value5
repair the swapped value index6
pick a uniform random array indexarray = [1]map = 1->0
Truth to preserve / Cost target
Truth to preserve
the map index of every stored value matches its array position
Cost target
O(1) average insert, remove, and pick
An array supports uniform random indexing. A map locates any value, and deletion swaps the final array item into the removed slot before popping.
Your call · What should guide every step of this algorithm?