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

2. What is the space complexity of the optimal approach that copies a linked list with random pointers by interleaving copied nodes within the original list?

medium

A. O(1) because no extra data structures proportional to n are used

B. O(n) due to storing all copied nodes in a hash map

C. O(n) due to recursion stack in the copying process

D. O(n) because of auxiliary arrays used to track random pointers

Solution

1. Step 1: Identify auxiliary data structures

   The optimal approach does not use hash maps or arrays; it weaves copied nodes into the original list.

2. Step 2: Analyze space usage

   Only a few pointers are used; no extra space proportional to n is allocated, so space complexity is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No hash maps or recursion stacks used [OK]

Hint: Interleaving nodes avoids extra space [OK]

Common Mistakes:

• Assuming hash map is always needed, so O(n) space
• Confusing recursion stack space with iterative approach
• Thinking auxiliary arrays are used for random pointers

3. Examine the following buggy code snippet for the MedianFinder class. Which line contains the subtle bug that can cause incorrect median calculation?

medium

A. Condition 'if self.low_size > self.high_size:' for balancing heaps

B. Line that pushes to high heap and increments high_size

C. Line that pushes to low heap and increments low_size

D. Condition 'elif self.high_size > self.low_size + 1:' for balancing heaps

Solution

1. Step 1: Understand balancing condition

   The heaps must be balanced so that their sizes differ by at most 1.

2. Step 2: Identify incorrect condition

   The condition 'if self.low_size > self.high_size:' moves an element from low to high even when sizes differ by only 1, causing imbalance.

3. Step 3: Correct condition

   The condition should be 'if self.low_size > self.high_size + 1:' to ensure size difference is more than 1 before balancing.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Balancing condition must check if low_size > high_size + 1 [OK]

Hint: Balance heaps only if size difference > 1 [OK]

Common Mistakes:

• Balancing heaps too aggressively
• Incorrect size difference checks

4. Consider the following buggy implementation of SnapshotArray. Which line contains the subtle bug that can cause incorrect get results when multiple sets occur before a snap on the same index?

import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.data = [[(-1, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        # Bug here
        self.data[index].append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

medium

A. Line in snap(): incrementing snap_id before returning

B. Line in __init__(): initializing with (-1, 0) instead of (0, 0)

C. Line in set(): always appending without checking if last snap_id matches

D. Line in get(): using bisect_right instead of bisect_left

Solution

1. Step 1: Analyze set() method

   The set method always appends (snap_id, val) without checking if the last entry has the same snap_id, causing duplicate entries for the same snap_id.

2. Step 2: Consequence on get()

   Duplicate entries for the same snap_id break binary search assumptions and can cause get to return incorrect values.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct code replaces last entry if snap_id matches [OK]

Hint: Check if last snap_id matches before appending in set() [OK]

Common Mistakes:

• Appending blindly causes duplicates
• Misunderstanding initialization defaults

5. Suppose the multilevel doubly linked list can have cycles introduced via child pointers (i.e., a child pointer may point to an ancestor node). Which modification to the flattening algorithm is necessary to handle this safely?

hard

A. Use recursion with a depth limit to prevent stack overflow on cycles.

B. Remove all child pointers before flattening to guarantee acyclic structure.

C. Use a hash set to track visited nodes and skip already visited ones to avoid infinite loops.

D. No modification needed; the existing in-place iterative approach handles cycles naturally.

Solution

1. Step 1: Understand the problem with cycles

   Cycles cause infinite loops during traversal if nodes are revisited.

2. Step 2: Identify safe traversal method

   Tracking visited nodes with a hash set prevents revisiting and infinite loops.

3. Step 3: Evaluate other options

   Removing child pointers loses structure; recursion depth limit is unreliable; existing code does not detect cycles.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Visited set prevents infinite loops in cyclic graphs [OK]

Hint: Track visited nodes to handle cycles safely [OK]

Common Mistakes:

• Assuming no cycles exist in input
• Relying on recursion depth limits
• Ignoring cycle detection altogether