Design HashMap
Implement a hash map for non-negative integer keys without using any built-in map type. Support put(key, value), get(key) returning -1 if absent, and remove(key).
- 0 ≤ key, value ≤ 10^6
- At most 10^4 operations
- Average O(1) insert, lookup and delete required
- Keys are integers and collisions must be handled explicitly
- Asks you to build the structure, not use it
Whenever a brute force re-scans earlier elements to check membership, count, or a complement, a hash table answers the same question in expected O(1) and turns O(n^2) into O(n). Grouping problems reduce to choosing a canonical key (a sorted string, a character-count tuple) and bucketing by it.
Allocate an array of B buckets (a prime such as 1009 or 10007) and hash a key to key mod B. Each bucket holds a small list of (key, value) pairs; put updates an existing pair or appends, get scans the bucket, remove deletes from it. With a good load factor the bucket lists stay short so operations are O(1) on average; optionally double B and rehash when the load exceeds a threshold.
- Open addressing with linear probing avoids per-bucket lists but needs tombstones for deletion. A direct-address array of size 10^6 + 1 also works here given the small key range, trading memory for simplicity.