Map Sum Pairs
Medium · Tries · Hash Table · String · Design · Trie
Problem
Design a map with string keys that can quickly total the values of all keys sharing a prefix.
Implement MapSum:
- MapSum() creates an empty map.
- insert(key, val) sets the value of key to val. If key is already present, its old value is replaced, not added to.
- sum(prefix) returns the total of the values of every key that starts with prefix.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments, and calls that return nothing report None.
Examples
Input: ops = ["MapSum","insert","insert","sum","insert","sum"], args = [[],["pen",4],["pencil",6],["pen"],["pen",1],["pen"]] Output: [None, None, None, 10, None, 7]
Both keys start with pen. Replacing pen's value with 1 changes the total to 1 + 6.
Input: ops = ["MapSum","insert","sum","sum"], args = [[],["star",9],["st"],["sp"]] Output: [None, None, 9, 0]
No key starts with sp, so its total is 0.
Constraints
- 1 <= len(key), len(prefix) <= 50
- key and prefix consist of lowercase English letters
- 1 <= val <= 1000
- At most 50 calls to insert and sum
Approaches
- Baseline: dictionary, scan every key on sum — time insert O(L), sum O(n · L) for n keys, space O(total key length)
Follow-up
What if keys were grouped by their ending, or you counted words with removals instead of summing values? See the use cases “Total by suffix” and “Count words by prefix, with removals”.
Related problems
Start free on Cariara · Coding problems · System design studio
