Design HashSet

Design HashSet is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Previously Seen / Existence Check subpattern.

Problem statement

Implement a class named MyHashSet that stores a collection of integer keys. A key can appear at most once, and the set initially contains no keys. Built-in hash set or hash table libraries must not be used.

The constructor MyHashSet() creates an empty set. add(key) inserts key; adding a key that is already present leaves the set unchanged. remove(key) deletes key if it is present; removing an absent key has no effect.

contains(key) checks membership and returns true when key is currently stored, or false otherwise. The constructor and the add and remove methods return nothing; the test harness represents such results as null.

Example 1:

Input:

["MyHashSet", "add", "contains", "remove", "contains"] [[],[23],[23],[23],[23]]

Output:

[null,null,true,null,false]

Explanation: The key 23 is inserted and found, then removed, so the final membership check is false.

Example 2:

Input:

["MyHashSet", "contains", "add", "add", "contains", "remove", "remove", "contains"] [[],[8],[8],[8],[8],[8],[8],[8]]

Output:

[null,false,null,null,true,null,null,false]

Explanation: The first lookup occurs before insertion. Repeated insertion and removal do not create duplicates or cause an error.

Example 3:

Input:

["MyHashSet", "add", "add", "contains", "remove", "contains", "add", "contains"] [[],[0],[1000000],[1000000],[0],[0],[0],[0]]

Output:

[null,null,null,true,null,false,null,true]

Explanation: The set can hold keys at both ends of the permitted range; removing 0 does not affect 1000000, and reinserting 0 makes it present again.

Constraints:

- 1 <= operations.length <= 10^4 - operations[0] is "MyHashSet" and has no arguments - Every later operation is "add", "remove", or "contains" - Each method receives exactly one integer argument named key - 0 <= key <= 10^6 - The arguments array has one entry for each operation, in the same order

Topics and companies

Topics: Array, Design, Hash Function.

How to practise Design HashSet on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) per add, remove, or contains operation time and O(10^6) space.

Open Design HashSet in the code editor, or read the Design HashSet editorial for a worked solution with its approach and complexity analysis.

Where Design HashSet sits in the DSA pattern sheet

Problems related to Design HashSet

Other problems that use the same Hashing - Previously Seen / Existence Check and Array/Matrix Manipulation Patterns techniques:

Preparing this workspace.