Medium · System Design

Insert Delete GetRandom O(1)

Given a sequence of operations on a RandomizedSet, where insert(val) and remove(val) return whether the set changed and getRandom() returns a uniformly random current element, return each call's result, with every operation running in O(1) average time.

Examples

Example 1

{
  "ops": [
    {"kind": "insert", "val": 1},
    {"kind": "insert", "val": 2},
    {"kind": "insert", "val": 3},
    {"kind": "remove", "val": 2},
    {"kind": "getRandom"}
  ],
  "randomIdx": 0
}

Output: [true, true, true, true, 1 or 3]

Example 2

{
  "ops": [
    {"kind": "insert", "val": 1},
    {"kind": "insert", "val": 1},
    {"kind": "insert", "val": 2},
    {"kind": "insert", "val": 3},
    {"kind": "remove", "val": 2},
    {"kind": "remove", "val": 3},
    {"kind": "remove", "val": 4},
    {"kind": "getRandom"}
  ],
  "randomIdx": 0
}

Output: [true, false, true, true, true, true, false, 1]

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.