380. Insert Delete GetRandom O(1)

mediumAsked at Pinterest

Pinterest's experimentation and A/B-testing infrastructure picks random users from a live cohort. Insert Delete GetRandom O(1) asks you to build a set with O(1) add, remove, and uniform random sample — the dynamic-array + index-map combo is the canonical answer.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

Glassdoor (2026-Q1)— Pinterest backend / experimentation-infra onsite reports cite this as the data-structure-design round.
LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list.

Problem

Implement the RandomizedSet class: bool insert(int val) — inserts val, returns true if val was not already present; bool remove(int val) — removes val if present, returns true; int getRandom() — returns a random element from the current set of elements (each element has the same probability of being returned). All three operations must run in O(1) average time complexity.

Constraints

-2^31 <= val <= 2^31 - 1
At most 2 * 10^5 calls in total 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 r; r.insert(1); r.remove(2); r.insert(2); r.getRandom(); r.remove(1); r.insert(2); r.getRandom();

Output

[null,true,false,true,1_or_2,true,false,2]

Approaches

1. HashSet + convert to array on getRandom (brute force)

Use a Set for insert and remove; on getRandom, convert to an array and uniform-pick.

Time: O(1) insert/remove, O(n) getRandom
Space: O(n)

class RandomizedSetBrute {
  constructor() { this.s = new Set(); }
  insert(val) {
    if (this.s.has(val)) return false;
    this.s.add(val); return true;
  }
  remove(val) {
    if (!this.s.has(val)) return false;
    this.s.delete(val); return true;
  }
  getRandom() {
    const arr = [...this.s];
    return arr[Math.floor(Math.random() * arr.length)];
  }
}

Tradeoff: Fails the O(1) constraint on getRandom because the array conversion is O(n). The interviewer will reject this — use it only to anchor.

2. Dynamic array + value-to-index map (optimal)

Keep a list (for O(1) random access) and a Map<val, index> (for O(1) lookup). On remove, swap the target with the last element to keep the array dense, then pop.

Time: O(1) insert/remove/getRandom
Space: O(n)

class RandomizedSet {
  constructor() {
    this.list = [];
    this.indexOf = new Map(); // val -> position in list
  }
  insert(val) {
    if (this.indexOf.has(val)) return false;
    this.indexOf.set(val, this.list.length);
    this.list.push(val);
    return true;
  }
  remove(val) {
    if (!this.indexOf.has(val)) return false;
    const idx = this.indexOf.get(val);
    const last = this.list[this.list.length - 1];
    this.list[idx] = last;
    this.indexOf.set(last, idx);
    this.list.pop();
    this.indexOf.delete(val);
    return true;
  }
  getRandom() {
    return this.list[Math.floor(Math.random() * this.list.length)];
  }
}

Tradeoff: Three operations all O(1). The swap-with-last trick on remove is the crux — narrate why it preserves array density and what would happen without it (the list would grow holes and getRandom would need rejection sampling).

Pinterest-specific tips

Pinterest interviewers want you to volunteer the edge case unprompted: 'what if I'm removing the last element? The swap is a no-op but the index update on `last` would clobber the entry I'm about to delete — let me make sure my order is: write last to idx, set indexOf[last]=idx, pop list, delete indexOf[val].' Walking through that order out loud is a strong signal.

Common mistakes

Forgetting to update indexOf for the swapped-in element — the map goes stale and subsequent removes break.
Order-of-operations bug on remove-the-last-element: if val IS the last element, you must still execute correctly. Walking the steps in the right order handles this naturally.
Using Set + Array<val>.indexOf for remove — indexOf is O(n), defeats the purpose.
Math.random() * list.length without Math.floor — returns a float.

Follow-up questions

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

Allow duplicates (LeetCode 381) — value to a Set of indices.
Weighted insert (each val has a weight; pick weighted random).
Range queries: getRandom from a subset matching a predicate.
Persistence: support undo (snapshot the state).

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 the swap-with-last trick instead of splicing?

Array.splice is O(n) because it shifts every subsequent element. Swap-with-last is O(1) and preserves the property that the array contains exactly the current set members in indices [0, size).

Why does Pinterest specifically care about uniform random sampling?

A/B-test cohort assignment, control-group selection, and exploration sampling all need uniform random over an evolving set. This data structure is the production primitive.

Free learning resources

Curated free links for this problem.