CT028
Prefix Sum Vault
MediumAcceptance: 0.0%
The Codetikki treasury maintains a map of keys with integer values. They need to quickly compute the sum of all values for keys that begin with a given prefix. Implement a PrefixMapSum class with: insert(key, value) - set key to value (overwrite if exists), and sum(prefix) - return the sum of all values of keys beginning with prefix.
Example 1:
Input: 4
insert columnar 3
insert column 2
sum col
sum colu
Output: 5
3
Example 2:
Input: 3
insert bag 4
insert bath 5
sum ba
Output: 9
Constraints:
1 <= number of operations <= 10^4 1 <= key length <= 100 -10^9 <= value <= 10^9
Tags:
trie hash-table design
Loading...
Test Cases:No test cases
No test cases available.