Skip to main content

18. Insert Delete GetRandom O(1)

mediumAsked at Confluent

Design a set with O(1) insert, remove, and random selection — Confluent uses it because the dense-array + map trick is the same one that lets a consumer group pick a partition uniformly during sampling.

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

Problem

Implement RandomizedSet supporting insert(val), remove(val), and getRandom() — all in average O(1) time. getRandom must return a uniformly random element of the current set.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 2*10^5 calls
  • There will be at least one element when getRandom is called

Examples

Example 1

Input
insert(1); insert(2); getRandom()
Output
1 or 2

Example 2

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

Approaches

1. Set only

Hash set for insert/remove; iterate to a random index for getRandom.

Time
O(n) random
Space
O(n)
// set.has/add/delete = O(1); getRandom walks to a random index = O(n)

Tradeoff:

2. Array plus index map

Keep values in an array and their indices in a map. To remove, swap the target with the last element, pop, and update the swapped index. getRandom is array[random()].

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

Tradeoff:

Confluent-specific tips

Confluent will ask how the dense-array idea applies to partition sampling — explain how a per-broker array of assigned partitions keeps getRandom O(1) without breaking exactly-once semantics during rebalance.

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 Confluent interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →