918. Handmade Hash Map
A tiny embedded device has no dictionary type, so you must build one. Write the class HandmadeMap (no constructor arguments) that stores integer keys with integer values, without using any built-in hash table, dictionary or map of your language.
put(key, value)stores the pair; ifkeyis already stored, its value is replaced.get(key)returns the stored value, or -1 if the key is not stored.remove(key)deletes the key and its value; if the key is not stored, nothing happens.
Use a fixed array of buckets and resolve collisions with chains. Every call should run in expected O(1) time for the allowed number of calls.
Example 1
- Input:
- operations = ["HandmadeMap","put","put","get","put","get","remove","get"]arguments = [[],[250,9],[31,4],[250],[250,77],[250],[31],[31]]
- Output:
- [null,null,null,9,null,77,null,-1]
- Explanation:
Key 250 is overwritten from 9 to 77, and key 31 reads back as -1 after it is removed.
Example 2
- Input:
- operations = ["HandmadeMap","get","put","get","remove","remove","get"]arguments = [[],[0],[0,0],[0],[5],[0],[0]]
- Output:
- [null,-1,null,0,null,null,-1]
- Explanation:
A key never stored gives -1; value 0 is a legal value; removing an absent key (5) changes nothing.
Constraints
0 ≤ key ≤ 1000000
0 ≤ value ≤ 1000000
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)