Skip to main content

380. Insert Delete GetRandom O(1)

mediumAsked at Shopify

Shopify asks this to test whether you can combine a hash map with an array to achieve O(1) on three operations that pull in opposite directions. It's the data-structure design round Shopify favors for backend candidates — A/B-test variant sampling, random product pickers, raffle systems all reduce to it.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Senior Backend Developer + Engineering Lead onsites cite Insert Delete GetRandom as a data-structure design round.
  • Blind (2025-12)— Shopify L4/L5 offers reference this problem as the 'composite data structure' round.

Problem

Implement the RandomizedSet class. insert(val) inserts val if not present and returns true, or returns false. remove(val) removes val if present and returns true, or returns false. getRandom() returns a random element from the current set; each element must have the same probability of being returned. All three must run in average O(1) time.

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

Explanation: After all operations, the set contains only 2.

Approaches

1. Hash map alone (fails getRandom)

A plain hash set gives O(1) insert/remove but getRandom requires iterating to the n-th element, which is O(n).

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) {
    if (!this.set.has(val)) return false;
    this.set.delete(val);
    return true;
  }
  getRandom() {
    const arr = Array.from(this.set);
    return arr[Math.floor(Math.random() * arr.length)];
  }
}

Tradeoff: Simple but fails the O(1) getRandom requirement — Array.from is O(n). Mention this only to motivate why we need both structures together.

2. Hash map + dynamic array (canonical optimal)

Store values in an array (gives O(1) random index access) and a hash map from value to its array index (gives O(1) presence check + index lookup). On remove, swap the target with the last element, pop, and update the map. Swap-with-last is the trick.

Time
O(1) average for all three
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 textbook answer. The array gives O(1) random index access; the map gives O(1) presence + index lookup. The swap-with-last trick is what makes remove O(1) without leaving holes in the array.

Shopify-specific tips

Shopify's expected follow-up is the LeetCode 381 variant: 'now allow duplicates'. The data structure becomes a Map<value, Set<index>>. Senior candidates are also asked 'what if remove must preserve insertion order' (answer: doubly-linked list + map, sacrificing O(1) random access). Always volunteer the duplicates variant — it's the single most common Shopify follow-up.

Common mistakes

  • Forgetting to update the swapped element's index in the map (corrupts subsequent removes).
  • Removing val from the map BEFORE the swap — if val is the last element, the swap is a no-op but you still need to update the map correctly. Order matters.
  • Using Math.random() * arr.length without Math.floor (returns a float).
  • Treating the dynamic array's .pop() as O(n) — it's O(1) amortized in JS.

Follow-up questions

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

  • Allow duplicates — LeetCode 381 (RandomizedCollection).
  • Preserve insertion order on getRandom (sacrifice average-case O(1) for some op).
  • Add a getRandomK(k) that returns k distinct random elements.
  • What if values can be very large objects, not ints? (Map<id, value> indirection.)

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 the last element on remove?

Because Array.splice in the middle is O(n) — it shifts all later elements left. Swapping the target with the last element lets us pop the tail in O(1). The map tells us the index of the swapped element so we can update its mapping.

Is Math.random() truly uniform?

Math.random() in modern V8 uses xorshift128+ and is uniform for our purposes. For cryptographic uniformity you'd use crypto.getRandomValues, but the interview answer just needs to be 'yes, uniform; each index has equal probability'.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →