Skip to main content

380. Insert Delete GetRandom O(1)

mediumAsked at Robinhood

Design a data structure that supports insert, delete, and getRandom — all in average O(1). Robinhood likes this design problem because it forces you to combine an array (random access) with a hash map (membership / index lookup) cleanly.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE-II onsite reports list this as a recurring data-structure design problem.
  • Blind (2025-12)— Robinhood backend trip reports name this as a thematic favorite for combining array + hash map.

Problem

Implement the RandomizedSet class: bool insert(int val), bool remove(int val), int getRandom(). Each function must run in O(1) average time. insert returns true iff val was not already present. remove returns true iff val was present. getRandom returns a random element from the current set, with each element equally likely.

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

Explanation: First getRandom is 1 or 2 uniformly. Second getRandom must be 2.

Approaches

1. Hash set only

Use a Set for insert and remove. getRandom requires converting the set to an array and indexing.

Time
O(1) insert/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 = [...this.set];
    return arr[Math.floor(Math.random() * arr.length)];
  }
}

Tradeoff: Trivial but getRandom is O(n) because Set iteration order doesn't support O(1) indexing. Mention it as the baseline, then add the array.

2. Array + hash map (val → index)

Array gives O(1) random access. Map gives O(1) membership + index lookup. Delete = swap with last + pop.

Time
O(1) average all operations
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() {
    return this.arr[Math.floor(Math.random() * this.arr.length)];
  }
}

Tradeoff: True O(1) average. The swap-with-last trick is the key insight — keeps the array contiguous without shifting on delete.

Robinhood-specific tips

Robinhood interviewers care about two subtleties: (1) the swap-with-last on delete must also update the map entry for the swapped element; (2) the random index must be drawn uniformly from [0, length). Both are easy to flub. Walk through delete on paper before coding it. Be ready for the follow-up: 'now allow duplicates' (LC 381) — switch map values from int to Set of indices.

Common mistakes

  • Forgetting to update idx.set(last, i) after the swap — the map still points to the old (just-popped) slot.
  • Skipping the case where val is already the last element — your swap is a self-swap; that's fine but make sure pop still happens.
  • Using Math.floor(Math.random() * (n + 1)) — off-by-one; max should be n.

Follow-up questions

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

  • Insert Delete GetRandom O(1) - Duplicates Allowed (LC 381) — same shape with multiset semantics.
  • Design a Stack with O(1) getRandom — array + uniform draw.
  • Random Pick with Weight (LC 528) — prefix sum + binary search.

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 does the swap-with-last trick work?

Because the array doesn't need to maintain order for getRandom — uniform draws don't care about position. Swapping the deleted element with the last lets us pop in O(1) without shifting.

Is the average-case O(1) tight?

Yes, modulo hash-collision worst case. JS Map.set/get is amortized O(1). The array operations are strictly O(1).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →