Implement Map Sum Pair
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

Question

Implement Map Sum Pair

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

Accepted Answer

The question asks to implement a data structure called 'MapSum' with functions to initialize, insert key-value pairs, and find the sum of values with a given prefix.

Implement a class called 'MapSum' with a constructor to initialize the data structure.
Implement the 'insert' function to insert key-value pairs into the 'MapSum'. If a key is already present, replace its value with the new one.
Implement the 'sum' function to find the sum of values whose key has a prefix equal to the given prefix.
Use a hashmap to store the key-value pairs, where the key is the string and the value is an integer.
For the 'sum' function, iterate through all the keys in the hashmap and check if the key starts with the given prefix. If yes, add the corresponding value to the sum.
Return the sum as the output of the 'sum' function.

Accepted Answer

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:

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’.
- Finally, return ‘ans’.

Space Complexity: OtherExplanation:

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).

Time Complexity: OtherExplanation:

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).

Python (3.5)

"""

	For the insert function:

	Time complexity: O(1)



	For the sum function:

	Time complexity: O(N * L)

	

	Space complexity: O(N) 



	Where N and L represents the size of map and the Length of the word.

"""





class MapSum:



    # 	Initilizing the HashMap map.

    def __init__(self):

        self.map = {}



    # 	Inserting the key-value pair in HashMap.

    def insert(self, key, val):

        self.map[key] = val



    # 	Adding all values whose prefix of the key is equal to given word prefix.

    def sum(self, prefix):

        ans = 0

        for key in self.map.keys():

            leng = len(prefix)

            if len(key) >= leng and key[:leng] == prefix:

                ans += self.map[key]

        return ans

Java (SE 1.8)

/*

	For the insert function:

	Time complexity: O(L)



	For the sum function:

	Time complexity: O(N * L)

	

	Space complexity: O(N * L) 



	Where N and L represents the size of map and the Length of the word.

*/



import java.util.HashMap;



public class MapSum {



    HashMap < String, Integer > map;





    //	Initilizing the HashMap map.

    public MapSum() {

        map = new HashMap < > ();

    }





    //	Inserting the key-value pair in HashMap.

    public void insert(String key, int val) {

        map.put(key, val);

    }





    //	Adding all values whose prefix of the key is equal to given word prefix.

    public int sum(String prefix) {

        int ans = 0;

        for (String key: map.keySet()) {

            if (key.startsWith(prefix)) {

                ans += map.get(key);

            }

        }

        return ans;

    }

}

C++ (g++ 5.4)

/*

	For the insert function:

	Time complexity: O(1)



	For the sum function:

	Time complexity: O(N * L)

	

	Space complexity: O(N) 



	Where N and L represents the size of map and the Length of the word.

*/



#include 



class MapSum

{

public:

    unordered_map map;



    //	Initilizing the HashMap map.

    MapSum() {}



    //	Inserting the key-value pair in HashMap.

    void insert(string &key, int val)

    {

        map.insert({key, val});

    }



    //	Adding all values whose prefix of the key is equal to given word prefix.

    int sum(string &prefix)

    {

        int ans = 0;

        for (auto key : map)

        {

            int leng = prefix.length();

            if (key.first.length() >= leng && key.first.substr(0, leng).compare(prefix) == 0)

            {

                ans += key.second;

            }

        }

        return ans;

    }

};

Accepted Answer

Prefix HashMap

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.

Space Complexity: OtherExplanation:

O(N * L) where ‘N’ is the size of ‘allPrefixes’ HashMap.

Because we are using two HashMaps ‘allValues’ and ‘allPrefixes’. In ‘allValues’ we are storing all the key-value pairs and then we are iterating through each key and storing all prefixes of each key into ‘allPrefixes’ HashMap. Hence the space complexity is O(N * L).

Time Complexity: OtherExplanation:

O(N * L).

For the insert function:

O(L), where ‘L’ is the length of the largest given word that we have to insert.

Because we are inserting all the prefixes of the given word in ‘allPrefixes’ HashMap.

For the sum function:

O(L), where ‘L’ is the length of the largest given word that we have to insert.

Because we have to check if the prefix is present in our ‘map’ or not. Hence the time complexity is O(L).

And we call these functions ‘N’ times. So overall time complexity for all operations is O(N * L).

C++ (g++ 5.4)

/*

	Time complexity: O(N * L)

	Space complexity: O(N * L) 



	Where N and L represents the size of map and the Length of the word.

*/



#include 



class MapSum

{



public:

    unordered_map allValues, allPrefixes;



    MapSum() {}



    //	Iserting all prefixes of the key in allPrefixes HashMap.

    void insert(string &key, int val)

    {



        int diff = val - allValues[key];

        allValues[key] = val;

        string prefix = "";



        for (int i = 0; i < key.length(); i++)

        {

            prefix += key[i];

            val = allPrefixes[prefix] + diff;

            allPrefixes[prefix] = val;

        }

    }



    // If the given word prefix is present in the HashMap allPrefixes then return the value at this key.

    int sum(string &prefix)

    {

        return allPrefixes[prefix];

    }

};

Python (3.5)

"""

	Time complexity: O(N * L)

	Space complexity: O(N * L) 



	Where N and L represents the size of map and the Length of the word.

"""





class MapSum:

    def __init__(self):

        self.allValues = {}

        self.allPrefixes = {}



    # 	Iserting all prefixes of the key in allPrefixes HashMap.

    def insert(self, key, val):

        diff = val

        if key in self.allValues:

            diff -= self.allValues[key]

        self.allValues[key] = val

        prefix = ""



        for i in range(len(key)):

            prefix += key[i]

            val = diff

            if prefix in self.allPrefixes:

                val += self.allPrefixes[prefix]

            self.allPrefixes[prefix] = val



    # If the given word prefix is present in the HashMap allPrefixes then return the value at this key.

    def sum(self, prefix):

        if prefix in self.allPrefixes:

            return self.allPrefixes[prefix]

        else:

            return 0

Java (SE 1.8)

/*

	Time complexity: O(N * L)

	Space complexity: O(N * L) 



	Where N and L represents the size of map and the Length of the word.

*/



import java.util.HashMap;



public class MapSum {



    HashMap < String, Integer > allValues;

    HashMap < String, Integer > allPrefixes;





    //	Initilizing the value of HashMaps.

    public MapSum() {

        allValues = new HashMap < > ();

        allPrefixes = new HashMap < > ();

    }





    //	Iserting all prefixes of the key in allPrefixes HashMap.

    public void insert(String key, int val) {

        int diff = val - allValues.getOrDefault(key, 0);

        allValues.put(key, val);

        String prefix = "";

        for (int i = 0; i < key.length(); i++) {

            prefix += key.charAt(i);

            allPrefixes.put(prefix, allPrefixes.getOrDefault(prefix, 0) + diff);

        }

    }





    // If the given word prefix is present in the HashMap allPrefixes then return the value at this key.

    public int sum(String prefix) {

        return allPrefixes.getOrDefault(prefix, 0);

    }

}

Accepted Answer

Trie

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

Space Complexity: OtherExplanation:

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

Because we are using a HashMap ‘allValues’ in which we are storing all the key-value pairs. And we are using a ‘TRIE’ ‘root’ in which we are storing all the prefixes of all key-value pairs.

Time Complexity: OtherExplanation:

O(N * L).

For the insert function:

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

Because we are inserting all the prefixes of the given word in ‘root’ ‘TRIE’.

For the sum function:

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

And we call these functions ‘N’ times. So overall time complexity for all operations is O(N * L).

Python (3.5)

"""

	Time complexity: O(N * L)

	Space complexity: O(N * L) 



	Where N and L represents the size of map and the Length of the word.

"""





class TrieNode:

    def __init__(self):

        self.children = {}

        self.val = 0





class MapSum:



    # 	Initialize the value of HashMap and Trie.

    def __init__(self):

        self.root = TrieNode()

        self.allValues = {}



    # 	Inserting all values into Trie.

    def insert(self, key, val):

        diff = val

        if key in self.allValues:

            diff -= self.allValues[key]

        self.allValues[key] = val

        cur = self.root

        cur.val += diff

        for i in range(len(key)):

            x = key[i]

            if x not in cur.children:

                cur.children[x] = TrieNode()

            cur = cur.children[x]

            cur.val += diff



    # 	Searching in trie that the word prefix is present or not.

    def sum(self, prefix):

        cur = self.root

        for i in range(len(prefix)):

            if prefix[i] not in cur.children:

                return 0

            cur = cur.children[prefix[i]]

        return cur.val

C++ (g++ 5.4)

/*

	Time complexity: O(N * L)

	Space complexity: O(N * L) 



	Where N and L represents the size of map and the Length of the word.

*/



#include 



class TrieNode

{

public:

    unordered_map children;

    int val;

};



class MapSum

{

public:

    TrieNode *root;

    unordered_map allValues;



    //	Initialize the value of HashMap and Trie.

    MapSum()

    {

        root = new TrieNode();

    }



    //	Inserting all values into Trie.

    void insert(string &key, int val)

    {

        int diff = val - allValues[key];

        allValues.insert({key, val});

        TrieNode *cur = root;

        cur->val += diff;

        for (int i = 0; i < key.length(); i++)

        {

            char x = key[i];

            if (cur->children[x] == NULL)

            {

                cur->children[x] = new TrieNode();

            }

            cur = cur->children[x];

            cur->val += diff;

        }

    }



    //	Searching in trie that the word prefix is present or not.

    int sum(string &prefix)

    {

        TrieNode *cur = root;

        for (int i = 0; i < prefix.length(); i++)

        {

            cur = cur->children[prefix[i]];

            if (cur == NULL)

            {

                return 0;

            }

        }

        return cur->val;

    }

};

Java (SE 1.8)

/*

	Time complexity: O(N * L)

	Space complexity: O(N * L) 



	Where N and L represents the size of map and the Length of the word.

*/



import java.util.HashMap;



class TrieNode {

    HashMap < Character, TrieNode > children = new HashMap < > ();

    int val;

}





public class MapSum {

    HashMap < String, Integer > allValues;

    TrieNode root;





    //	Initialize the value of HashMap and Trie.

    public MapSum() {

        allValues = new HashMap < > ();

        root = new TrieNode();

    }





    //	Inserting all values into Trie.

    public void insert(String key, int val) {

        int diff = val - allValues.getOrDefault(key, 0);

        allValues.put(key, val);

        TrieNode cur = root;

        cur.val += diff;

        for (int i = 0; i < key.length(); i++) {

            char x = key.charAt(i);

            cur.children.putIfAbsent(x, new TrieNode());

            cur = cur.children.get(x);

            cur.val += diff;

        }

    }





    //	Searching in trie that the word prefix is present or not. 

    public int sum(String prefix) {

        TrieNode cur = root;

        for (int i = 0; i < prefix.length(); i++) {

            cur = cur.children.get(prefix.charAt(i));

            if (cur == null)

                return 0;

        }

        return cur.val;

    }

}

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

Note :

Input Format :

Output Format :

Note :

Constraints :

Top GlobalLogic Senior Software Engineer interview questions & answers

Popular interview questions of Senior Software Engineer

Top HR questions asked in GlobalLogic Senior Software Engineer