380. Insert Delete GetRandom O(1)

mediumAsked at Airbnb

Design a set supporting insert, remove, and getRandom all in O(1) average. Airbnb asks this to test the array + hash-map-of-indices pattern — array gives O(1) random; hash map gives O(1) lookup; swap-remove keeps both true.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

Glassdoor (2026-Q1)— Airbnb L4/L5 onsite reports list this as a signature design medium.
Blind (2025-11)— Recurring in Airbnb backend interview reports.

Problem

Implement the RandomizedSet class: bool insert(int val) inserts an item val into the set if not present; bool remove(int val) removes an item if present; int getRandom() returns a random element from the current set of elements (it's guaranteed 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 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

insert(1); remove(2); insert(2); getRandom(); remove(1); insert(2); getRandom()

Output

[true,false,true,1 or 2,true,false,2]

Explanation: After insert(1), insert(2), getRandom returns 1 or 2 uniformly.

Approaches

1. Array + hash map of val -> index (optimal)

Array gives O(1) random access by index. Map gives O(1) lookup of val's index. On remove, swap the last element into the gap, then pop.

Time: O(1) average per op
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 swap-with-last trick is the key insight — it makes the array remove O(1) without leaving holes. Without it, you'd have O(n) shifts.

2. Set only (broken random)

A plain Set has O(1) insert/remove but no random-by-index. Walking to a random key is O(n).

Time: O(n) per getRandom
Space: O(n)

// Intentionally incorrect for O(1) random — teaching foil.
class RandomizedSetSet {
  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 idx = Math.floor(Math.random() * this.s.size);
    let i = 0;
    for (const v of this.s) { if (i === idx) return v; i++; }
  }
}

Tradeoff: Useful as a foil — it shows why getRandom in O(1) demands a dense array, not just a hash structure.

Airbnb-specific tips

Airbnb's bar on this is the swap-with-last trick said out loud: 'On remove, I swap the doomed element with the last element of the array, then pop. That makes remove O(1) and keeps the array dense — which keeps getRandom O(1).' Without that sentence, the answer looks like magic.

Common mistakes

Forgetting to update the index map for the swapped-in element.
Splicing out the element instead of swap-and-pop (gives O(n) remove).
Returning the array reference from getRandom instead of an element from it.

Follow-up questions

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

Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) — map value to a set of indices.
Design a Cache with TTL — variant requiring expiration tracking.
What if you needed weighted random? (Prefix sum + binary search — see LC 528.)

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 both an array AND a hash map?

Array gives O(1) random access by index. Map gives O(1) value-to-index. Neither alone supports all three operations in O(1).

Is the swap-with-last always safe?

Yes — the array is unordered, so reordering during remove is fine. We just need to keep the map in sync for the swapped element.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →