Skip to main content

19. Insert Delete GetRandom O(1)

mediumAsked at Revolut

Design a set supporting O(1) insert, delete, and random pick, a Revolut systems-design favorite that mirrors picking a random active order from a hot ledger partition.

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

Problem

Implement RandomizedSet with insert(val), remove(val), and getRandom(), all in average O(1). All operations must be implemented in expected constant time.

Constraints

  • -2^31 <= val <= 2^31-1
  • At most 2 * 10^5 calls per op
  • getRandom called only when set is non-empty

Examples

Example 1

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

Example 2

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

Approaches

1. Hash set only

Insert/delete are O(1); but getRandom needs to materialize keys to pick, which is O(n).

Time
O(1)/O(1)/O(n)
Space
O(n)
// store in a Set; getRandom = [...set][Math.floor(Math.random()*set.size)]

Tradeoff:

2. Array + index map

Keep an array of values plus a map from value to its index. Removal swaps with the last slot to keep the array dense.

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

Tradeoff:

Revolut-specific tips

Revolut interviewers will push you on swap-with-last during removal — they want to hear you describe it as the same trick used in O(1) deletion from a sharded ledger active-orders array.

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

Practice these live with InterviewChamp.AI →