706. Design HashMap
Asked at Goldman Sachs
Difficulty
Easy
Time
O(1) average per operation, O(n
Space
O(size + n)
Pattern
Array
Companies
1
Problem
Build a simple hash map class that stores integer keys and integer values. You may not use any built-in hash table or dictionary — you must implement the storage yourself.
Your class needs three methods. put(key, value) stores the pair. If the key is already in the map, replace its old value with the new one (do not add a second copy). get(key) returns the value stored for that key, or -1 if the key is not in the map. remove(key) deletes the key and its value; if the key is not there, do nothing.
The real point of this problem is showing that you know what happens inside a hash map: a fixed array of buckets, a hash function that turns a key into a bucket index, and a way to handle collisions (two keys landing in the same bucket). A common choice is bucket = key % size with a prime size, and each bucket holds a small list of (key, value) pairs.
What the map must do
Constraints
- ●
0 <= key, value <= 10^6 - ●
At most 10^4 calls will be made to put, get, and remove
Examples
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]][null, null, null, 1, -1, null, 1, null, -1]["MyHashMap", "put", "get", "remove", "get"]
[[], [5, 10], [5], [5], [5]][null, null, 10, null, -1]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Easy | View all Goldman Sachs questions → |
How to Think About It
Direct addressing (an array of size 10^6 + 1) technically works for the given key range but misses the point of the exercise.
Key insight: use a fixed array of buckets, compute bucket = key % size, and store (key, value) pairs in each bucket so collisions are handled by chaining.
put: scan the bucket; update the value if the key exists, otherwise append a new pair. get: scan and return the value or -1. remove: scan and delete the pair if found.
Choose a prime bucket count (for example 1009 or 2069) to spread keys that share common factors.
Follow-up talking points: load factor, resizing when buckets get long, and open addressing as an alternative to chaining.
Optimal Approach
State: buckets, an array of size lists.
put(key, value): find the bucket key % size; if a pair with key exists, overwrite its value; otherwise append (key, value).get(key): scan the bucket; return the value if found, else -1.remove(key): scan the bucket; delete the pair with key if present.
Time: O(n / size) average per operation, O(1) with a reasonable load factor. Space: O(size + n).
Bucket array with chaining
What Trips People Up in Real Interviews
Using the language's built-in dictionary inside your class. That defeats the purpose of the question.
Appending a duplicate pair on put instead of updating the existing key.
Returning 0 or null from get for a missing key instead of -1.
Not discussing collisions or load factor. That discussion is usually worth more than the code itself.
Solution Code
O(1) average per operation, O(n timeclass MyHashMap:
def __init__(self):
self.size = 2069
self.buckets = [[] for _ in range(self.size)]
def put(self, key, value):
bucket = self.buckets[key % self.size]
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
def get(self, key):
for k, v in self.buckets[key % self.size]:
if k == key:
return v
return -1
def remove(self, key):
bucket = self.buckets[key % self.size]
for i, pair in enumerate(bucket):
if pair[0] == key:
bucket.pop(i)
returnFrequently Asked Questions
What is the Design HashMap problem?
Design HashMap asks you to build `put`, `get`, and `remove` for integer keys without using a built-in hash table. The interviewer is checking that you understand how hash maps work inside: a bucket array, a hash function, and collision handling.
How do you solve Design HashMap?
The optimal approach runs in O(1) average per operation, O(n time and O(size + n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Design HashMap?
Design HashMap is asked at Goldman Sachs. It is a easy difficulty problem.
What are common mistakes on Design HashMap?
- Using the language's built-in dictionary inside your class. That defeats the purpose of the question.
- Appending a duplicate pair on `put` instead of updating the existing key.
- Returning `0` or `null` from `get` for a missing key instead of `-1`.
- Not discussing collisions or load factor. That discussion is usually worth more than the code itself.