Skip to main content

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 Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →