Map Sum Pairs

Medium · Trie · about 15 minutes

Asked at Google, Amazon, Meta.

Design a map from string keys to integer values that can sum the values of all keys with a given prefix.

• MapSum() creates an empty map.
• insert(key, val) sets key to val, replacing any previous value.
• sum(prefix) returns the sum of the values of every key that starts with prefix.

Related guides

• Trie