Course4all
Join us on telegram
Home/dsa/Design/Insert Delete GetRandom O(1) - Duplicates allowed

Insert Delete GetRandom O(1) - Duplicates allowed

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Insert Delete GetRandom O(1) - Duplicates allowed

Design a data structure that supports insert, remove, and getRandom in O(1)O(1) time, where duplicates are allowed.

Strategy

Combine a List of values (for O(1)O(1) random access) with a HashMap<Value, Set<Indices>> (for O(1)O(1) removal).

Hard

Examples

Input: ["RandomizedCollection","insert","insert","insert","getRandom","remove","getRandom"] [[],[1],[1],[2],[],[1],[]]
Output: [null, true, false, true, 1 or 2, true, 1 or 2]
Approach 1

Level I: Simple List with Linear Scan

Intuition

Maintain a simple ArrayList to store values. For insert, append to the end. For remove, find the first occurrence using a linear scan O(N)O(N) and remove it. For getRandom, pick a random index in O(1)O(1).

⏱ Insert: O(1), Remove: O(N), GetRandom: O(1).💾 O(N).

Detailed Dry Run

List: [1, 1, 2]. Remove(1) -> Find index 0 -> List: [1, 2]. getRandom() picks 1 or 2 with equal prob.

java
class RandomizedCollection {
    List<Integer> list = new ArrayList<>();
    Random rand = new Random();
    public boolean insert(int val) {
        boolean exists = list.contains(val); list.add(val); return !exists;
    }
    public boolean remove(int val) {
        return list.remove((Integer)val);
    }
    public int getRandom() { return list.get(rand.nextInt(list.size())); }
}
Approach 2

Level II: Map of Count + Randomized Index

Intuition

Maintain a Map<Value, Frequency> and a List<Value>. When removing, find the first occurrence in the List and replace it with the last element. This is O(N)O(N) for remove but O(1)O(1) for others.

⏱ Insert: O(1), Remove: O(N), GetRandom: O(1).💾 O(N).
java
class RandomizedCollection {
    List<Integer> list = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    Random rand = new Random();
    public boolean insert(int val) {
        boolean res = !map.containsKey(val);
        map.put(val, map.getOrDefault(val, 0) + 1); list.add(val);
        return res;
    }
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int f = map.get(val); if (f == 1) map.remove(val); else map.put(val, f - 1);
        list.remove((Integer)val); // O(N) search
        return true;
    }
    public int getRandom() { return list.get(rand.nextInt(list.size())); }
}
Approach 3

Level III: HashMap of Sets + Array

Intuition

When removing an element, swap its last index from the Set with the last element in the Array. This allows O(1)O(1) deletion from an array by overwriting the target with the last item and popping.

⏱ O(1) average for all operations.💾 O(N).
java
class RandomizedCollection {
    List<Integer> list = new ArrayList<>();
    Map<Integer, Set<Integer>> map = new HashMap<>();
    Random rand = new Random();
    public boolean insert(int val) {
        boolean exists = map.containsKey(val);
        if (!exists) map.put(val, new HashSet<>());
        map.get(val).add(list.size());
        list.add(val);
        return !exists;
    }
    public boolean remove(int val) {
        if (!map.containsKey(val) || map.get(val).isEmpty()) return false;
        int removeIdx = map.get(val).iterator().next();
        map.get(val).remove(removeIdx);
        int lastVal = list.get(list.size() - 1);
        list.set(removeIdx, lastVal);
        map.get(lastVal).add(removeIdx);
        map.get(lastVal).remove(list.size() - 1);
        list.remove(list.size() - 1);
        return true;
    }
    public int getRandom() { return list.get(rand.nextInt(list.size())); }
}
← Previous QuestionLFU Cache
Next Question →All O(1) Data Structure