469. Design HashMap
Build a key → value store from scratch, without touching your language's built-in dictionary / map types.
Implement a class MyHashMap with three operations:
put(key, value)— store the mappingkey → value. Ifkeyalready has a value, overwrite it.get(key)— return the value stored forkey, or-1if the key is absent.remove(key)— delete the mapping forkeyif it exists; otherwise do nothing.
Keys and values are integers in [0, 10^6], so -1 can never be a real stored value — it unambiguously means "not found". Only get produces output. Careful: a value of 0 is a perfectly valid stored value and must not be confused with a missing key.
Example 1:
Input: MyHashMap(); put(1, 1), put(2, 2), get(1), get(3), put(2, 1), get(2), remove(2), get(2)
Output: [1, -1, 1, -1]
Explanation: get(1) finds the stored 1. Key 3 was never put, so get(3) is -1. put(2, 1) overwrites the old value 2, so get(2) returns 1 — until remove(2) deletes the mapping and get(2) becomes -1.
Example 2:
Input: MyHashMap(); get(10), put(10, 0), get(10)
Output: [-1, 0]
Explanation: Before any put, get(10) reports -1 (missing). After put(10, 0), get(10) must return the real stored value 0 — zero is a value, not "absent".
Constraints:
- 0 ≤ key, value ≤ 10⁶
- At most 10⁴ calls total to put, get, and remove
- Do not use built-in hash map / dictionary types
Hints:
Start dumb: a list of (key, value) pairs and a scan per call. Where does it hurt when the map grows?
Keys are bounded by 10^6 and values are never negative — so one big array filled with -1, indexed by the key itself, makes every operation a single array access.
To spend memory on what you actually store: pick B buckets, send key k to bucket k % B, and keep that bucket's (key, value) pairs in a short chain. put must overwrite in place when the key is already chained.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: put(1, 1), put(2, 2), get(1), get(3), put(2, 1), get(2), remove(2), get(2)
Expected output: [1, -1, 1, -1]