Design HashSet

Design HashSet

1. What is this problem about?

The Design HashSet interview question is similar to the HashMap problem but focuses solely on unique keys. You need to implement a set that supports add(key), remove(key), and contains(key). The key challenge is ensuring that adding the same key multiple times has no additional effect, and checking for existence is fast. This Design HashSet coding problem evaluates your ability to implement deduplication logic.

2. Why is this asked in interviews?

Companies like Meta and Amazon ask this to test your knowledge of Hash Table interview patterns. It’s a foundational exercise in managing a collection where membership is the primary concern. It evaluates your ability to use boolean arrays or bitsets for small ranges, and hashing for large ones.

3. Algorithmic pattern used

This is usually implemented with Hashing with Buckets.

• Use an array of linked lists (Separate Chaining).
• add: Hash the key, check the corresponding bucket. If the key isn't already there, add it.
• contains: Hash the key, search the bucket for the key.
• remove: Hash the key, find and delete the key from the bucket if it exists.
• Prime Array Size: Using a prime number for the number of buckets (like 769 or 10007) helps reduce the frequency of collisions.

4. Example explanation

1. add(1): Key 1 hashed to bucket 1. Success.
2. add(2): Key 2 hashed to bucket 2. Success.
3. contains(1): Returns true.
4. add(1): Key 1 hashed to bucket 1. It's already there! No change.
5. remove(2): Key 2 found in bucket 2 and removed.

5. Common mistakes candidates make

• Using a large bitset: While boolean[1000001] works for integer keys, it's not a generalizable solution for other types of keys (like strings) and uses excessive memory.
• Slow Contains: If buckets aren't handled correctly, the contains check becomes $O(N)$ instead of $O(1)$ average.
• Initialization: Failing to initialize the array of buckets properly (e.g., starting with null instead of empty list objects).

6. Interview preparation tip

Practice calculating the Load Factor (Number of elements / Number of buckets). Discussing how you would resize the internal array when it gets too full is a great way to demonstrate advanced understanding of data structure scaling.