Insert Delete GetRandom O(1) with Duplicates

🎯

Insert Delete GetRandom O(1) with Duplicates

hardDESIGNAmazonGoogleFacebook

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

💡 This problem challenges beginners because it requires designing a data structure that supports insertions, deletions, and random access all in constant time, even when duplicates exist. Managing duplicates efficiently while maintaining O(1) operations is tricky and often confuses newcomers.

📋

Problem Statement

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

💡

Example

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

Output[true, false, true, 1 or 2, true, 1 or 2]

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.

• Removing an element not present → returns false
• Inserting multiple duplicates → insert returns false after first
• Calling getRandom on single-element collection → always returns that element
• Removing all duplicates one by one → collection becomes empty

⚠️

Common Mistakes

Not updating index map after swapping elements during removal

Leads to incorrect indices causing wrong removals or crashes

✅ Always update the index set/map for the swapped element after removal

Using list.remove(val) which removes first occurrence but is O(n)

Causes time limit exceeded on large inputs

✅ Use index tracking and swap with last element to remove in O(1)

Not handling empty collections before getRandom

Runtime error or undefined behavior

✅ Ensure getRandom is only called when collection is non-empty

Returning wrong boolean value on insert when duplicates exist

Fails test cases expecting true only if val was not present before

✅ Return true only if val was not present before insertion

Using a set instead of multiset or list for indices, losing duplicates info

Cannot track multiple occurrences correctly

✅ Use a set of indices or linked list to track all occurrences

🧠

Brute Force (List with Linear Search)

💡 This approach exists to establish a baseline and understand the problem constraints. It uses simple data structures but is inefficient, helping beginners see why optimization is necessary.

Intuition

Store all elements in a list. Insert appends to the list. Remove searches linearly for the element and removes it. getRandom picks a random index from the list.

Algorithm

1. Maintain a list to store all elements including duplicates.
2. For insert(val), append val to the list and return true if val was not present before.
3. For remove(val), scan the list to find val and remove the first occurrence; return true if found.
4. For getRandom(), pick a random index in the list and return the element.

💡 The algorithm is straightforward but the linear search for remove is costly and makes the approach impractical for large inputs.

</>

Code

import random

class RandomizedCollection:
    def __init__(self):
        self.nums = []

    def insert(self, val: int) -> bool:
        contains = val in self.nums
        self.nums.append(val)
        return not contains

    def remove(self, val: int) -> bool:
        if val not in self.nums:
            return False
        self.nums.remove(val)
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)

# Driver code
rc = RandomizedCollection()
print(rc.insert(1))  # True
print(rc.insert(1))  # False
print(rc.insert(2))  # True
print(rc.getRandom())  # 1 or 2
print(rc.remove(1))  # True
print(rc.getRandom())  # 1 or 2

Line Notes

self.nums = []Initialize list to store all elements including duplicates

contains = val in self.numsCheck if val already exists to determine return value

self.nums.append(val)Add val to the end of the list

if val not in self.numsCheck presence before removal to avoid errors

self.nums.remove(val)Remove first occurrence of val, costly linear operation

return random.choice(self.nums)Pick a random element uniformly from the list

import java.util.*;

class RandomizedCollection {
    List<Integer> nums;

    public RandomizedCollection() {
        nums = new ArrayList<>();
    }

    public boolean insert(int val) {
        boolean contains = nums.contains(val);
        nums.add(val);
        return !contains;
    }

    public boolean remove(int val) {
        if (!nums.contains(val)) return false;
        nums.remove(Integer.valueOf(val));
        return true;
    }

    public int getRandom() {
        Random rand = new Random();
        return nums.get(rand.nextInt(nums.size()));
    }

    public static void main(String[] args) {
        RandomizedCollection rc = new RandomizedCollection();
        System.out.println(rc.insert(1));  // true
        System.out.println(rc.insert(1));  // false
        System.out.println(rc.insert(2));  // true
        System.out.println(rc.getRandom());  // 1 or 2
        System.out.println(rc.remove(1));  // true
        System.out.println(rc.getRandom());  // 1 or 2
    }
}

Line Notes

nums = new ArrayList<>()Initialize list to hold elements including duplicates

boolean contains = nums.contains(val)Check if val exists to determine return value

nums.add(val)Add val to the list

if (!nums.contains(val)) return falseCheck presence before removal to avoid errors

nums.remove(Integer.valueOf(val))Remove first occurrence of val, linear time

rand.nextInt(nums.size())Generate random index for getRandom

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

class RandomizedCollection {
    vector<int> nums;
public:
    RandomizedCollection() {
        srand(time(0));
    }

    bool insert(int val) {
        bool contains = find(nums.begin(), nums.end(), val) != nums.end();
        nums.push_back(val);
        return !contains;
    }

    bool remove(int val) {
        auto it = find(nums.begin(), nums.end(), val);
        if (it == nums.end()) return false;
        nums.erase(it);
        return true;
    }

    int getRandom() {
        int idx = rand() % nums.size();
        return nums[idx];
    }
};

int main() {
    RandomizedCollection rc;
    cout << rc.insert(1) << endl;  // 1 (true)
    cout << rc.insert(1) << endl;  // 0 (false)
    cout << rc.insert(2) << endl;  // 1 (true)
    cout << rc.getRandom() << endl;  // 1 or 2
    cout << rc.remove(1) << endl;  // 1 (true)
    cout << rc.getRandom() << endl;  // 1 or 2
    return 0;
}

Line Notes

vector<int> nums;Store all elements including duplicates in a vector

find(nums.begin(), nums.end(), val)Linear search to check presence or find element

nums.push_back(val);Append val to the vector

nums.erase(it);Remove first occurrence of val, costly linear operation

rand() % nums.size()Generate random index for getRandom

class RandomizedCollection {
    constructor() {
        this.nums = [];
    }

    insert(val) {
        const contains = this.nums.includes(val);
        this.nums.push(val);
        return !contains;
    }

    remove(val) {
        const idx = this.nums.indexOf(val);
        if (idx === -1) return false;
        this.nums.splice(idx, 1);
        return true;
    }

    getRandom() {
        const idx = Math.floor(Math.random() * this.nums.length);
        return this.nums[idx];
    }
}

// Driver code
const rc = new RandomizedCollection();
console.log(rc.insert(1));  // true
console.log(rc.insert(1));  // false
console.log(rc.insert(2));  // true
console.log(rc.getRandom());  // 1 or 2
console.log(rc.remove(1));  // true
console.log(rc.getRandom());  // 1 or 2

Line Notes

this.nums = []Initialize array to hold all elements including duplicates

this.nums.includes(val)Check if val exists to determine return value

this.nums.push(val)Add val to the array

this.nums.indexOf(val)Find index of val for removal, linear time

this.nums.splice(idx, 1)Remove first occurrence of val

Math.floor(Math.random() * this.nums.length)Generate random index for getRandom

⏱

Complexity

TimeO(n) for remove due to linear search; O(1) for insert and getRandom

SpaceO(n) to store all elements

Insert is O(1) because it appends. Remove is O(n) because it searches linearly. getRandom is O(1) by random index. Overall, remove dominates time complexity.

💡 For n=100000, remove could take up to 100000 operations, which is too slow for large inputs.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large datasets but helps understand the problem and why optimization is needed.

🧠

Hash Map + List with Index Tracking

💡 This approach improves remove operation by using a hash map to track indices of each value, enabling O(1) removals by swapping with the last element.

Intuition

Use a list to store elements and a hash map from value to a set of indices where it appears. On removal, swap the target element with the last element in the list and update indices in the map.

Algorithm

1. Maintain a list of elements and a hash map from val to a set of indices where val appears.
2. For insert(val), append val to list and add index to map[val]. Return true if val was not present before.
3. For remove(val), if val not in map or map[val] empty, return false.
4. Otherwise, get an index of val from map[val], swap element at that index with last element in list, update map accordingly, and pop last element.
5. Return true after removal.
6. For getRandom(), pick a random index from list and return element.

💡 The key insight is swapping with the last element to avoid costly shifts and updating the map to keep indices accurate.

</>

Code

import random
from collections import defaultdict

class RandomizedCollection:
    def __init__(self):
        self.nums = []
        self.idx_map = defaultdict(set)

    def insert(self, val: int) -> bool:
        self.nums.append(val)
        self.idx_map[val].add(len(self.nums) - 1)
        return len(self.idx_map[val]) == 1

    def remove(self, val: int) -> bool:
        if not self.idx_map[val]:
            return False
        remove_idx = self.idx_map[val].pop()
        last_val = self.nums[-1]
        self.nums[remove_idx] = last_val
        self.idx_map[last_val].add(remove_idx)
        self.idx_map[last_val].discard(len(self.nums) - 1)
        self.nums.pop()
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)

# Driver code
rc = RandomizedCollection()
print(rc.insert(1))  # True
print(rc.insert(1))  # False
print(rc.insert(2))  # True
print(rc.getRandom())  # 1 or 2
print(rc.remove(1))  # True
print(rc.getRandom())  # 1 or 2

Line Notes

self.nums = []List stores all elements for O(1) random access

self.idx_map = defaultdict(set)Map from val to set of indices for O(1) removals

self.nums.append(val)Add val to end of list

self.idx_map[val].add(len(self.nums) - 1)Record index of newly added val

remove_idx = self.idx_map[val].pop()Get an index of val to remove

last_val = self.nums[-1]Get last element to swap with removed element

self.nums[remove_idx] = last_valOverwrite removed element with last element

self.idx_map[last_val].add(remove_idx)Update last element's index set with new index

self.idx_map[last_val].discard(len(self.nums) - 1)Remove old index of last element

self.nums.pop()Remove last element from list

import java.util.*;

class RandomizedCollection {
    List<Integer> nums;
    Map<Integer, Set<Integer>> idxMap;
    Random rand;

    public RandomizedCollection() {
        nums = new ArrayList<>();
        idxMap = new HashMap<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        nums.add(val);
        idxMap.putIfAbsent(val, new HashSet<>());
        idxMap.get(val).add(nums.size() - 1);
        return idxMap.get(val).size() == 1;
    }

    public boolean remove(int val) {
        if (!idxMap.containsKey(val) || idxMap.get(val).isEmpty()) return false;
        int removeIdx = idxMap.get(val).iterator().next();
        idxMap.get(val).remove(removeIdx);
        int lastVal = nums.get(nums.size() - 1);
        nums.set(removeIdx, lastVal);
        idxMap.get(lastVal).add(removeIdx);
        idxMap.get(lastVal).remove(nums.size() - 1);
        nums.remove(nums.size() - 1);
        return true;
    }

    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }

    public static void main(String[] args) {
        RandomizedCollection rc = new RandomizedCollection();
        System.out.println(rc.insert(1));  // true
        System.out.println(rc.insert(1));  // false
        System.out.println(rc.insert(2));  // true
        System.out.println(rc.getRandom());  // 1 or 2
        System.out.println(rc.remove(1));  // true
        System.out.println(rc.getRandom());  // 1 or 2
    }
}

Line Notes

nums = new ArrayList<>()List to store elements for O(1) random access

idxMap = new HashMap<>()Map from val to set of indices for O(1) removals

nums.add(val)Add val to end of list

idxMap.putIfAbsent(val, new HashSet<>())Initialize set for val if absent

idxMap.get(val).add(nums.size() - 1)Add index of newly inserted val

int removeIdx = idxMap.get(val).iterator().next()Get an index of val to remove

nums.set(removeIdx, lastVal)Swap last element into removed element's position

idxMap.get(lastVal).add(removeIdx)Update lastVal's indices with new position

idxMap.get(lastVal).remove(nums.size() - 1)Remove old index of lastVal

nums.remove(nums.size() - 1)Remove last element from list

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cstdlib>
#include <ctime>

using namespace std;

class RandomizedCollection {
    vector<int> nums;
    unordered_map<int, unordered_set<int>> idxMap;
public:
    RandomizedCollection() {
        srand(time(0));
    }

    bool insert(int val) {
        nums.push_back(val);
        idxMap[val].insert(nums.size() - 1);
        return idxMap[val].size() == 1;
    }

    bool remove(int val) {
        if (idxMap.find(val) == idxMap.end() || idxMap[val].empty()) return false;
        int removeIdx = *idxMap[val].begin();
        idxMap[val].erase(removeIdx);
        int lastVal = nums.back();
        nums[removeIdx] = lastVal;
        idxMap[lastVal].insert(removeIdx);
        idxMap[lastVal].erase(nums.size() - 1);
        nums.pop_back();
        return true;
    }

    int getRandom() {
        int idx = rand() % nums.size();
        return nums[idx];
    }
};

int main() {
    RandomizedCollection rc;
    cout << rc.insert(1) << endl;  // 1 (true)
    cout << rc.insert(1) << endl;  // 0 (false)
    cout << rc.insert(2) << endl;  // 1 (true)
    cout << rc.getRandom() << endl;  // 1 or 2
    cout << rc.remove(1) << endl;  // 1 (true)
    cout << rc.getRandom() << endl;  // 1 or 2
    return 0;
}

Line Notes

vector<int> nums;Store elements for O(1) random access

unordered_map<int, unordered_set<int>> idxMap;Map from val to set of indices for O(1) removals

nums.push_back(val);Add val to end of vector

idxMap[val].insert(nums.size() - 1);Record index of inserted val

int removeIdx = *idxMap[val].begin();Get an index of val to remove

nums[removeIdx] = lastVal;Swap last element into removed element's position

idxMap[lastVal].insert(removeIdx);Update lastVal's indices with new position

idxMap[lastVal].erase(nums.size() - 1);Remove old index of lastVal

nums.pop_back();Remove last element from vector

class RandomizedCollection {
    constructor() {
        this.nums = [];
        this.idxMap = new Map();
    }

    insert(val) {
        if (!this.idxMap.has(val)) this.idxMap.set(val, new Set());
        this.nums.push(val);
        this.idxMap.get(val).add(this.nums.length - 1);
        return this.idxMap.get(val).size === 1;
    }

    remove(val) {
        if (!this.idxMap.has(val) || this.idxMap.get(val).size === 0) return false;
        const removeIdx = this.idxMap.get(val).values().next().value;
        this.idxMap.get(val).delete(removeIdx);
        const lastVal = this.nums[this.nums.length - 1];
        this.nums[removeIdx] = lastVal;
        this.idxMap.get(lastVal).add(removeIdx);
        this.idxMap.get(lastVal).delete(this.nums.length - 1);
        this.nums.pop();
        return true;
    }

    getRandom() {
        const idx = Math.floor(Math.random() * this.nums.length);
        return this.nums[idx];
    }
}

// Driver code
const rc = new RandomizedCollection();
console.log(rc.insert(1));  // true
console.log(rc.insert(1));  // false
console.log(rc.insert(2));  // true
console.log(rc.getRandom());  // 1 or 2
console.log(rc.remove(1));  // true
console.log(rc.getRandom());  // 1 or 2

Line Notes

this.nums = []Array to store elements for O(1) random access

this.idxMap = new Map()Map from val to set of indices for O(1) removals

this.nums.push(val)Add val to end of array

this.idxMap.get(val).add(this.nums.length - 1)Record index of inserted val

const removeIdx = this.idxMap.get(val).values().next().valueGet an index of val to remove

this.nums[removeIdx] = lastValSwap last element into removed element's position

this.idxMap.get(lastVal).add(removeIdx)Update lastVal's indices with new position

this.idxMap.get(lastVal).delete(this.nums.length - 1)Remove old index of lastVal

this.nums.pop()Remove last element from array

⏱

Complexity

TimeAverage O(1) for insert, remove, and getRandom

SpaceO(n) for storing elements and index sets

Insert appends and updates map in O(1). Remove swaps and updates map in O(1). getRandom picks random index in O(1).

💡 For n=100000, all operations complete in constant time, making this approach scalable.

Interview Verdict: Accepted / Optimal for interview coding

This approach is the standard solution and expected in interviews for this problem.

🧠

Optimized Hash Map + List with Linked List for Indices

💡 This approach replaces the set of indices with a doubly linked list per value to optimize index removals and insertions, reducing overhead in some languages.

Intuition

Instead of a set, maintain a doubly linked list of indices for each value to allow O(1) removal of indices without hashing overhead. The rest of the approach is similar to approach 2.

Algorithm

1. Maintain a list of elements and a map from val to a doubly linked list of indices.
2. For insert(val), append val to list and add index to val's linked list.
3. For remove(val), remove an index from val's linked list, swap with last element in list, update linked lists accordingly.
4. For getRandom(), pick a random index from list and return element.

💡 Using linked lists for indices avoids hashing overhead and can improve performance in some environments.

</>

Code

import random

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def append(self, val):
        node = Node(val)
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
        return node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def is_empty(self):
        return self.head.next == self.tail

class RandomizedCollection:
    def __init__(self):
        self.nums = []
        self.idx_map = {}
        self.node_map = {}

    def insert(self, val: int) -> bool:
        if val not in self.idx_map:
            self.idx_map[val] = DoublyLinkedList()
        self.nums.append(val)
        node = self.idx_map[val].append(len(self.nums) - 1)
        self.node_map[len(self.nums) - 1] = node
        # Return True if val was not present before insertion
        return self.idx_map[val].head.next == node and node.next == self.idx_map[val].tail

    def remove(self, val: int) -> bool:
        if val not in self.idx_map or self.idx_map[val].is_empty():
            return False
        node = self.idx_map[val].head.next
        remove_idx = node.val
        self.idx_map[val].remove(node)

        last_val = self.nums[-1]
        self.nums[remove_idx] = last_val

        last_node = self.node_map[len(self.nums) - 1]
        self.node_map[remove_idx] = last_node
        last_node.val = remove_idx

        self.nums.pop()
        del self.node_map[len(self.nums)]

        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)

# Driver code
rc = RandomizedCollection()
print(rc.insert(1))  # True
print(rc.insert(1))  # False
print(rc.insert(2))  # True
print(rc.getRandom())  # 1 or 2
print(rc.remove(1))  # True
print(rc.getRandom())  # 1 or 2

Line Notes

class Node:Node class for doubly linked list to store indices

class DoublyLinkedList:Doubly linked list to hold indices for each val

self.idx_map[val] = DoublyLinkedList()Initialize linked list for val if absent

node = self.idx_map[val].append(len(self.nums) - 1)Append new index node to val's linked list

self.node_map[len(self.nums) - 1] = nodeMap index to node for O(1) access

return self.idx_map[val].head.next == node and node.next == self.idx_map[val].tailReturn True if val was not present before insertion (list had no nodes)

node = self.idx_map[val].head.nextGet node to remove from linked list

self.idx_map[val].remove(node)Remove node from linked list

last_node.val = remove_idxUpdate last node's index value after swap

del self.node_map[len(self.nums)]Remove mapping for popped index

/* Due to complexity and verbosity, this approach is rarely implemented in Java interviews. The concept is similar to approach 2 but uses linked lists for index tracking. */

Line Notes

/* Due to complexity and verbosityLinked list index tracking is complex and rarely used in Java interviews

The concept is similar to approach 2Same logic but with linked list instead of sets

*/Placeholder to indicate approach not implemented here

/* Due to complexity and verbosity, this approach is rarely implemented in C++ interviews. The concept is similar to approach 2 but uses linked lists for index tracking. */

Line Notes

/* Due to complexity and verbosityLinked list index tracking is complex and rarely used in C++ interviews

The concept is similar to approach 2Same logic but with linked list instead of sets

*/Placeholder to indicate approach not implemented here

/* Due to complexity and verbosity, this approach is rarely implemented in JavaScript interviews. The concept is similar to approach 2 but uses linked lists for index tracking. */

Line Notes

/* Due to complexity and verbosityLinked list index tracking is complex and rarely used in JavaScript interviews

The concept is similar to approach 2Same logic but with linked list instead of sets

*/Placeholder to indicate approach not implemented here

⏱

Complexity

TimeO(1) average for insert, remove, and getRandom

SpaceO(n) for storing elements and linked list nodes

Linked list operations for indices are O(1), similar to set operations but with less hashing overhead.

💡 This approach is a theoretical optimization that can help in some languages but is more complex to implement.

Interview Verdict: Accepted but rarely used in practice

This approach is more complex and rarely required; approach 2 is preferred in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 is the best balance of simplicity and efficiency and should be coded in most interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) remove, O(1) insert/getRandom	O(n)	No	N/A	Mention only - never code
2. Hash Map + List with Index Tracking	Average O(1) for all operations	O(n)	No	N/A	Code this approach
3. Linked List for Indices	Average O(1)	O(n)	No	N/A	Mention if asked about further optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Describe the brute force approach and its inefficiencies.Step 3: Introduce the hash map + list approach for O(1) operations.Step 4: Code the optimal solution carefully, explaining each step.Step 5: Test with edge cases and discuss possible follow-ups.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test: 7min. Total ~30min

What the Interviewer Tests

Ability to design complex data structures, handle duplicates, maintain O(1) operations, and write clean, bug-free code.

Common Follow-ups

• How to handle duplicates efficiently? → Use a map from val to indices set.
• Can you optimize space or time further? → Linked list for indices or balanced trees (rare).

💡 Follow-ups test deeper understanding of data structure tradeoffs and edge case handling.

🔍

Pattern Recognition

When to Use

1) Need O(1) insert, remove, getRandom; 2) Duplicates allowed; 3) Random access required; 4) Efficient index tracking needed.

Signature Phrases

Insert Delete GetRandom O(1)Duplicates allowedRandom element with equal probability

NOT This Pattern When

Problems requiring order statistics or range queries are different patterns.

Similar Problems

Insert Delete GetRandom O(1) - simpler version without duplicatesDesign data structure with O(1) insert and delete - no randomRandomized Set - no duplicates allowed

Practice

1. You need to design a stack data structure that supports the usual push and pop operations, but also an increment operation that adds a given value to the bottom k elements of the stack efficiently. Which approach guarantees the most optimal time complexity for a sequence of n operations?

easy

A. Use a balanced binary search tree to store elements and increments, allowing O(log n) updates and queries.

B. Directly increment the bottom k elements on each increment call, resulting in O(n*k) time for n operations.

C. Use a lazy increment array to record increments and propagate them during pop operations, achieving O(n) total time.

D. Maintain a prefix sum array of increments and update it on each increment call, applying increments during pop.

Solution

1. Step 1: Understand the problem constraints

   The increment operation must be efficient even when called multiple times, so directly incrementing bottom k elements each time (O(n*k)) is too slow.

2. Step 2: Recognize the lazy increment pattern

   Using an auxiliary array to store increments lazily and applying them during pop operations reduces total time to O(n), as increments are propagated only once per element.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Lazy increments avoid repeated updates, achieving O(n) total time [OK]

Hint: Lazy increments reduce repeated updates to O(n) total time [OK]

Common Mistakes:

• Directly incrementing elements each time causes TLE
• Using complex data structures unnecessarily

2. You need to design a system that supports posting tweets and retrieving the 10 most recent tweets from a user's timeline, including tweets from users they follow. Which approach best balances efficient posting and retrieving the top recent tweets in real-time?

easy

A. Store all tweets in a global list and scan it entirely each time to find the top 10 recent tweets.

B. Maintain a linked list of tweets per user, a hashmap for followees, and use a max heap to merge the most recent tweets from followees efficiently.

C. Use a dynamic programming approach to precompute the top tweets for each user after every post.

D. Use a simple array per user and sort all tweets from followees every time the feed is requested.

Solution

1. Step 1: Understand the problem constraints

   The system must support fast posting and retrieving the top 10 recent tweets from a user's followees including themselves.

2. Step 2: Evaluate approaches

   Brute force scanning or sorting all tweets each time is inefficient. DP is not applicable here. Using linked lists per user and a max heap for merging recent tweets achieves O(1) posting and O(k log F) retrieval, where F is followees count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linked list + hashmap + heap is the optimal pattern for this problem [OK]

Hint: Linked list + heap merges recent tweets efficiently [OK]

Common Mistakes:

• Thinking sorting all tweets each time is efficient
• Trying DP for a streaming feed problem

3. 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

4. You need to design a data structure that supports setting values at indices, taking snapshots of the entire array state, and retrieving values at any snapshot efficiently. Which approach best balances time and space complexity for frequent set and get operations?

easy

A. Store full copies of the array on every snapshot to allow O(1) get operations.

B. Maintain a hash map per index storing (snap_id, value) pairs and use binary search to retrieve values for get operations.

C. Use a single global hash map keyed by (index, snap_id) and perform linear search for get operations.

D. Use a segment tree to store snapshots and query values at any snapshot.

Solution

1. Step 1: Understand problem requirements

   The data structure must efficiently support set, snap, and get operations with many snapshots and updates.

2. Step 2: Evaluate approaches

   Storing full snapshots (B) uses too much space and is slow for many snaps. A global hash map with linear search (C) makes get operations slow. Segment trees (D) are complex and not optimal here. Using a hash map per index with binary search (A) allows O(1) amortized set and snap, and O(log m) get, balancing time and space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search per index enables fast retrieval [OK]

Hint: Binary search per index enables fast retrieval [OK]

Common Mistakes:

• Thinking full snapshots are efficient for many snaps
• Using linear search for get causes slow queries

5. What is the time complexity of adding a number and then finding the median using the balanced two heaps approach with lazy deletion for a data stream of size n?

medium

A. O(log n) per addNum and O(log n) per findMedian

B. O(n) per addNum and O(1) per findMedian

C. O(log n) per addNum and O(1) per findMedian

D. O(1) per addNum and O(n) per findMedian

Solution

1. Step 1: Analyze addNum complexity

   Adding a number involves pushing to a heap and balancing heaps, each O(log n) operations.

2. Step 2: Analyze findMedian complexity

   Median is retrieved from the top of heaps without modification, O(1) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Insertion is O(log n), median retrieval O(1) [OK]

Hint: Heap push/pop are O(log n), median peek is O(1) [OK]

Common Mistakes:

• Assuming sorting each query is O(log n)
• Confusing addNum with findMedian complexity