Implementation: HashMap

Easy

0/40

Average time to solve is 30m

Contributed by

204 upvotes

+27 more companies

Problem statement

Design a data structure that stores a mapping of a key to a given value and supports the following operations in constant time.

1. INSERT(key, value): Inserts an integer value to the data structure against a string type key if not already present. If already present, it updates the value of the key with the new one. This function will not return anything.

2. DELETE(key): Removes the key from the data structure if present. It doesn't return anything.

3. SEARCH(key): It searches for the key in the data structure. In case it is present, return true. Otherwise, return false.

4. GET(key): It returns the integer value stored against the given key. If the key is not present, return -1. 

5. GET_SIZE(): It returns an integer value denoting the size of the data structure. 

6. IS_EMPTY(): It returns a boolean value, denoting whether the data structure is empty or not.

Note :

1. Key is always a string value.
2. Value can never be -1.

Operations Performed :

First(Denoted by integer value 1):  Insertion to the Data Structure. It is done in a pair of (key, value).

Second(Denoted by integer value 2):  Deletion of a key from the Data Structure.

Third(Denoted by integer value 3): Search a given key in the Data Structure.

Fourth(Denoted by integer value 4): Retrieve the value for a given key from the Data Structure.

Fifth(Denoted by integer value 5): Retrieve the size of the Data Structure.

Sixth(Denoted by integer value 6): Retrieve whether the Data Structure is empty or not.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line contains an integer 'N' which denotes the number of operations to be performed. Then the operations follow.

Every 'N' lines represent an operation that needs to be performed.

For the 'INSERT' operation, the input line will have three input values separated by a single space, representing the type of the operation in integer, the key inserted as a string, and the value against the key as an integer respectively.

For the rest of the operations except fifth and sixth, the input line will have two values separated by a single space, representing the type of the operation in integer and the key to be inserted as a string respectively. 

For the last two operations(fifth and sixth), the input will contain a single integer, denoting only the type of operation in the integer.

Output Format :

For type 1 operation, you do not need to return anything.

For type 2 operation, remove the element from the data structure and don't return anything.

For type 3 operation, return true if the key is present in the data structure. Else, return false.

For type 4 operation, return the value stored against the key. If the key is not present, return -1.

For type 5 operation, return the size.

For type 6 operation, return the boolean denoting whether the data structure is empty or not.

Constraints :

1 <= N <= 10 ^ 5
1 <= T <= 3
1 <= V <= 10 ^ 5

Where 'T' is the type of operation and 'V' is the value of the operand.

Time Limit: 3 sec

Sample Input 1 :

3
1 qwerty 35
1 qwerty 50
5

Sample Output 1 :

Explanation Of Sample Input 1 :

1 operation: We need to insert 'qwerty' with a value of 35.

2 operation: We need to insert 'qwerty' with a value of 50.

3 operation: We need to return the size of HashMap. So, We will return 1.

Sample Input 2 :

6
1 code 9
3 code
2 code
3 code
5
6

Sample Output 2 :

true
false
0
true

Console