Skip to main content

380. Insert Delete GetRandom O(1)

mediumAsked at Microsoft

Insert Delete GetRandom O(1) is Microsoft's go-to data-structure design medium. The trick is pairing an array (for O(1) random access by index) with a hash map (for O(1) value lookup), then doing the swap-with-last trick on delete.

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

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Azure/Bing org senior phone-screen reports list this as the canonical 30-minute design medium.
  • Levels.fyi (2025-12)— Microsoft L60/L61 interview compilations include Insert Delete GetRandom with the array+hash-map combination.

Problem

Implement the RandomizedSet class: RandomizedSet() initializes the RandomizedSet object. bool insert(int val) inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) removes an item val from the set if present. Returns true if the item was 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. You must implement the functions of the class such that each function works in average O(1) time complexity.

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","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]
Output
[null,true,false,true,2,true,false,2]

Explanation: Insert 1, remove 2 (false), insert 2, getRandom returns 2, remove 1, insert 2 (false because already present), getRandom returns 2.

Approaches

1. Array + hash map with swap-with-last on delete (optimal)

Store values in an array for O(1) random index. Hash-map value -> index for O(1) lookup. On delete, swap the target with the last element so the array stays compact.

Time
O(1) average per operation
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: Tight pairing: the array gives O(1) random access; the map gives O(1) lookup; the swap-with-last keeps deletion O(1) by avoiding the linear-shift cost. This combination is the entire interview.

2. Hash set only (rejected — getRandom is O(n))

Store values in a Set. getRandom by iterating to a random index.

Time
O(n) for getRandom
Space
O(n)
class RandomizedSet {
  constructor() { this.s = new Set(); }
  insert(val) { if (this.s.has(val)) return false; this.s.add(val); return true; }
  remove(val) { return this.s.delete(val); }
  getRandom() {
    const arr = Array.from(this.s);
    return arr[Math.floor(Math.random() * arr.length)];
  }
}

Tradeoff: Easy to write but getRandom is O(n) because hash sets don't support index access. Useful only as the reject example: 'a Set gives me O(1) insert and remove but not O(1) random — I need a structure with both.'

Microsoft-specific tips

Microsoft is grading whether you can articulate WHY both data structures are needed. Say it out loud: 'I need O(1) random index access, which means an array. I need O(1) value lookup for insert and remove, which means a hash map. The map stores value to array-index. The swap-with-last on delete is how I keep the array compact in O(1).' That paragraph IS the answer.

Common mistakes

  • Forgetting to update the map for the swapped element on delete — the map gets out of sync with the array.
  • Calling arr.splice(i, 1) instead of swap-with-last — splice is O(n), defeats the whole design.
  • Not handling the swap-when-target-is-last edge case — actually safe because writing the same value to itself then popping is a no-op, but call it out anyway.

Follow-up questions

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

  • Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) — same idea but the map stores a set of indices per value.
  • Random Pick with Blacklist (LC 710) — different randomization design.
  • What if getRandom needed weighted probabilities?

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 is the swap-with-last trick necessary?

Removing from the middle of an array would cost O(n) for the shift. Swapping the target with the last element and then popping costs O(1) and keeps the array dense (no gaps), which is what makes getRandom safe.

What if the target IS the last element?

The swap is a self-write (no-op), then pop removes it. The map delete still works. It's the same code path.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →