Design a hashset
Design a HashSet without using any built-in hash table libraries.

Implement the following public functions :

1) Constructor: It initializes the data members as required. 2) add(value): It inserts an element into the HashSet. The function takes one argument which is the value that needs to be added and returns nothing 3) contains(value): It checks whether the element exists in the HashSet or not. The function takes one argument which is the value that needs to be searched for in the HashSet. The function returns true if the element exists, otherwise returns false. 4) remove(value): It removes an element from the HashSet. The function takes one argument which is the value that needs to be removed from the HashSet and returns the element which is being removed. If the element does not exist in the HashSet or if HashSet is empty, return -1.

Operations Performed on the HashSet:

Query-1 (Denoted by an integer 1)- Inserts an element in the HashSet Query-2 (Denoted by an integer 2)- Returns a boolean value denoting whether the element is present in the HashSet or not. Query-3 (Denoted by an integer 3)- Removes the element from the HashSet.

Input format:

The first line of input contains an integer ‘Q’ denoting the number of queries. The next ‘Q’ lines represent the queries that need to be performed. Each query case contains two integers, two integers separated by a single space, representing the type of the operation, and a value on which operation needs to be performed.

Output format

For Query 1, you do not need to return anything. For Query 2, return true or false depending upon whether the element is present or not. For Query 3, return the element which is being removed from the HashSet.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Design a hashset

Design a HashSet without using any built-in hash table libraries.

Implement the following public functions :

1) Constructor: It initializes the data members as required.

2) add(value): It inserts an element into the HashSet. The function takes one argument which is the value that needs to be added and returns nothing

3) contains(value): It checks whether the element exists in the HashSet or not. The function takes one argument which is the value that needs to be searched for in the HashSet. The function returns true if the element exists, otherwise returns false.

4) remove(value): It removes an element from the HashSet. The function takes one argument which is the value that needs to be removed from the HashSet and returns the element which is being removed. If the element does not exist in the HashSet or if HashSet is empty, return -1.

Operations Performed on the HashSet:

Query-1 (Denoted by an integer 1)- Inserts an element in the HashSet

Query-2 (Denoted by an integer 2)- Returns a boolean value denoting whether the element is present in the HashSet or not.

Query-3 (Denoted by an integer 3)- Removes the element from the HashSet.

Input format:

The first line of input contains an integer ‘Q’ denoting the number of queries.
The next ‘Q’ lines represent the queries that need to be performed.

Each query case contains two integers, two integers separated by a single space, representing the type of the operation, and a value on which operation needs to be performed.

Output format

For Query 1, you do not need to return anything.

For Query 2, return true or false depending upon whether the element is present or not.

For Query 3, return the element which is being removed from the HashSet.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= Q <= 10^3
1 <= query type <= 3
0 <= VALUE <= 10^6

Where ‘Q’ is the total number of queries, ‘value’ is the element that will be added, removed, or whose existence in the HashSet is to be checked.

Time limit: 1 second

Accepted Answer

I knew that HashSet uses O(1) time to search an element in the list. Also, the word ' Hash' in HashSet helped me to come up with the solution, to use hash table that can help solve the problem efficiently.

Accepted Answer

Chained Hashing Approach

The idea is to store the elements in the hash table to reduce the space. To avoid a collision, chaining is used.

Make a hash table of size 1000.
For the addition of a value to a hash table, find its index by passing it in a hash function. In the hash function, the modulus of the value and a constant is taken. The result is the index where the element will be stored in the hash table.
To avoid a collision, use chaining. In chaining, each cell of the hash table points to a linked list of records that have the same hash function value. So, to add the element, just push the element in the list at the found index.
To remove an element, first find its index in the hash table, then search the element in the list of records present at that index. If the element is found, erase the element and return the removed element. If the element is not present already, return -1.
To search an element, first find its index in the hash table. Now, search for the element in the list of records present at the index. If the element is found, return true. Else return false.

Space Complexity: O(n)Explanation:

O(HASHTABLE_SIZE), ‘HASHTABLE_SIZE’ denotes the size of the hash table.

A hashtable is used to store the elements, hence the size required would be of the order of the size of Hashtable.

Time Complexity: O(n^2)Explanation:

O(Q^2), ‘Q’ denotes the number of queries.

The time complexity of add operation is O(1).

The time complexity of finding the element is O(Q).

The time complexity of removing the element is O(Q).

The maximum number of elements in a cell in the hashtable will be ‘Q’ because in the worst case, ‘Q’ add operations will be performed.

Accepted Answer

List Based Approach

The idea is to use a vector to act as a HashSet. All three operations are performed using the vector.

Create a vector/list.
To add an element, push the element to the vector.
To check whether the element is present or not, perform a linear search on the vector.
1. If the element is found, return true
2. Else if an element is not found, return false.
To remove an element, use the erase operation(removes the element and resizes the vector) on the vector and return the removed element. If the element is not present already, return -1.

Space Complexity: O(n)Explanation:

O(Q), where ‘Q’ is the number of queries.

In the worst case, the maximum number of elements in the vector will be equal to the number of queries.

Time Complexity: O(n^2)Explanation:

O(Q^2), ‘Q’ denotes the number of queries that are performed on the HashSet.

The time complexity of add operation is O(1).

The time complexity of finding the element is O(Q).

The time complexity of removing the element is O(Q).

The maximum size of HashSet will be ‘Q’ because in the worst case ‘Q’ add operations will be performed.

Accepted Answer

Mark the elements

The idea is to use a boolean vector of size 10^6 to mark the elements in the HashSet.

Initialize a boolean vector of size 10^6(size of the queries) with false. Call it ‘HASH’.
For add operation, take the element as an index in hashset as set it to ‘true’.
To check whether the element is present in the HashSet or not, check ‘HASH[ELEMENT]’. If it is ‘true’, the element is present and returns true. Else, return false.
To remove an element from HashSet, turn ‘HASH[ELEMENT]’ to false and return the removed element. If the element is not present in the HashSet, return -1.

Space Complexity: O(n)Explanation:

O(ELEMENT), where ‘ELEMENT’ is the largest value that can be inserted in the HashSet.

A boolean vector of size 10^6 is used to mark the presence of an element

Time Complexity: O(1)Explanation:

O(1), as it uses constant time.

The time complexity of add operation is O(1).

The time complexity of finding the element is O(1).

The time complexity of removing the element is O(1).

Design a HashSet without using any built-in hash table libraries.

Implement the following public functions :

Operations Performed on the HashSet:

Input format:

Output format

Note:

Constraints:

Top Goldman Sachs Software Analyst interview questions & answers

Popular interview questions of Software Analyst