Skip to main content

14. Insert Delete GetRandom O(1)

mediumAsked at Redis

Design a set supporting insert, remove and getRandom all in O(1); Redis loves it because SRANDMEMBER and dict-table sampling use the same trick.

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

Problem

Implement RandomizedSet with insert(val) (returns true if not present), remove(val) (returns true if present), and getRandom() returning a uniformly random element. All must run in average O(1).

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls

Examples

Example 1

Input
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]
Output
[null,true,false,true,2,true,false,2]

Approaches

1. Set + reservoir scan

JS Set for insert/remove, walk it to pick random.

Time
O(1) insert/remove, O(n) random
Space
O(n)
const s = new Set();
// getRandom: const arr = [...s]; return arr[Math.floor(Math.random()*arr.length)];

Tradeoff:

2. Array + index map (swap-pop trick)

Keep values in an array and a Map from value to its array index. On remove, swap the deleted index with the tail then pop. getRandom indexes the array. Same trick Redis uses internally for SRANDMEMBER on dict-encoded sets.

Time
O(1) per op
Space
O(n)
class RandomizedSet {
  constructor() { this.vals = []; this.idx = new Map(); }
  insert(v) {
    if (this.idx.has(v)) return false;
    this.idx.set(v, this.vals.length);
    this.vals.push(v);
    return true;
  }
  remove(v) {
    if (!this.idx.has(v)) return false;
    const i = this.idx.get(v);
    const last = this.vals[this.vals.length - 1];
    this.vals[i] = last;
    this.idx.set(last, i);
    this.vals.pop();
    this.idx.delete(v);
    return true;
  }
  getRandom() { return this.vals[Math.floor(Math.random() * this.vals.length)]; }
}

Tradeoff:

Redis-specific tips

Redis interviewers grade for the swap-pop trick because that's exactly how SRANDMEMBER stays O(1) on hashtable-encoded sets; mention the intset/hashtable encoding split.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →