What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 180 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

12. Swap-with-Last Delete: Insert Delete GetRandom O(1) (LC 380) • Invariant Proof & Speed-Run

Theory Context•Advanced Data Structures

MediumLC 380

Insert Delete GetRandom O(1) (LeetCode 380)

You will see how moving the last value into a removed value's slot keeps the list gap-free, so a random pick stays uniform.

Target Frequency:AmazonGoogleMeta

Build a class, RandomizedSet, that stores a set of distinct integers and can hand back one of them at random. Every operation has to take O(1) time on average.

RandomizedSet() creates an empty set.
bool insert(int val) adds val if it is missing. It returns true when val was added and false when it was already there.
bool remove(int val) deletes val if it is there. It returns true when val was deleted and false when it was not in the set.
int getRandom() returns one of the stored values, chosen so that every value in the set at that moment is equally likely.

Worked Examples

Example 1

Input:

["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]

Output:[null,true,false,true,2,true,false,2]

Explanation: `insert(1)` adds 1. `remove(2)` returns `false`: 2 is not stored. `insert(2)` adds 2, so the set is `{1, 2}` and the first `getRandom()` may return 1 or 2, each with probability 1/2 (LeetCode shows 2). `remove(1)` leaves `{2}`, `insert(2)` returns `false` because 2 is already stored, and the last `getRandom()` can only return 2.

⚖️Formal Constraints & Bounds

-2³¹ <= val <= 2³¹ - 1
At most 2 * 10⁵ calls are made to insert, remove and getRandom altogether.
getRandom is only called when the set holds at least one value.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

A list gives a uniform random pick but only deletes its last slot in O(1), so delete by moving the last value into the hole and recording its new slot in the map: the list stays gap-free and every value keeps exactly one slot.

Real-World Scenario & Production Applications

A load balancer that sends each request to a random healthy server, a game that picks a random live enemy, or a sampler that draws a random active user all need to add and drop members constantly and pick one at random with equal chances. A hash set can't pick at random without copying itself; a packed array with a value-to-slot map does all three in O(1).

Step-by-Step Execution Trace Table

The debugger's first preset (the trap case: remove(2) while 2 is the last value):

Call	`self.values` after the call	`self.index` after the call	Returns	What happened
`RandomizedSet()`	`[]`	`{}`	`null`	An empty set
`insert(1)`	`[1]`	`{1: 0}`	`true`	1 takes slot 0
`insert(2)`	`[1, 2]`	`{1: 0, 2: 1}`	`true`	2 takes slot 1
`insert(3)`	`[1, 2, 3]`	`{1: 0, 2: 1, 3: 2}`	`true`	3 takes slot 2
`remove(1)`	`[3, 2]`	`{2: 1, 3: 0}`	`true`	`i = 0`, `last = 3`: 3 moves into slot 0, `self.index[3] = 0`, then `pop()`
`remove(2)`	`[3]`	`{3: 0}`	`true`	`i = 1` and `last = 2`: 2 is the last value. `self.index[2] = 1`, then `del self.index[2]`. Deleting first would write `2: 1` back
`insert(2)`	`[3, 2]`	`{3: 0, 2: 1}`	`true`	With a stale `2: 1` left in the map, this would return `false`
`remove(3)`	`[2]`	`{2: 0}`	`true`	`i = 0`, `last = 2`: 2 moves into slot 0
`getRandom()`	`[2]`	`{2: 0}`	`2`	`random.choice([2])`: the only value

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	A random pick where every value is equally likely needs the values packed in a list with no gaps, and a list only deletes its last slot in O(1): so fill a removed value's slot with the last value.
2	Keep this true: `self.values` holds each value once with no gaps, and `self.index[v]` is the slot of `v`. Every `remove` has to leave both true.
3	`insert`: return `False` if `val in self.index`, else record `self.index[val] = len(self.values)` and append. `remove`: `i = self.index[val]`, `last = self.values[-1]`, `self.values[i] = last`, fix the map, `pop()`. `getRandom`: `random.choice(self.values)`.
4	The trap: write `self.index[last] = i` before `del self.index[val]`. When `val` is the last value, `last == val`, and the other order puts `val` back in the map.

Target: Insert Delete GetRandom O(1) (LeetCode 380). Every stored value sits in one slot `0 .. n - 1`, with no holes, so `random.choice` gives each a 1-in-n chance.

Boundary Model: Trie Prefix Tree Branching / DSU Near-Flat Forest

Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.

Loop Invariant Termination

Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

A hash set inserts and removes in O(1), but it can't hand back a uniformly random member: it has no positions to pick from. A list can: random.choice(self.values) picks each slot 0 .. n - 1 with the same chance. But a list only removes its last slot in O(1); removing from the middle shifts everything after it. Insert Delete GetRandom keeps both: the list for the random pick, and a map self.index from each value to its slot. To remove val, don't close the gap by shifting: move the last value into val's slot, record that value's new slot in self.index, and pop the end. A set has no order, so moving one value changes nothing a caller can see.

🅿️ The Analogy: A Car Park With Numbered Bays

A car park fills its bays in order from bay 0, and a notebook says which bay each car is in. To pick a car at random, draw a bay number from 0 to n - 1: every bay is full, so every car has the same chance. When the car in bay 3 leaves, you don't move every later car forward one bay: you drive the car from the last bay into bay 3, correct its line in the notebook, and the last bay is free. If the leaving car is the one in the last bay, it "moves" into its own bay, so correct the notebook first and cross the leaving car out second, or you write it straight back in.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

i = self.index[val]
last = self.values[-1]
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()

After these lines self.values is still gap-free and every stored value still has exactly one slot, so random.choice stays uniform. The order of the two map writes only matters when val is the last value: then last == val, the write self.index[last] = i touches val's own entry, and del self.index[val] removes it right after. In the other order, delete then write, the write puts val back into the map.

💡 Summary

The list gives the random pick, the map gives the slot. insert records the slot and appends; remove fills the hole with the last value, updates that value's slot, deletes val's entry and pops; getRandom is random.choice(self.values). $O(1)$ average per call, $O(N)$ space.

Deleting before updating: del self.index[val] followed by self.index[last] = i is wrong when val is the last value (last == val): the write puts val back at a slot that pop() removes, so a later insert(val) returns false. Update self.index[last] first, then delete.
Forgetting the moved value: after self.values[i] = last, the map must say self.index[last] = i; otherwise it still points at the old last slot, and removing last later fills the wrong slot.
Popping before filling the hole: last = self.values.pop() and then self.values[i] = last raises IndexError when val was in the last slot. Fill the hole first, pop last.
Removing from the middle: self.values.remove(val) or self.values.pop(i) shifts every later value: O(N) per call, about 10¹⁰ steps at these limits, and every shifted slot in self.index goes stale.
A biased pick: random.randint(0, len(self.values) - 2) never returns the last value, and self.values[0] is not random at all. random.choice(self.values) gives each slot, and so each value, a 1-in-n chance.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots an O(1) random pick next to O(1) deletes and defends the swap-with-last delete out loud.

Pattern Recognition Signals

The 10-second spot

"Return a random element" with "every element equally likely", next to insert and remove "in average O(1) time": a uniform pick needs the values packed in an array, and removing by value in O(1) needs a map from value to slot. A set has no order, which is the signal that a value may be moved: Insert Delete GetRandom, delete by moving the last value into the hole.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

self.values holds every stored value exactly once with no gaps, and self.index[v] is the slot of v in self.values. insert records self.index[val] = len(self.values) and appends; remove moves last into slot i, sets self.index[last] = i, deletes self.index[val] and pops.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Write self.index[last] = i before del self.index[val]: when val is the last value, last == val, and deleting first writes val back into the map at a slot that pop() removes, so a later insert(val) returns false.
Update the moved value's slot at all: without self.index[last] = i, the map still says last sits at the end, and removing it later fills the wrong slot.
Fill the hole before self.values.pop(): popping first and then writing self.values[i] fails when i was the last slot, which no longer exists.
Never self.values.remove(val) or self.values.pop(i) from the middle: both shift the rest of the list, O(N), and every shifted value's slot in self.index goes stale.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use the Insert Delete GetRandom design: an array plus an index map. A pick where every value is equally likely needs the values packed in an array, so getRandom is random choice over it, and a map from each value to its slot makes insert and the lookup in remove O(1). The hard part is deleting from the middle of the array in O(1). A set has no order, so I move the last value into the removed value's slot, record that value's new slot in the map, delete the removed value's entry and pop the end. The array stays gap-free, so every value keeps exactly one slot and the same chance. The trap is the order of the two map writes: when the removed value is itself the last one, updating first and deleting second is right, while deleting first writes it straight back into the map. Every call is O(1) on average, and the space is O(N).

So: a gap-free list for the pick, a map for the slot, and on remove update self.index[last] before deleting self.index[val].

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(1) average per call

Look at each method. insert does one map lookup (val in self.index), one map write and one append. remove does one lookup, reads self.values[-1], writes one list slot, writes one map entry, deletes one map entry and pops the end of the list: nothing shifts. getRandom draws one random index and reads one slot. Map operations are O(1) on average (hashing), and append and pop() at the end of a Python list are amortized O(1), so every call is O(1) on average and a run of Q calls costs O(Q).

SPACE COMPLEXITY

O(N)

self.values and self.index each hold one entry per stored value: O(N) for N values. No recursion, and no call builds a temporary list.

Formal Recurrence Relation

T(Q) = Q · O(1) = O(Q) for Q calls (average)

Derivation Progression

insert

O(1) average

One lookup val in self.index, one map write self.index[val] = len(self.values), one append at the end of the list.

remove

O(1) average

One lookup, one read of self.values[-1], one slot write self.values[i] = last, one map write, one del, one pop() at the end: nothing shifts.

getRandom

O(1)

random.choice(self.values) draws one index and reads one slot.

Total

O(Q)

Constant average work per call over Q calls.

Variable Definitions

$N$

Number of values in the set, len(self.values)

$Q$

Number of calls to insert, remove and getRandom (at most 2 * 10⁵)

Memory Architecture & Bounds

🟣 Call Stack

O(1) No recursion

🔵 Auxiliary Heap

O(N): one list slot and one map entry per stored value

🟢 Output Space

O(1) per call: one boolean or integer

Boundary Best / Worst Cases

Best Case

$O(1)$ per call

Average Case

$O(1)$ per call

Worst Case

$O(N)$ for one call when every value hashes to the same bucket, or when the list grows its buffer; O(1) amortized over a run

Recurrence Tree Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "return a random element", "every element equally likely", "average O(1)" for insert and remove. A uniform pick needs the values packed in an array; deleting by value in O(1) needs a map from value to slot: Insert Delete GetRandom, an array plus an index map, deleting by moving the last value into the hole.

CONSTRAINTS & BOUNDS

Up to $2 \cdot 10^5$ calls, values in $[-2^{31}, 2^{31} - 1]$ . A hash set alone can't pick uniformly without copying itself into a list ( $O(N)$ per getRandom); a list alone removes in $O(N)$ (search, then shift), up to about $10^{10}$ steps. Array plus map: $O(1)$ average per call for $O(N)$ memory.

FAANG PRODUCTION TRAPS & EDGE CASES

Removing the last value: write self.index[last] = i before del self.index[val], because then last == val. If several threads share the set, remove changes two slots and two map entries, so it must run as one critical section: a getRandom between the move and the pop can see the moved value twice. Python's dict is O(1) on average, not in the worst case.

Core Algorithmic State Invariants

1. One Slot per Value, No Gaps

`self.values` holds every stored value exactly once with no holes, and `self.index[v]` is the slot of `v`, so `random.choice(self.values)` gives each value a 1-in-n chance.

2. Update, Then Delete

`remove` moves `last` into slot `i`, writes `self.index[last] = i` and only then runs `del self.index[val]`. When `val` is the last value, `last == val`, and the other order writes `val` back into the map.

3. O(1) on Average

No call walks the list: a few map operations, one slot write and one `append` or `pop()` at the end. Every call is O(1) on average, for one list slot and one map entry per value: O(N) space.

Theory Context•Advanced Data Structures

MediumLC 380

Insert Delete GetRandom O(1) (LeetCode 380)

You will see how moving the last value into a removed value's slot keeps the list gap-free, so a random pick stays uniform.

Target Frequency:AmazonGoogleMeta

Build a class, RandomizedSet, that stores a set of distinct integers and can hand back one of them at random. Every operation has to take O(1) time on average.

RandomizedSet() creates an empty set.
bool insert(int val) adds val if it is missing. It returns true when val was added and false when it was already there.
bool remove(int val) deletes val if it is there. It returns true when val was deleted and false when it was not in the set.
int getRandom() returns one of the stored values, chosen so that every value in the set at that moment is equally likely.

Worked Examples

Example 1

Input:

["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]

Output:[null,true,false,true,2,true,false,2]

⚖️Formal Constraints & Bounds

-2³¹ <= val <= 2³¹ - 1
At most 2 * 10⁵ calls are made to insert, remove and getRandom altogether.
getRandom is only called when the set holds at least one value.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Step-by-Step Execution Trace Table

The debugger's first preset (the trap case: remove(2) while 2 is the last value):

Call	`self.values` after the call	`self.index` after the call	Returns	What happened
`RandomizedSet()`	`[]`	`{}`	`null`	An empty set
`insert(1)`	`[1]`	`{1: 0}`	`true`	1 takes slot 0
`insert(2)`	`[1, 2]`	`{1: 0, 2: 1}`	`true`	2 takes slot 1
`insert(3)`	`[1, 2, 3]`	`{1: 0, 2: 1, 3: 2}`	`true`	3 takes slot 2
`remove(1)`	`[3, 2]`	`{2: 1, 3: 0}`	`true`	`i = 0`, `last = 3`: 3 moves into slot 0, `self.index[3] = 0`, then `pop()`
`remove(2)`	`[3]`	`{3: 0}`	`true`	`i = 1` and `last = 2`: 2 is the last value. `self.index[2] = 1`, then `del self.index[2]`. Deleting first would write `2: 1` back
`insert(2)`	`[3, 2]`	`{3: 0, 2: 1}`	`true`	With a stale `2: 1` left in the map, this would return `false`
`remove(3)`	`[2]`	`{2: 0}`	`true`	`i = 0`, `last = 2`: 2 moves into slot 0
`getRandom()`	`[2]`	`{2: 0}`	`2`	`random.choice([2])`: the only value

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	A random pick where every value is equally likely needs the values packed in a list with no gaps, and a list only deletes its last slot in O(1): so fill a removed value's slot with the last value.
2	Keep this true: `self.values` holds each value once with no gaps, and `self.index[v]` is the slot of `v`. Every `remove` has to leave both true.
3	`insert`: return `False` if `val in self.index`, else record `self.index[val] = len(self.values)` and append. `remove`: `i = self.index[val]`, `last = self.values[-1]`, `self.values[i] = last`, fix the map, `pop()`. `getRandom`: `random.choice(self.values)`.
4	The trap: write `self.index[last] = i` before `del self.index[val]`. When `val` is the last value, `last == val`, and the other order puts `val` back in the map.

Target: Insert Delete GetRandom O(1) (LeetCode 380). Every stored value sits in one slot `0 .. n - 1`, with no holes, so `random.choice` gives each a 1-in-n chance.

Boundary Model: Trie Prefix Tree Branching / DSU Near-Flat Forest

Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.

Loop Invariant Termination

Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🅿️ The Analogy: A Car Park With Numbered Bays

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

i = self.index[val]
last = self.values[-1]
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()

💡 Summary

Deleting before updating: del self.index[val] followed by self.index[last] = i is wrong when val is the last value (last == val): the write puts val back at a slot that pop() removes, so a later insert(val) returns false. Update self.index[last] first, then delete.
Forgetting the moved value: after self.values[i] = last, the map must say self.index[last] = i; otherwise it still points at the old last slot, and removing last later fills the wrong slot.
Popping before filling the hole: last = self.values.pop() and then self.values[i] = last raises IndexError when val was in the last slot. Fill the hole first, pop last.
Removing from the middle: self.values.remove(val) or self.values.pop(i) shifts every later value: O(N) per call, about 10¹⁰ steps at these limits, and every shifted slot in self.index goes stale.
A biased pick: random.randint(0, len(self.values) - 2) never returns the last value, and self.values[0] is not random at all. random.choice(self.values) gives each slot, and so each value, a 1-in-n chance.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots an O(1) random pick next to O(1) deletes and defends the swap-with-last delete out loud.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Write self.index[last] = i before del self.index[val]: when val is the last value, last == val, and deleting first writes val back into the map at a slot that pop() removes, so a later insert(val) returns false.
Update the moved value's slot at all: without self.index[last] = i, the map still says last sits at the end, and removing it later fills the wrong slot.
Fill the hole before self.values.pop(): popping first and then writing self.values[i] fails when i was the last slot, which no longer exists.
Never self.values.remove(val) or self.values.pop(i) from the middle: both shift the rest of the list, O(N), and every shifted value's slot in self.index goes stale.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use the Insert Delete GetRandom design: an array plus an index map. A pick where every value is equally likely needs the values packed in an array, so getRandom is random choice over it, and a map from each value to its slot makes insert and the lookup in remove O(1). The hard part is deleting from the middle of the array in O(1). A set has no order, so I move the last value into the removed value's slot, record that value's new slot in the map, delete the removed value's entry and pop the end. The array stays gap-free, so every value keeps exactly one slot and the same chance. The trap is the order of the two map writes: when the removed value is itself the last one, updating first and deleting second is right, while deleting first writes it straight back into the map. Every call is O(1) on average, and the space is O(N).

So: a gap-free list for the pick, a map for the slot, and on remove update self.index[last] before deleting self.index[val].

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(1) average per call

SPACE COMPLEXITY

O(N)

self.values and self.index each hold one entry per stored value: O(N) for N values. No recursion, and no call builds a temporary list.

Formal Recurrence Relation

T(Q) = Q · O(1) = O(Q) for Q calls (average)

Derivation Progression

insert

O(1) average

One lookup val in self.index, one map write self.index[val] = len(self.values), one append at the end of the list.

remove

O(1) average

One lookup, one read of self.values[-1], one slot write self.values[i] = last, one map write, one del, one pop() at the end: nothing shifts.

getRandom

O(1)

random.choice(self.values) draws one index and reads one slot.

Total

O(Q)

Constant average work per call over Q calls.

Variable Definitions

$N$

Number of values in the set, len(self.values)

$Q$

Number of calls to insert, remove and getRandom (at most 2 * 10⁵)

Memory Architecture & Bounds

🟣 Call Stack

O(1) No recursion

🔵 Auxiliary Heap

O(N): one list slot and one map entry per stored value

🟢 Output Space

O(1) per call: one boolean or integer

Boundary Best / Worst Cases

Best Case

$O(1)$ per call

Average Case

$O(1)$ per call

Worst Case

$O(N)$ for one call when every value hashes to the same bucket, or when the list grows its buffer; O(1) amortized over a run

Recurrence Tree Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. One Slot per Value, No Gaps

`self.values` holds every stored value exactly once with no holes, and `self.index[v]` is the slot of `v`, so `random.choice(self.values)` gives each value a 1-in-n chance.

2. Update, Then Delete

3. O(1) on Average

No call walks the list: a few map operations, one slot write and one `append` or `pop()` at the end. Every call is O(1) on average, for one list slot and one map entry per value: O(N) space.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: INSERT DELETE GETRANDOM O(1) (LEETCODE 380)

T = O(1) average per callS = O(N)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
A gap-free list for the random pick	`self.values: list[int] = []`	Every stored value sits in one slot `0 .. n - 1`, with no holes, so `random.choice` gives each a 1-in-n chance.
A map from value to its slot	`self.index: dict[int, int] = {}`	It answers `val in self.index` and finds `val`'s slot in O(1) on average: no scan of the list.
Insert: record the slot, then append	`self.index[val] = len(self.values) self.values.append(val)`	The new value goes to the end, and the end's slot number is the list length before the append.
Fill the hole with the last value	`i = self.index[val] last = self.values[-1] self.values[i] = last`	A set has no order, so the last value may move into `val`'s slot: the list keeps no gap and nothing shifts.
Update the moved value's slot first, then delete	`self.index[last] = i del self.index[val]`	The card's trap: when `val` is the last value, `last == val`, and only this order leaves `val` out of the map.
Drop the last slot in O(1)	`self.values.pop()`	The last slot now holds a copy of `last` (or `val` itself), so popping it removes nothing that is still needed.
Pick uniformly over slots	`return random.choice(self.values)`	One slot per value, so every stored value is equally likely.

Call

self.values after the call

self.index after the call

Returns

What happened

RandomizedSet()

[]

{}

null

An empty set

insert(1)

[1]

{1: 0}

true

1 takes slot 0

insert(2)

[1, 2]

{1: 0, 2: 1}

true

2 takes slot 1

insert(3)

[1, 2, 3]

{1: 0, 2: 1, 3: 2}

true

3 takes slot 2

remove(1)

[3, 2]

{2: 1, 3: 0}

true

i = 0, last = 3: 3 moves into slot 0, self.index[3] = 0, then pop()

remove(2)

[3]

{3: 0}

true

i = 1 and last = 2: 2 is the last value. self.index[2] = 1, then del self.index[2]. Deleting first would write 2: 1 back

insert(2)

[3, 2]

{3: 0, 2: 1}

true

With a stale 2: 1 left in the map, this would return false

remove(3)

[2]

{2: 0}

true

i = 0, last = 2: 2 moves into slot 0

getRandom()

[2]

{2: 0}

2

random.choice([2]): the only value

Call

self.values after the call

self.index after the call

Returns

What happened

RandomizedSet()

[]

{}

null

An empty set

insert(1)

[1]

{1: 0}

true

1 takes slot 0

insert(2)

[1, 2]

{1: 0, 2: 1}

true

2 takes slot 1

insert(3)

[1, 2, 3]

{1: 0, 2: 1, 3: 2}

true

3 takes slot 2

remove(1)

[3, 2]

{2: 1, 3: 0}

true

i = 0, last = 3: 3 moves into slot 0, self.index[3] = 0, then pop()

remove(2)

[3]

{3: 0}

true

i = 1 and last = 2: 2 is the last value. self.index[2] = 1, then del self.index[2]. Deleting first would write 2: 1 back

insert(2)

[3, 2]

{3: 0, 2: 1}

true

With a stale 2: 1 left in the map, this would return false

remove(3)

[2]

{2: 0}

true

i = 0, last = 2: 2 moves into slot 0

getRandom()

[2]

{2: 0}

2

random.choice([2]): the only value

🧭 Conceptual Foundation & Pattern Intuition

🅿️ The Analogy: A Car Park With Numbered Bays

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

i = self.index[val]
last = self.values[-1]
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()

💡 Summary

Canonical Invariant

Concrete Code

Engineering Rationale

A gap-free list for the random pick

self.values: list[int] = []

Every stored value sits in one slot `0 .. n - 1`, with no holes, so `random.choice` gives each a 1-in-n chance.

A map from value to its slot

self.index: dict[int, int] = {}

It answers `val in self.index` and finds `val`'s slot in O(1) on average: no scan of the list.

Insert: record the slot, then append

self.index[val] = len(self.values)
self.values.append(val)

The new value goes to the end, and the end's slot number is the list length before the append.

Fill the hole with the last value

i = self.index[val]
last = self.values[-1]
self.values[i] = last

A set has no order, so the last value may move into `val`'s slot: the list keeps no gap and nothing shifts.

Update the moved value's slot first, then delete

self.index[last] = i
del self.index[val]

The card's trap: when `val` is the last value, `last == val`, and only this order leaves `val` out of the map.

Drop the last slot in O(1)

self.values.pop()

The last slot now holds a copy of `last` (or `val` itself), so popping it removes nothing that is still needed.

Pick uniformly over slots

return random.choice(self.values)

One slot per value, so every stored value is equally likely.