Implement Map Sum Pair

Moderate
0/80
Average time to solve is 30m
0 upvote
Asked in companies
Morgan StanleyAmerican ExpressMicrosoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
3
insert coding 4
insert ninja 5
sum ni
Sample Output 1 :
5
Explanation of sample input 1 :
First, we insert a key-value pair into the ‘MapSum’ having ‘KEY’ as “coding'' and ‘VAL’ as 4.

Then again we are inserting a key-value pair into the ‘MapSum’ having ‘KEY’ as “ninja” and ‘VAL’ as 5.

Only one key has the prefix “ni” is “ninjas” and the ‘VAL’ is 5.
Sample Input 2 :
1
4
insert a 4
insert aa 5
Insert aaa 6
sum a
Sample Output 2 :
15
Explanation of sample input 2 :
First, we insert three key-value pair in ‘MapSum’:
(“a”, 4), (“aa”, 5) and (“aaa”, 6)
Then the sum of all values whose prefix of the keys is equal to ‘a’ is 4 + 5 + 6 = 15.
Hint

Can you think of using a HashMap?


 

Approaches (3)
Brute Force

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’.
       
Time Complexity

For the insert function:

O(L) , where ‘L’ is the length of the largest word.

 

Because we are inserting a string into HashMap ‘map’. Hence the time complexity is O(L).

 

For the sum function:

O(N * L), where ‘N’ is the size of ‘map’ and ‘L’ is the length of the largest word.

 

Because for finding our answer we are iterating the ‘map’ then checking the prefix of the current key is equal to the given prefix. Hence the time complexity is O(N * L). 

Space Complexity

O(N * L) where ‘N’ is the size of ‘map’ and ‘L’ is the length of the largest word.

 

Because we are using a ‘map’ for storing all the key-value pairs and as we are storing every string (avg length 'L') into the hashmap. Hence the overall complexity is O(N * L).

Code Solution
(100% EXP penalty)
Implement Map Sum Pair
Full screen
Console