Design HashMap
Learn this problem
ByteDanceNEW GRADONSITE INTERVIEWProblem statement
Implement an integer-keyed map without using a built-in map, dictionary, or hash-table container to store its entries. Arrays, lists, and your own node types are allowed.
Process three equal-length arrays from left to right. At index i, use operations[i], keys[i], and values[i] as follows:
put: insert the key with the supplied value, replacing its old value if present.get: append the key's current value to the answer, or-1if absent.remove: delete the key if present; removing an absent key has no effect.
values[i] is ignored for get and remove. Return only the results of get, in encounter order. Start with an empty map for each call. Distinct keys must remain separate even when their hash values collide. Resizing is not required; the full operation count is known in advance.
The judge checks observable map behavior. The editorial implements the storage explicitly to demonstrate the requested data structure.
Function
runHashMap(operations: String[], keys: int[], values: int[]) → int[]Examples
Example 1
operations = ["put","put","get","put","get","remove","get"]keys = [4,9,4,4,4,4,4]values = [20,30,0,25,0,0,0]return = [20,25,-1]Key 4 first stores 20, is updated to 25, and is then removed. Key 9 remains independent.
Example 2
operations = ["remove","get","put","get"]keys = [0,0,0,0]values = [0,0,0,0]return = [-1,0]Removing an absent key does nothing. A stored value of 0 is different from the missing-key result -1.
Constraints
- All three arrays have equal length
q, where0 <= q <= 300. operations[i]isput,get, orremove.0 <= keys[i], values[i] <= 1000000000.