Design HashMap
Asked at Goldman Sachs
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.
Asked At
| 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).
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.