HashMap

medium · hashing, chaining

Brief-reported interview attribution (unverified): LeetCode 706 is the design-round version of this question

How to approach an LLD round

Requirements

  • 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 absent

Rules. 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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. RecruiterCharacter joke · No posting date

    We loved your energy. We went with the candidate whose code compiled.

  2. TryGetValueCharacter joke · No posting date

    My solution passed all the tests. All zero of them. I forgot to run them.

  3. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.