Insert Delete GetRandom O(1)

📋

Problem

Imagine you are building a gaming platform where you need to quickly add players, remove players, and pick a random player to start a game - all in constant time.

Design a data structure that supports the following operations in average O(1) time: insert(val): Inserts an item val into the set if not already present. remove(val): Removes an item val from the set if present. getRandom(): Returns a random element from the current set of elements. Each element must have the same probability of being returned.

1 ≤ number of operations ≤ 10^5Values inserted are integers in the range [-10^9, 10^9]At any time, getRandom will only be called if the set is non-empty

Edge cases: Remove element not present → should return falseInsert duplicate element → should return falsegetRandom on single element set → always returns that element

</>

IDE

class RandomizedSet: def __init__(self): pass def insert(self, val: int) -> bool: pass def remove(self, val: int) -> bool: pass def getRandom(self) -> int: passpublic class RandomizedSet { public RandomizedSet() {} public boolean insert(int val) {} public boolean remove(int val) {} public int getRandom() {} }class RandomizedSet { public: RandomizedSet() {} bool insert(int val) {} bool remove(int val) {} int getRandom() {} };class RandomizedSet { constructor() {} insert(val) {} remove(val) {} getRandom() {} }

class RandomizedSet:
    def __init__(self):
        # Write your solution here
        pass
    def insert(self, val: int) -> bool:
        pass
    def remove(self, val: int) -> bool:
        pass
    def getRandom(self) -> int:
        pass

public class RandomizedSet {
    public RandomizedSet() {
        // Write your solution here
    }
    public boolean insert(int val) {
        return false;
    }
    public boolean remove(int val) {
        return false;
    }
    public int getRandom() {
        return 0;
    }
}

class RandomizedSet {
public:
    RandomizedSet() {
        // Write your solution here
    }
    bool insert(int val) {
        return false;
    }
    bool remove(int val) {
        return false;
    }
    int getRandom() {
        return 0;
    }
};

class RandomizedSet {
    constructor() {
        // Write your solution here
    }
    insert(val) {
        return false;
    }
    remove(val) {
        return false;
    }
    getRandom() {
        return 0;
    }
}

Common Bugs to Avoid

Wrong: remove returns true even when element not presentNot checking presence in hash map before removal✅ Add a presence check: if val not in map, return false immediately

Wrong: insert returns true for duplicate elementsNot verifying if element already exists before insertion✅ Check if val in map before inserting; return false if present

Wrong: getRandom returns removed elements or crashes on single elementNot updating array and map correctly on remove; stale indices remain✅ On remove, swap element with last, update map, and pop last element

Wrong: insert fails to add element after removalRemove does not fully delete element from map and array✅ Ensure remove deletes element from map and array completely

Wrong: TLE on large inputRemove or insert implemented with linear search instead of hash map✅ Use hash map for indices and swap-delete trick for O(1) removals

✓

Test Cases

Focus on handling empty and minimal cases correctly before moving on.

Ensure your data structure updates all internal states correctly after each operation.

Optimize your solution to use O(1) average time operations using hash map and array.

t1_01basic

Input["insert(1)","insert(2)","getRandom()","remove(1)","getRandom()"]

Expected[true,true,"1 or 2",true,2]

⏱ Performance - must finish in 2000ms

Insert 1 and 2 successfully. getRandom returns either 1 or 2 with equal probability. Remove 1 successfully. getRandom now returns 2 as it's the only element.

💡 Think about how to store elements for O(1) insert, remove, and random access.

💡 Use a hash map for indices and an array for elements to enable swap-delete trick.

💡 On remove, swap the element with the last and pop to maintain O(1) removal.

Why it failed: Basic case failed - likely missing swap-delete trick causing remove to be O(n) or incorrect getRandom. Fix by maintaining element indices in a hash map and swapping with last element before removal.

✓ Core operations implemented correctly with O(1) average time.

t1_02basic

Input["insert(10)","insert(20)","insert(30)","remove(20)","getRandom()"]

Expected[true,true,true,true,"10 or 30"]

⏱ Performance - must finish in 2000ms

Insert 10, 20, 30 successfully. Remove 20 successfully. getRandom returns either 10 or 30 with equal probability.

💡 Check that remove updates both the array and hash map correctly.

💡 Ensure getRandom picks uniformly from current elements only.

💡 Verify that after removal, the internal data structures remain consistent.

Why it failed: Remove operation failed to update hash map or array correctly, causing getRandom to return removed elements or fail. Fix by updating index map and swapping elements properly.

✓ Remove and getRandom handle multiple elements correctly.

t2_01edge

Input["remove(5)"]

Expected[false]

⏱ Performance - must finish in 2000ms

Removing an element not present should return false.

💡 Check if element exists before attempting removal.

💡 Use hash map to verify presence in O(1).

💡 Return false immediately if element not found.

Why it failed: Remove returns true or errors when element not present. Fix by checking presence in hash map before removal.

✓ Remove correctly returns false for absent elements.

t2_02edge

Input["insert(42)","insert(42)"]

Expected[true,false]

⏱ Performance - must finish in 2000ms

Inserting duplicate element should return false on second insert.

💡 Check if element already exists before inserting.

💡 Use hash map to detect duplicates efficiently.

💡 Return false if element is already present.

Why it failed: Insert allows duplicates causing incorrect state or multiple entries. Fix by checking hash map before insertion.

✓ Insert prevents duplicates correctly.

t2_03edge

Input["insert(100)","getRandom()"]

Expected[true,100]

⏱ Performance - must finish in 2000ms

getRandom on single element set always returns that element.

💡 When only one element exists, getRandom should return it directly.

💡 Ensure random selection handles single-element array correctly.

💡 Avoid errors or empty returns when size is one.

Why it failed: getRandom returns wrong value or errors on single element. Fix by handling single-element case or using uniform random selection.

✓ getRandom returns the only element correctly.

t3_01corner

Input["insert(1)","insert(2)","insert(3)","remove(2)","insert(2)","getRandom()"]

Expected[true,true,true,true,true,"1 or 2 or 3"]

⏱ Performance - must finish in 2000ms

Re-inserting a removed element should succeed and getRandom returns any current element.

💡 Ensure remove deletes element fully from hash map and array.

💡 Insert should allow previously removed elements.

💡 getRandom should reflect current set accurately.

Why it failed: Insert fails to add element after removal due to stale hash map entries. Fix by removing element from hash map and array completely on remove.

✓ Insert after remove works and getRandom reflects current elements.

t3_02corner

Input["insert(5)","insert(10)","remove(5)","remove(10)","getRandom()"]

Expected[true,true,true,true,null]

⏱ Performance - must finish in 2000ms

getRandom called on empty set should not occur per constraints; if it does, handle gracefully.

💡 Check if set is empty before getRandom.

💡 Throw exception or handle error if getRandom called on empty.

💡 Ensure no invalid access to empty array.

Why it failed: getRandom crashes or returns invalid value on empty set. Fix by checking size before getRandom and handling empty case.

✓ getRandom safely handles empty set or is never called when empty.

t3_03corner

Input["insert(1)","insert(2)","insert(3)","remove(1)","remove(3)","getRandom()"]

Expected[true,true,true,true,true,2]

⏱ Performance - must finish in 2000ms

After removing multiple elements, getRandom returns the only remaining element.

💡 Ensure multiple removals update hash map and array correctly.

💡 getRandom should reflect current single element.

💡 Verify no stale indices remain after removals.

Why it failed: getRandom returns removed elements due to stale indices. Fix by updating hash map and swapping elements properly on each remove.

✓ Multiple removals handled correctly; getRandom returns current element.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Test with 100000 operations to ensure O(1) average time per operation completes within 2 seconds.

💡 Brute force remove with linear search will TLE here.

💡 Use hash map for indices and array for elements to achieve O(1) average.

💡 Implement swap-delete trick to maintain constant time removals.

Why it failed: TLE due to linear time remove or insert operations. Fix by using hash map for index tracking and swap-delete trick for O(1) removals.

✓ Algorithm runs in O(1) average time per operation as expected.

Practice

1. Consider the following Python function to detect duplicates. What is the value of the variable seen after processing the third element in the input [2, 4, 2, 5]?

easy

A. {4, 2}

B. {2, 4, 2}

C. {2, 4, 5}

D. {2, 4}

Solution

1. Step 1: Trace the loop iterations

   After first element (2), seen = {2}. After second element (4), seen = {2, 4}. After third element (2), since 2 is already in seen, the function returns True before adding anything new.

2. Step 2: Determine seen after third element

   Because the function returns immediately upon detecting duplicate, seen remains {2, 4} at that point.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Duplicate detected at third element, no new additions after second iteration [OK]

Hint: Function returns immediately on duplicate, so seen stops growing [OK]

Common Mistakes:

• Assuming duplicate is added again to set
• Confusing order of insertion
• Misreading when return occurs

2. What is the worst-case time complexity of the optimal hash set approach to detect duplicates in an array of length n?

medium

A. O(n) average, but O(n²) worst-case if many hash collisions occur

B. O(n log n) due to sorting inside the hash set

C. O(n²) because each insertion checks all existing elements

D. O(n) guaranteed due to constant-time hash set operations

Solution

1. Step 1: Understand average case

   Hash set operations (insert, lookup) are O(1) average, so iterating n elements is O(n) average.

2. Step 2: Consider worst-case scenario

   If many hash collisions occur, hash set operations degrade to O(n) each, making total O(n²) in worst case.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash collisions cause worst-case quadratic time, though rare in practice [OK]

Hint: Hash collisions can degrade hash set to O(n²) worst-case [OK]

Common Mistakes:

• Assuming guaranteed O(n) time
• Confusing sorting complexity with hashing
• Thinking insertion checks all elements explicitly

3. Consider the following buggy get method for the time-based key-value store. Which line contains the subtle bug that causes incorrect results when querying timestamps less than the smallest stored timestamp?

medium

A. Line 6: Returning empty string if i == 0

B. Line 2: Checking if key not in store

C. Line 5: Using bisect_left instead of bisect_right

D. Line 7: Returning values[i-1]

Solution

1. Step 1: Understand difference between bisect_left and bisect_right

   bisect_left returns insertion index to the left, which can cause off-by-one errors when timestamp equals stored timestamps.

2. Step 2: Identify impact on retrieval

   Using bisect_left causes incorrect index i for timestamps equal to stored ones, leading to wrong value or empty string returned.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   bisect_right is required to get correct insertion point for retrieval [OK]

Hint: bisect_right needed to get correct insertion index [OK]

Common Mistakes:

• Using bisect_left instead of bisect_right
• Incorrect boundary check for i==0
• Returning wrong index value

4. Suppose the problem is modified so that negative integers are allowed as input. Which of the following changes to the optimal Happy Number detection algorithm correctly handles negative inputs without breaking correctness or efficiency?

hard

A. Reject negative inputs immediately as invalid and return false

B. Add negative numbers to the unhappy cycle set to detect cycles quickly

C. Ignore the sign and compute sum of squares of digits of the absolute value; proceed as usual

D. Modify sum_of_squares to include the sign squared (which is always positive) and proceed

Solution

1. Step 1: Consider negative input handling

   Sum of squares of digits depends on digits, not sign; absolute value preserves digits.

2. Step 2: Verify correctness and efficiency

   Using absolute value avoids complexity and maintains correctness; no need to add negatives to cycle set or reject.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Absolute value preserves digit sums and cycle detection [OK]

Hint: Use absolute value to handle negative inputs [OK]

Common Mistakes:

• Adding negatives to cycle set
• Rejecting negatives unnecessarily

5. Suppose the time-based key-value store is extended to allow multiple values to be set at the same timestamp for a key, and get should return the most recently set value at or before the timestamp. Which modification to the data structure and retrieval algorithm is correct?

hard

A. Store multiple values per timestamp in a list and modify binary search to find the last value in that list.

B. Store timestamps with duplicates in a list and use bisect_right to find insertion index, then return the last inserted value at that timestamp.

C. Store all (timestamp, value) pairs in insertion order and perform linear search backward on get.

D. Use a hash map from (key, timestamp) to a stack of values and pop on get.

Solution

1. Step 1: Understand requirement for multiple values per timestamp

   Multiple values at same timestamp require storing duplicates and retrieving the most recent one.

2. Step 2: Analyze retrieval with duplicates

   Using bisect_right on timestamps list with duplicates returns insertion index after all duplicates; returning value at i-1 gives the last inserted value at that timestamp.

3. Step 3: Confirm data structure modification

   Storing timestamps with duplicates in order and values aligned allows correct retrieval without linear search or complex structures.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   bisect_right with duplicates returns correct index for last inserted value [OK]

Hint: bisect_right handles duplicates by returning insertion after last duplicate [OK]

Common Mistakes:

• Using linear search causing inefficiency
• Using stacks requiring pop on get
• Storing multiple values in nested lists complicates retrieval