Last Updated: 10 Apr, 2021
Implement Map Sum Pair
Moderate
Asked in companies
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
Approaches
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:
- Declare a global variable ‘map’ in which we store all key-value pairs.
- MapSum():
- Make an object of ‘map’.
- insert(‘KEY’, ‘VAL’):
- Insert this key-value pair in ‘map'.
- 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’.
- If the current key starts with given ‘PREFIX’:
- Finally, return ‘ans’.
For insert(‘KEY’, ‘VALUE’) function:
We declare two HashMap ‘allValues’ and ‘allPrefixes’ in which we store all key-value pairs and all prefixes of every key-value pair.
If the current ‘KEY’ is already present in the map ‘allValues’ then we replace the ‘VAl’ at every prefix which is present in the ‘allPrefixes’ map.
For sum(‘PREFIX’) function:
We can simply return the ‘VAL’ that is present at the ‘KEY’ which is equal to ‘PREFIX’.
The steps are as follows:
- Declare two HashMap ‘allValues’ and ‘allPrefixes’ as we discussed above.
- MapSum():
- Make an object of ‘allValues’ and ‘allPrefixes’ .
- insert(‘KEY’, ‘VAL’):
- Declare a variable ‘diff’ in which we store what amount of value we should add or subtract to ‘allPrefixes’.
- If ‘allValues’ contains key ‘KEY’:
- ‘diff’ = value at key ‘KEY’ in ‘allValues’.
- Else:
- ‘diff’ = 0.
- Add this key value pair in ‘allValues’.
- Declare a string ‘prefix’ in which we store all the prefixes.
- Run a loop for ‘i’ = 0 to length of the ‘KEY’:
- Add current char into ‘prefix’.
- Add ‘diff’ + value in ‘allPrefixes’ at a key ‘KEY’.
- sum(‘PREFIX’):
- If ‘allPrefixes’ contains key ‘PREFIX’:
- Return value at this key.
- Else:
- Return 0.
- If ‘allPrefixes’ contains key ‘PREFIX’:
This approach is similar to the above approach but now we are storing all the prefixes in a ‘TRIE’ data structure.
The steps are as follows:
- Declare HashMap ‘allValues’ and a ‘TRIE ‘root’ as we discussed above.
- TrieNode class/struct:
- Declare a hashMap 'children’ and a variable ‘val’.
- MapSum():
- Make an object of ‘allValues’ and ‘root’.
- insert(‘KEY’, ‘VAL’):
- Declare a variable ‘diff’ in which we store what amount of value we should add or subtract to ‘allPrefixes’.
- If ‘allValues’ contains key ‘KEY’:
- ‘diff’ = ‘val’ - value at key ‘KEY’ in ‘allValues’.
- Else:
- ‘diff’ = ‘val’.
- Add this key-value pair in ‘allValues’.
- Declare a ‘curr’ TrieNode in which we store current nodes of the ‘TRIE’.
- ‘curr.value’ = ‘curr.value’ + ‘diff’.
- Run a loop for ‘i’ = 0 to length of the ‘KEY’:
- If the children node is not present for the current character:
- Add a new node in ‘curr’.
- ‘curr.val’ = ‘curr.val’ + ‘diff’.
- If the children node is not present for the current character:
- sum(‘PREFIX’):
- Declare a ‘curr’ TrieNode in which we store the ‘root’ node of the ‘TRIE’.
- Run a loop for ‘i’ = 0 to the length of the ‘PREFIX’:
- ‘curr’ is equal to ‘curr’.children.
- If ‘curr’ is ‘NULL’:
- Return 0.
- Finally , return ‘curr’.val.