Scale Engineer

Map Sum Pairs

Med
#0631Time: - `insert(key, val)`: O(L), where L is the length of the `key`. This is the time taken to compute the hash of the string. - `sum(prefix)`: O(N * P), where N is the number of keys in the map and P is the length of the `prefix`. We iterate through all N keys, and for each, `startsWith` takes O(P) time.Space: O(K), where K is the total number of characters across all keys stored in the map. This is because the map needs to store all the key strings.1 company
Patterns
Design
Data structures
Hash TableStringTrie
Companies
Akuna Capital

Prompt

Design a map that allows you to do the following:

  • Maps a string key to a given value.
  • Returns the sum of the values that have a key with a prefix equal to a given string.

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

 

Example 1:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

 

Constraints:

  • 1 <= key.length, prefix.length <= 50
  • key and prefix consist of only lowercase English letters.
  • 1 <= val <= 1000
  • At most 50 calls will be made to insert and sum.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a standard HashMap to store the key-value pairs. The insert operation is straightforward, mapping directly to the put method of the hash map. To calculate the sum for a given prefix, we iterate through all the keys in the map, check if each key starts with the prefix, and accumulate the values of the matching keys.

Algorithm

  • In the constructor, initialize a HashMap<String, Integer> to store the key-value pairs.
  • For the insert(String key, int val) method:
    • Use the map's put method to insert or update the key-value pair: map.put(key, val).
  • For the sum(String prefix) method:
    • Initialize a variable totalSum to 0.
    • Iterate through every entry (key, value) in the HashMap.
    • For each key, use the startsWith() method to check if it begins with the given prefix.
    • If key.startsWith(prefix) is true, add the corresponding value to totalSum.
    • After checking all keys, return totalSum.

Walkthrough

The simplest way to solve this problem is by using a HashMap to store the mapping from a string key to an integer val.

insert(key, val) operation: This operation is very simple. We just place the (key, val) pair into our hash map. If the key already exists, the put operation will automatically overwrite the old value with the new one, which is the desired behavior.

sum(prefix) operation: For this operation, we need to find all keys that start with the given prefix. Since the hash map doesn't provide a direct way to query by prefix, we have to iterate through its entire set of keys. For each key, we check if it has the given prefix using the String.startsWith() method. If it does, we add the key's associated value to a running sum. Finally, we return this sum.

import java.util.HashMap;import java.util.Map; class MapSum {    private Map<String, Integer> map;     /** Initialize your data structure here. */    public MapSum() {        map = new HashMap<>();    }        public void insert(String key, int val) {        map.put(key, val);    }        public int sum(String prefix) {        int totalSum = 0;        for (Map.Entry<String, Integer> entry : map.entrySet()) {            if (entry.getKey().startsWith(prefix)) {                totalSum += entry.getValue();            }        }        return totalSum;    }}

Complexity

Time

- `insert(key, val)`: O(L), where L is the length of the `key`. This is the time taken to compute the hash of the string. - `sum(prefix)`: O(N * P), where N is the number of keys in the map and P is the length of the `prefix`. We iterate through all N keys, and for each, `startsWith` takes O(P) time.

Space

O(K), where K is the total number of characters across all keys stored in the map. This is because the map needs to store all the key strings.

Trade-offs

Pros

  • Very simple to implement and understand.

  • Low memory overhead if the number of keys is small.

Cons

  • The sum operation is inefficient, especially for a large number of keys, as it requires a full scan of all stored keys.

Solutions

public class Trie { private Trie [] children = new Trie [ 26 ]; private int val ; public void Insert ( string w , int x ) { Trie node = this ; for ( int i = 0 ; i < w . Length ; ++ i ) { int idx = w [ i ] - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; node . val += x ; } } public int Search ( string w ) { Trie node = this ; for ( int i = 0 ; i < w . Length ; ++ i ) { int idx = w [ i ] - 'a' ; if ( node . children [ idx ] == null ) { return 0 ; } node = node . children [ idx ]; } return node . val ; } } public class MapSum { private Dictionary < string , int > d = new Dictionary < string , int >(); private Trie trie = new Trie (); public MapSum () { } public void Insert ( string key , int val ) { int x = val - ( d . ContainsKey ( key ) ? d [ key ] : 0 ); d [ key ] = val ; trie . Insert ( key , x ); } public int Sum ( string prefix ) { return trie . Search ( prefix ); } } /** * Your MapSum object will be instantiated and called as such: * MapSum obj = new MapSum(); * obj.Insert(key,val); * int param_2 = obj.Sum(prefix); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem