Insert Delete GetRandom O(1)
Build a set of whole numbers that can also hand back a random member. insert(val) adds val and returns true, or returns false if val was already there. remove(val) takes val out and returns true, or returns false if val was not there. getRandom() returns one of the numbers in the set right now, each member equally likely; it is only called when the set is not empty. Aim for O(1) on average for all three. The script driver below replays a list of calls. For each getRandom it calls your method many times (60 draws, or 200 when the set holds 4 numbers or fewer), checks every draw against its own record of the set, and for a small set checks that every member shows up at least once. It reports true when all of that holds. For insert and remove it reports what your class returned. For long scripts it also reads insertRun(start, count, step) and removeRun(start, count, step): they call insert or remove on start, start+step, start+2*step, ... in order, and report true when every one of those calls answered what a plain set would. getRandomRun(count) makes the getRandom check count times and reports true when all of them held. Limits: at most 600000 inserts and removes in one script (a run counts every number in it), -2147483648 <= val <= 2147483647. Example: RandomizedSet() insert(4) -> true, insert(4) -> false, insert(9) -> true remove(4) -> true, remove(4) -> false getRandom() -> 9 (the only member left)
You're building a set that can also hand back a random member, and every call has to be O(1) on average. Interviewers love it because each obvious structure fails at least one of the three calls, so you have to combine two. The classic trap is what happens to the last element when you remove one from the middle. Expect up to 600,000 inserts and removes in one script.
Examples
You write
RandomizedSet: insert(val: int), remove(val: int), get_random()
Example 1
- Input
- RandomizedSet(), insert(4) => true, insert(4) => false, insert(9) => true, remove(4) => true, remove(4) => false, getRandom() => true, insert(4) => true, getRandom() => true, remove(9) => true, getRandom() => true
- returns
- [true, false, true, true, false, true, true, true, true, true]
Example 2
- Input
- RandomizedSet(), remove(5) => false, insert(5) => true, remove(5) => true, remove(5) => false, insert(5) => true, getRandom() => true
- returns
- [false, true, true, false, true, true]
Save this for your laptop
The editor and Run need a bigger screen. The link opens Insert Delete GetRandom O(1) ready to code. It is free, and the editor needs no account.
The pattern behind it
Design
I reach for it when
- The statement describes a class with methods, not one function.
- Each method needs to be fast, and the structure decides how fast.
Say this before you type. Say each method, the cost you want from it, and the structure that earns that cost.
All 28 Design problemsArrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.