algoadvance

Problem Statement

You need to implement the MapSum class:

• MapSum() Initializes the MapSum object.
• void insert(String key, int val) Inserts the key-val pair into the map. If the key already existed, the original key-value pair will be overridden to the new one.
• int sum(String prefix) Returns the sum of all the pairs’ value whose key starts with the given prefix.

Clarifying Questions

1. Can the keys contain any characters, or are they just lowercase English letters?
2. Are the key and prefix guaranteed to be non-empty?

Let’s assume for simplicity that keys are non-empty strings consisting of lowercase English letters and that they can be of any length.

Strategy

We’ll use a combination of a hashmap and a Trie (prefix tree) to efficiently manage the insert and prefix sum operations.

1. Insert Operation: This will involve storing the key-value pairs in a dictionary. We’ll also update/add the key in a Trie structure to keep track of all keys that start with given prefixes.

2. Sum Operation:

   • Navigate the Trie to find the node corresponding to the prefix.
   • Accumulate the sums of all nodes in the subtree of this prefix node.

Code Implementation

Here’s how we can implement this:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.value = 0

class MapSum:

    def __init__(self):
        self.map = {}
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        if key in self.map:
            delta = val - self.map[key]
        else:
            delta = val
        self.map[key] = val

        node = self.root
        node.value += delta
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.value += delta

    def sum(self, prefix: str) -> int:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.value

Time Complexity

• Insert Operation: O(m), where m is the length of the key. We need to update nodes in the Trie up to the length of the key.
• Sum Operation: O(p), where p is the length of the prefix. We traverse the Trie up to the length of the prefix.

This approach ensures efficient insert and sum operations by leveraging both a hashmap for direct key access and a Trie for prefix-based sum calculations.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?