Insert Delete GetRandom O(1) with Duplicates

📋

Problem

Imagine building a music playlist app where songs can be added multiple times, removed, and played randomly - all instantly.

Design a data structure that supports all following operations in average O(1) time: insert(val): Inserts an item val to the collection. Returns true if the item was not already present. remove(val): Removes an item val from the collection if present. Returns true if the item was present. getRandom(): Returns a random element from the current collection of elements. The probability of each element being returned is linearly related to the number of same elements in the collection. Duplicate elements are allowed.

1 ≤ number of operations ≤ 10^5-10^9 ≤ val ≤ 10^9At least one element will be present when getRandom is called

Edge cases: Removing an element not present → returns falseInserting multiple duplicates → insert returns false after firstCalling getRandom on single-element collection → always returns that element

</>

IDE

class RandomizedCollection:public class RandomizedCollection {class RandomizedCollection {class RandomizedCollection {

class RandomizedCollection:
    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 RandomizedCollection {
    public RandomizedCollection() {
        // Write your solution here
    }
    public boolean insert(int val) {
        return false;
    }
    public boolean remove(int val) {
        return false;
    }
    public int getRandom() {
        return 0;
    }
}

#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: insert returns true for duplicate insertionsNot checking if val already exists before insert returns.✅ Return !map[val].empty() before insertion to determine if val was present.

Wrong: remove returns true even when val not presentNot verifying presence in map before removal.✅ Check if map[val] is empty before attempting removal; return false if empty.

Wrong: getRandom returns removed elementsNot updating indices in map after swapping last element on remove.✅ Update map entries for swapped element index after removal.

Wrong: remove removes all duplicates at onceRemoving all indices of val instead of one per call.✅ Remove only one index from map[val] and update array accordingly per remove call.

Wrong: TLE on large inputLinear search on remove instead of O(1) swap and map update.✅ Use hash map to track indices and swap last element with removed element for O(1) remove.

✓

Test Cases

Focus on handling empty and single-element collections correctly.

Watch out for stale indices and ensure correct boolean returns on duplicates.

Optimize remove operation to avoid linear scans by swapping with last element.

t1_01basic

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

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

⏱ Performance - must finish in 2000ms

First insert(1) returns true because 1 was not present. Second insert(1) returns false because 1 was already present. insert(2) returns true. getRandom() returns 1 with probability 2/3 or 2 with probability 1/3. remove(1) removes one occurrence of 1 and returns true. getRandom() now returns 1 or 2 with equal probability.

💡 Think about how to track multiple indices for duplicates efficiently.

💡 Use a hash map from value to a set of indices and an array to store values.

💡 On remove, swap with last element and update indices in the map to maintain O(1).

Why it failed: Incorrect insert or remove return values or getRandom probabilities indicate failure to handle duplicates or update indices correctly. Fix by maintaining a map from val to index set and updating on swaps.

✓ Correctly handles duplicates with O(1) insert, remove, and getRandom.

t1_02basic

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

Expected[true,true,false,true,"10 or 20",true,20]

⏱ Performance - must finish in 2000ms

insert(10) true (new), insert(20) true (new), insert(10) false (duplicate), remove(10) true (one occurrence removed), getRandom() returns 10 or 20, remove(10) true (last 10 removed), getRandom() returns 20 only.

💡 Check that insert returns false for duplicates after first insertion.

💡 Ensure remove only removes one occurrence and updates data structures.

💡 getRandom should reflect current collection state after removals.

Why it failed: Failing to update index sets on remove causes stale indices or wrong getRandom results. Fix by removing index from map and swapping last element properly.

✓ Correctly updates internal state after insertions and removals.

t2_01edge

Input["remove(5)"]

Expected[false]

⏱ Performance - must finish in 2000ms

Removing an element not present returns false.

💡 Check if the value exists before attempting removal.

💡 Use the map to verify presence before removing.

💡 Return false immediately if val not found in map.

Why it failed: Removing non-existent element returns true or causes error. Fix by checking map presence before removal.

✓ Correctly returns false when removing absent element.

t2_02edge

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

Expected[true,42]

⏱ Performance - must finish in 2000ms

Single element inserted; getRandom always returns that element.

💡 When only one element exists, getRandom must return it.

💡 Ensure getRandom does not fail on single-element collection.

💡 Return the only element in the array without error.

Why it failed: getRandom fails or returns invalid value on single-element collection. Fix by handling single-element case correctly.

✓ getRandom returns the only element correctly.

t2_03edge

Input["insert(7)","insert(7)","insert(7)","remove(7)","remove(7)","remove(7)","remove(7)"]

Expected[true,false,false,true,true,true,false]

⏱ Performance - must finish in 2000ms

Insert 7 once returns true, duplicates return false. Remove 7 three times returns true each time, last remove returns false as collection empty.

💡 Check that insert returns false for duplicates after first.

💡 Remove should remove one occurrence at a time.

💡 After all duplicates removed, further remove returns false.

Why it failed: Remove returns true when element no longer present or insert returns true for duplicates. Fix by tracking counts and updating map correctly.

✓ Correctly handles multiple duplicates and empty collection after removals.

t3_01corner

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

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

⏱ Performance - must finish in 2000ms

Removing middle element and getRandom should not return removed element.

💡 Check that remove swaps last element into removed index.

💡 Update indices in map after swap to avoid stale references.

💡 getRandom should only return current elements.

Why it failed: getRandom returns removed element due to stale indices. Fix by updating map indices after swap on remove.

✓ Correctly removes element and updates internal state.

t3_02corner

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

Expected[true,false,true,true,false]

⏱ Performance - must finish in 2000ms

Remove called more times than duplicates; last remove returns false.

💡 Ensure remove only removes one occurrence per call.

💡 Check map emptiness after each removal.

💡 Return false if no occurrences remain.

Why it failed: Remove returns true even when no occurrences left. Fix by checking map emptiness before removal.

✓ Removes duplicates one by one and returns false when none left.

t3_03corner

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

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

⏱ Performance - must finish in 2000ms

Re-inserting a removed element returns true and getRandom includes it.

💡 Check insert returns true if element was fully removed before.

💡 Ensure map and array updated correctly on re-insert.

💡 getRandom should reflect current collection including re-inserted elements.

Why it failed: Insert returns false incorrectly for re-inserted element. Fix by checking map emptiness before insert.

✓ Correctly handles re-insertion after removal.

t4_01performance

Input["insert(0)","insert(1)","insert(2)","insert(3)","insert(4)","insert(5)","insert(6)","insert(7)","insert(8)","insert(9)","remove(0)","remove(1)","remove(2)","remove(3)","remove(4)","remove(5)","remove(6)","remove(7)","remove(8)","remove(9)"]

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 operations with mixed inserts and removes must complete in 2s using O(1) average operations.

💡 Use hash map and array with index sets for O(1) average insert/remove.

💡 Avoid linear scans on remove by swapping with last element.

💡 Maintain index sets to update positions efficiently.

Why it failed: TLE due to linear remove or inefficient data structure. Fix by using hash map to track indices and swapping last element on remove.

✓ Algorithm runs within time limit using O(1) average operations.

Practice

1. Consider the following Python code snippet for the MedianFinder class using two heaps. After adding the numbers 1, 5, and 3 in that order, what is the value of the median returned by findMedian()?

easy

A. 1.0

B. 3.0

C. 5.0

D. 2.0

Solution

1. Step 1: Insert 1

   Low heap empty, push -1 to low; low_size=1, high_size=0.

2. Step 2: Insert 5

   5 > -low[0] (which is 1), push 5 to high; low_size=1, high_size=1; heaps balanced.

3. Step 3: Insert 3

   3 <= 5 but > 1, push 3 to high; high_size=2, low_size=1; balance heaps by moving smallest from high (3) to low (-3); low_size=2, high_size=1.

4. Step 4: Find median

   low_size > high_size, median is -low[0] = 3.0.

5. Step 5: Re-examine median calculation

   After balancing, low heap has [-3, -1], high heap has [5]. Median is top of low heap = 3.0, but the question asks for median after adding 1,5,3 in order, so median is 3.0.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Median after [1,5,3] is 3.0 [OK]

Hint: Median is top of larger heap after balancing [OK]

Common Mistakes:

• Forgetting to balance heaps after insertion
• Returning wrong heap top for median

2. Given the following code snippet for flattening a multilevel doubly linked list, what is the value of curr.val after the first iteration of the outer while loop when the input list is: 1 - 2 - 3, where node 2 has a child list 4 - 5?

easy

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Initialize curr to head (node with val=1)

   First iteration: curr.val = 1, no child, so move to next node.

2. Step 2: After first iteration, curr moves to node with val=2

   Thus, after the first iteration, curr.val is 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   curr.val is 1 after first iteration of the loop [OK]

Hint: curr starts at head with val=1 and moves after processing [OK]

Common Mistakes:

• Assuming curr.val changes before moving
• Confusing iteration count with node value

3. You need to design a data structure that supports adding intervals, removing intervals, and querying whether a given range is fully covered by the added intervals. Which approach guarantees efficient updates and queries with logarithmic time complexity per operation?

easy

A. Use a balanced binary search tree (e.g., TreeMap) to store and merge intervals, enabling logarithmic time operations.

B. Use a brute force list of intervals and scan all intervals for each operation.

C. Use dynamic programming to precompute coverage for all possible ranges.

D. Use a greedy algorithm that always merges intervals only when queried.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support add, remove, and query operations on intervals efficiently.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n) per operation, which is inefficient. DP is not suitable for dynamic interval updates. Greedy merging only on query delays merging and leads to inefficient queries. Balanced BST with interval merging maintains sorted intervals and merges overlapping ones, supporting O(log n) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Balanced BST with merging -> O(log n) per operation [OK]

Hint: Balanced BST with merging enables efficient interval operations [OK]

Common Mistakes:

• Thinking DP or greedy solves dynamic interval updates efficiently

4. You are given a list of buildings represented as triplets (left, right, height). The goal is to output the skyline formed by these buildings as a list of key points where the height changes. Which algorithmic approach guarantees an optimal solution with time complexity O(n log n)?

easy

A. Divide and conquer approach that recursively merges skylines of building subsets

B. Dynamic programming approach that stores maximum heights for subproblems

C. Greedy approach that iteratively picks the tallest building at each x-coordinate

D. Brute force simulation by iterating over all x-coordinates and tracking max height

Solution

1. Step 1: Understand problem requirements

   The problem requires merging multiple building outlines into a single skyline efficiently.

2. Step 2: Evaluate algorithmic approaches

   Greedy and brute force approaches either fail to guarantee optimal time or are inefficient. Dynamic programming is not a natural fit here. Divide and conquer merges smaller skylines efficiently in O(n log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Divide and conquer merges sorted skylines efficiently [OK]

Hint: Divide and conquer merges sorted skylines in O(n log n) [OK]

Common Mistakes:

• Thinking greedy or brute force is optimal
• Confusing DP with skyline merging

5. Suppose the skyline problem is extended so that buildings can overlap and have negative heights (e.g., representing underground structures). Which modification to the divide and conquer approach is necessary to correctly handle this variant?

hard

A. Modify the merge step to consider absolute values of heights when computing max height

B. Adjust the merge logic to track both max and min heights at each x-coordinate and merge accordingly

C. No modification needed; the existing merge logic works for negative heights

D. Replace divide and conquer with a brute force height map simulation to handle negative heights

Solution

1. Step 1: Understand impact of negative heights

   Negative heights mean skyline can go below ground, so max height alone is insufficient to represent shape.

2. Step 2: Modify merge logic accordingly

   Need to track both max and min heights at each x to correctly merge skylines with negative and positive heights.

3. Step 3: Evaluate other options

   Using absolute values loses sign info; brute force is inefficient; no modification fails correctness.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking both max and min heights handles negative overlaps correctly [OK]

Hint: Negative heights require tracking min and max heights, not just max [OK]

Common Mistakes:

• Ignoring negative heights
• Using absolute values incorrectly
• Assuming no change needed