Implement Map Sum Pair

Posted: 10 Apr, 2021
Difficulty: Moderate


Try Problem

Ninja has to implement a data structure called ‘MapSum’. Ninja has to implement two functions and one constructor.

1) MapSum(): Ninja has to initialize the ‘MapSum’.
2) insert(‘KEY’, ‘VAL’): Ninja has to insert this key-value pair in this ‘MapSum’.
3) sum(‘PREFIX’): Ninja has to find the sum of all values whose prefix of the keys is equal to ‘PREFIX’

Note :

During insertion, In the ‘MapSum’ if a ‘KEY’ is already present in the ‘MapSum’ then replace it with the new one.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ which denotes how many times the functions(as discussed above) we call.

The next “N” lines contain the string and key-value pair or a string, the first one is the name of the function and the second one is a ‘key-value’ or ‘PREFIX’.
Output Format :
For each test case, complete all the functions as we discussed above.

Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 50
2 <= ‘N’ <= 10000
1 <= |‘KEY’|, |‘PREFIX’| <= 50
1 <= ‘VAL’ <= 1000

Where |‘KEY’| and |’PREFIX’| denotes the length of the string ‘KEY’ and ‘PREFIX’. ‘VAL’ denotes the value of the key-value pair.

Time limit: 1 sec
Approach 1

First, we declare a ‘map’ HashMap in which we store all the key-value pairs. Then for the second function i.e ‘sum’ we simply iterate through the ‘map’ and check whether the ‘KEY’ of the current key-value pairs contains a prefix equal to the given prefix.

The steps are as follows: 

  1. Declare a global variable ‘map’ in which we store all key-value pairs.
  2. MapSum():
    • Make an object of ‘map’.
  3. insert(‘KEY’, ‘VAL’):
    • Insert this key-value pair in ‘map'.
  4. sum(‘PREFIX’):
    • Declare a variable ‘ans’ in which we store our resultant answer.
    • Iterate through ‘map’:
      • If the current key starts with given ‘PREFIX’:
        • Add the value in ‘ans’.
    • Finally, return ‘ans’.
Try Problem