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. What is the time complexity of the inc and dec operations in the optimized AllOne data structure that uses doubly linked list buckets and hash maps, and why?

medium

A. O(1) worst-case because all operations involve only pointer and hash map updates

B. O(1) amortized because bucket insertion and removal are constant time with hash maps

C. O(log n) due to maintaining sorted order of buckets

D. O(n) because updating buckets requires scanning keys

Solution

1. Step 1: Identify operations involved in inc/dec

   Operations include moving keys between buckets, inserting/removing buckets, and updating hash maps.

2. Step 2: Analyze complexity of each operation

   All pointer updates and hash map lookups/inserts/removals are O(1). No scanning or sorting is needed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All operations are pointer and hash map updates, no loops over keys [OK]

Hint: Pointer and hash map ops are O(1), no scanning or sorting [OK]

Common Mistakes:

• Confusing bucket insertion as O(log n) or scanning keys as O(n)

2. The following code attempts to copy a linked list with random pointers using the optimal weaving approach. Identify the line that contains a subtle bug that can cause incorrect random pointer assignment or list corruption.

def copyRandomList(head):
    if not head:
        return None
    curr = head
    # Step 1: Insert copied nodes
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next
    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random  # Bug here
        curr = curr.next.next
    # Step 3: Separate lists
    curr = head
    copy_head = head.next
    copy_curr = copy_head
    while curr:
        curr.next = curr.next.next
        if copy_curr.next:
            copy_curr.next = copy_curr.next.next
        curr = curr.next
        copy_curr = copy_curr.next
    return copy_head

medium

A. Line assigning curr.next.random = curr.random

B. Line inserting copied nodes: curr.next = new_node

C. Line advancing curr in Step 1: curr = new_node.next

D. Line separating original and copied lists: curr.next = curr.next.next

Solution

1. Step 1: Analyze random pointer assignment

   The line assigns curr.next.random = curr.random, but curr.random points to original nodes, not copied nodes.

2. Step 2: Correct assignment

   It should be curr.next.random = curr.random.next to point to the copied node corresponding to curr.random.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect random pointer assignment breaks copied list correctness [OK]

Hint: Random pointer must point to copied node, not original [OK]

Common Mistakes:

• Assigning random pointer directly to original node
• Mixing original and copied nodes after weaving
• Forgetting to advance curr by two nodes

3. What is the average time complexity of search, insert, and erase operations in a skiplist with dynamic max level and probability tuning, assuming n elements?

medium

A. O(log n) average due to probabilistic multi-level structure

B. O(1) average due to direct indexing in arrays

C. O(log^2 n) because each level requires a separate traversal

D. O(n) because linked lists require linear traversal

Solution

1. Step 1: Understand skiplist structure

   Skiplist uses multiple levels with probabilistic promotion, reducing expected search path length to logarithmic in n.

2. Step 2: Analyze average operation cost

   Each operation traverses from top level down, with expected O(log n) steps due to geometric level distribution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Skiplist average complexity is well-known as O(log n) [OK]

Hint: Skiplist average complexity is logarithmic, not linear or constant [OK]

Common Mistakes:

• Assuming linear time due to linked list base
• Confusing traversal at each level as multiplicative
• Thinking arrays provide O(1) search in skiplist

4. What is the worst-case time complexity of the in-place iterative flattening algorithm for a multilevel doubly linked list where each node may have a child list, and why?

medium

A. O(n) because each node is visited once.

B. O(n) with O(n) auxiliary space for recursion stack.

C. O(n log n) due to repeated merging of child lists.

D. O(n^2) because finding the tail of each child list requires traversing child nodes repeatedly.

Solution

1. Step 1: Identify the costly operation

   Finding the tail of each child list requires traversing that child list fully.

2. Step 2: Analyze nested traversal effect

   Since this tail-finding happens for multiple nodes, total time can be quadratic in number of nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Repeated tail traversal causes O(n^2) time in worst case [OK]

Hint: Repeated tail search causes quadratic time [OK]

Common Mistakes:

• Assuming linear time because each node is visited once
• Confusing recursion stack space with iterative approach

5. Consider the following buggy addRange method for the RangeModule. Which line contains the subtle bug that causes incorrect interval merging?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] > left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

medium

A. Line with condition: if i != 0 and self.intervals[self.starts[i-1]] > left:

B. Line with bisect_left call: i = bisect_left(self.starts, left)

C. Line deleting intervals: for k in self.starts[i:j]: del self.intervals[k]

D. Line updating self.starts: self.starts[i:j] = [left]

Solution

1. Step 1: Analyze the condition for merging overlapping intervals

   The condition uses > instead of >=, so intervals that exactly touch at the boundary are not merged.

2. Step 2: Consequence of the bug

   This causes fragmented intervals and incorrect query results because adjacent intervals are not merged properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using > instead of >= misses boundary merges [OK]

Hint: Check interval overlap condition carefully for off-by-one errors [OK]

Common Mistakes:

• Using strict inequality instead of inclusive for merging intervals