Skip to main content

80. Insert Delete GetRandom O(1)

mediumAsked at Salesforce

Design a data structure supporting insert, delete, and getRandom all in O(1). Salesforce uses this as the canonical 'when do you need both array and map' problem.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses array+map for indexed-random sampling in ML pipelines.
  • Blind (2025-10)— Common Salesforce backend onsite design question.

Problem

Implement the RandomizedSet class: bool insert(int val) - inserts an item val into the set if not present. Returns true if not present, false otherwise. bool remove(int val) - removes an item val from the set if present. Returns true if present, false otherwise. int getRandom() - returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned. All operations must be average O(1).

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls in total will be made.
  • There will be at least one element in the data structure when getRandom is called.

Examples

Example 1

Input
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]
Output
[null,true,false,true,2,true,false,2]

Approaches

1. Map only

Set for O(1) insert/delete/contains; iterate for random.

Time
O(n) for getRandom
Space
O(n)
// Random scan is O(n).

Tradeoff: getRandom is O(n) — fails the requirement.

2. Array + index map

Array holds values. Map: val → index in array. Insert appends. Delete swaps with last, then pops. getRandom = arr[random index].

Time
O(1) all ops
Space
O(n)
class RandomizedSet {
  constructor() { this.arr = []; this.idx = new Map(); }
  insert(val) {
    if (this.idx.has(val)) return false;
    this.idx.set(val, this.arr.length);
    this.arr.push(val);
    return true;
  }
  remove(val) {
    if (!this.idx.has(val)) return false;
    const i = this.idx.get(val);
    const last = this.arr[this.arr.length - 1];
    this.arr[i] = last;
    this.idx.set(last, i);
    this.arr.pop();
    this.idx.delete(val);
    return true;
  }
  getRandom() {
    return this.arr[Math.floor(Math.random() * this.arr.length)];
  }
}

Tradeoff: The swap-with-last trick keeps the array dense, enabling O(1) random index. The map maintains val→index in sync.

Salesforce-specific tips

Salesforce specifically tests this swap-with-last pattern because it generalizes — anywhere you need O(1) random sampling from a mutable set. They grade on whether you remember to update the index map AFTER the swap. Bonus signal: discuss the variant LC 381 (with duplicates) which uses a map of value → Set of indices.

Common mistakes

  • Forgetting to update idx for the swapped-from-last element — corrupts the index map.
  • Removing before swapping — loses the value to swap with.
  • Trying to use Set directly — JS Set doesn't support indexed access in O(1).

Follow-up questions

An interviewer at Salesforce may pivot to one of these next:

  • Insert Delete GetRandom O(1) - Duplicates allowed (LC 381).
  • Random Pick with Weight (LC 528).
  • Implement a randomized priority queue.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why swap with last?

Removing an interior element naively requires shifting later elements (O(n)). Swapping with the last lets us pop() in O(1).

Why update idx for the swapped element?

Because its position changed. Without the update, future remove calls for it would find the wrong index.

Practice these live with InterviewChamp.AI

Drill Insert Delete GetRandom O(1) and other Salesforce interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →