Skip to main content

380. Insert Delete GetRandom O(1)

mediumAsked at Google

Design a data structure that supports insert, remove, and getRandom — all in O(1) average. Google asks this to test whether you can combine a hash map (for O(1) lookup) with a dynamic array (for O(1) random access), and to see if you handle the 'swap to end before pop' trick for O(1) removal.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4 onsite reports cite this as the data-structure design round.
  • Reddit r/cscareerquestions (2025-11)— Recurring Google new-grad onsite question.

Problem

Implement the RandomizedSet class: insert(val) inserts an item, returns true if not already present. remove(val) removes an item, returns true if present. getRandom() returns a random element from the current set with equal probability. All three operations must average O(1).

Constraints

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

Examples

Example 1

Input
RandomizedSet(); insert(1); remove(2); insert(2); getRandom(); remove(1); insert(2); getRandom()
Output
[null, true, false, true, 1 or 2, true, false, 2]

Explanation: getRandom returns 1 or 2 randomly. After remove(1) and insert(2), only 2 exists, so getRandom returns 2.

Approaches

1. Hash set only

Use a Set for O(1) insert and remove. getRandom iterates to a random index.

Time
O(1) insert, O(1) remove, O(n) getRandom
Space
O(n)
class RandomizedSetSlow {
  constructor() { this.set = new Set(); }
  insert(val) { if (this.set.has(val)) return false; this.set.add(val); return true; }
  remove(val) { return this.set.delete(val); }
  getRandom() {
    const idx = Math.floor(Math.random() * this.set.size);
    let i = 0;
    for (const v of this.set) { if (i === idx) return v; i++; }
  }
}

Tradeoff: Fails the O(1) getRandom requirement — Set has no O(1) random access. Mention only to anchor the optimal.

2. Hash map + dynamic array with swap-to-end (optimal)

Array gives O(1) random index access. Hash map of val→arrayIndex gives O(1) lookup. On remove, swap target with the last element, then pop.

Time
O(1) average for all three
Space
O(n)
class RandomizedSet {
  constructor() {
    this.arr = [];
    this.idx = new Map(); // val -> index in arr
  }
  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() {
    const i = Math.floor(Math.random() * this.arr.length);
    return this.arr[i];
  }
}

Tradeoff: Each data structure provides the property the other lacks: the hash map gives lookup, the array gives random access. Swap-to-end is the trick that makes removal O(1) without shifting the rest of the array.

Google-specific tips

Google interviewers specifically grade the swap-to-end articulation. State it out loud: 'To remove in O(1), I'll move the target to the end first, then pop — that avoids shifting the rest of the array.' Forgetting to update the hash map index for the swapped element is the #1 bug.

Common mistakes

  • Forgetting to update idx[last] = i after the swap — leaves a dangling reference.
  • Trying to use only a hash set (no O(1) random access).
  • Using splice instead of pop+swap — splice is O(n).

Follow-up questions

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

  • What if duplicates are allowed (LC 381)? Hash map points to a Set of indices.
  • Make it thread-safe.
  • What if you also need O(1) snapshot() that returns all elements?

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-to-end?

Removing from the middle of an array is O(n) because everything to the right must shift. Swapping with the last element first means the removal is just a pop — O(1).

Is this truly O(1) or amortized?

Hash map operations are average O(1) (can be O(n) worst case on bad hashing). Array push is amortized O(1). For interview purposes, both qualify as O(1) average.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →