MediumStringsAI interview only
Map Sum Pairs
Asked atamazongooglemetabloomberg
01 · Problem
Design a key-value store that can also total the values of all keys sharing a prefix.
Implement the MapSum class:
MapSum()creates an empty store.void insert(String key, int val)storesvalunderkey. Ifkeyalready exists, its old value is replaced byval(not added to it).int sum(String prefix)returns the total of the values of every stored key that starts withprefix(a key equal toprefixcounts). If no key matches, return0.
02 · Examples
Example 01
Input
["MapSum","insert","insert","sum","sum"], [[],["sunset",8],["sunny",5],["sun"],["suns"]]
Output
[null,null,null,13,8]
Both "sunset" and "sunny" start with "sun", so sum("sun") is 8 + 5 = 13. Only "sunset" starts with "suns", giving 8.
Example 02
Input
["MapSum","insert","insert","sum","insert","sum"], [[],["cat",4],["car",1],["ca"],["cat",10],["ca"]]
Output
[null,null,null,5,null,11]
cat=4 and car=1 give sum("ca") = 5. Inserting cat again replaces 4 with 10, so sum("ca") becomes 10 + 1 = 11.
Example 03
Input
["MapSum","insert","sum","sum"], [[],["dog",7],["do"],["cat"]]
Output
[null,null,7,0]
"dog" starts with "do", giving 7. No key starts with "cat", so that sum is 0.
03 · Constraints
- 011 <= key.length, prefix.length <= 50
- 02key and prefix consist of lowercase English letters
- 031 <= val <= 1000
- 04At most 50 calls in total are made to insert and sum
04 · Optimal complexity
- Time
- O(L) per operation
- Space
- O(total characters inserted)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.