919. Handmade Hash Set
Implement the class HandmadeSet (no constructor arguments) that stores a set of non-negative integers. Using any built-in hash set, hash map, dictionary or ordered set of your language is forbidden; build the hashing yourself.
add(key)insertskey; inserting a key that is already present changes nothing.remove(key)deleteskey; if it is absent, nothing happens.contains(key)returnstrueif the key is currently in the set andfalseotherwise.
Keys can be as large as a billion, so a direct table is impossible. Spread the keys over a fixed array of buckets and chain collisions; each call should run in expected O(1) time.
Example 1
- Input:
- operations = ["HandmadeSet","add","add","contains","contains","remove","contains","contains"]arguments = [[],[808],[1839],[808],[1839],[808],[808],[1839]]
- Output:
- [null,null,null,true,true,null,false,true]
- Explanation:
808 and 1839 collide for a table of 1031 buckets (808 + 1031 = 1839) but still behave as independent members.
Example 2
- Input:
- operations = ["HandmadeSet","contains","add","add","contains","remove","contains","remove"]arguments = [[],[0],[0],[0],[0],[0],[0],[0]]
- Output:
- [null,false,null,null,true,null,false,null]
- Explanation:
Adding an existing key twice keeps one copy, so one removal empties it; the second removal is a no-op.
Constraints
0 ≤ key ≤ 109
At most 3000 calls in total
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(1) expected per call
- Space
- O(n)