HashMap
medium · hashing, chaining
Brief-reported interview attribution (unverified): LeetCode 706 is the design-round version of this question
How to approach an LLD roundRequirements
- Functional: put/get/remove with O(1) average time, keys collide by bucket (chaining), missing keys return -1, negative keys work.
- Non-functional: the bucket function is the only hashing logic; the map must not expose its buckets.
- Out of scope: resizing/rehashing, concurrency, ordering.
Statement
Implement a hash map for integer keys. get returns -1 for a
missing key. Collisions are resolved by chaining. The bucket count is fixed at
769 (a prime).
class MyHashMap:
def __init__(self, size=769):
def put(self, key, value):
# insert, or update the value if the key already exists
def get(self, key):
# -> value, or -1 if the key is absent
def remove(self, key):
# delete the key if present; a no-op if absentRules. Bucket index is key % size (Python's % keeps negative keys in
range). Two keys that land in the same bucket must coexist, and removing one must
not affect the other.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
Entry (one key-value pair; SRP). MyHashMap (buckets of entries; chaining). No pattern is forced; the split (entry vs map) is the point.
Public demo
# Public demo: run after implementing the class API above.
h = MyHashMap()
h.put(1, 10)
print(h.get(1))
print(h.get(2))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
A hash map is shared state in a server: a concurrent put and get can see a half-written bucket. Guard each bucket with its own lock (striped locking) or one lock for the whole map. The reference is single-threaded; the lock is described here.
Trade-offs & extensions
Fixed 769 buckets with no resizing — it degrades if the key count grows far past the bucket count. Extending: grow the bucket count and rehash when the load factor passes a threshold.
Starter code
class Entry:
def __init__(self, key, value):
"""Initialize the state described in the problem."""
pass
class MyHashMap:
def __init__(self, size=769):
"""Initialize the state described in the problem."""
pass
def put(self, key, value):
"""insert, or update the value if the key already exists"""
pass
def get(self, key):
"""-> value, or -1 if the key is absent"""
pass
def remove(self, key):
"""delete the key if present; a no-op if absent"""
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter