Implement Hash Map with O(1) space

Question

Implement a hash map that supports the `put` and `get` operations with O(1) time complexity for both operations. The hash map should handle collisions using chaining or open addressing and must be designed to use O(1) space complexity. Your implementation should allow for storing key-value pairs, where keys are unique strings and values are integers, and should return the value associated with a key when using the `get` operation.

Codemia · Accepted Answer

To implement a hash map that supports `put` and `get` operations with O(1) time complexity, we can utilize a fixed-size array (bucket) to store key-value pairs. Given that the keys are unique strings and values are integers, we can create a simple hash function that maps the string keys to indices in the array. Collisions can be handled by using chaining, where each bucket at an index holds a list of key-value pairs that hash to the same index. The O(1) space complexity constraint implies that we must use a constant amount of additional space regardless of the number of key-value pairs. This means we should not dynamically allocate space based on the number of pairs.

1. **Define the HashMap**: Create a class `HashMap` with an array of fixed size (let's say 1000) to store the lists of key-value pairs. 
2. **Hash Function**: Implement a simple hash function that takes a string key and returns an index based on the length of the key and its characters. For example, `hash(key) = sum(ord(c) for c in key) % size`. 
3. **Put Operation**: In the `put(key, value)` method, compute the index using the hash function. If a list already exists at that index, check if the key exists; if it does, update the value, otherwise append a new key-value pair. 
4. **Get Operation**: In the `get(key)` method, compute the index and search through the list at that index for the key. If found, return the associated value; if not, return None or a suitable default. 
5. **Example**: For keys "apple" and "banana", if both hash to the same index, their pairs will be stored in a list at that index.

```python
class HashMap:
    def __init__(self):
        self.size = 1000  # Fixed size for the hash map
        self.buckets = [[] for _ in range(self.size)]  # List of lists for chaining

def _hash(self, key):
        return sum(ord(c) for c in key) % self.size

def put(self, key: str, value: int):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                self.buckets[index][i] = (key, value)  # Update existing key
                return
        self.buckets[index].append((key, value))  # Add new key-value pair

def get(self, key: str) -> int:
        index = self._hash(key)
        for k, v in self.buckets[index]:
            if k == key:
                return v  # Return value if key is found
        return None  # Return None if key is not found
```

The time complexity for both `put` and `get` operations is O(1) on average. This is due to the direct access provided by the hash function. However, in the worst case (all keys collide and end up in the same bucket), the complexity can degrade to O(n), where n is the number of key-value pairs. The space complexity is O(1) since we are using a fixed-size array for our buckets, independent of the number of elements stored.

1. **Empty Input**: If `get` is called with a non-existing key, it should return None. 
2. **Overwrite Values**: If `put` is called with an existing key, it should update the corresponding value. 
3. **Single Element**: Ensure that operations work correctly with only one key-value pair. 
4. **Collision Handling**: Test that when multiple keys hash to the same index, they are properly stored and retrieved without data loss.

Implement Hash Map with O(1) space

Adobe

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Adobe Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string