Map Sum Pairs

Map Sum Pairs

What is this problem about?

The Map Sum Pairs problem requires you to design a custom data structure. It must support two operations: insert(key, val) which inserts a string key and an integer value (overwriting the value if the key already exists), and sum(prefix) which returns the sum of all values whose associated keys start with the given string prefix.

Why is this asked in interviews?

This is a classic Object-Oriented Design and Data Structure problem. Interviewers ask it because it bridges the gap between a standard Hash Map and a Trie (Prefix Tree). It evaluates whether a candidate can recognize that while Hash Maps are great for exact matches, Tries are the undisputed kings of prefix-based grouping. It tests your ability to augment standard tree nodes with custom integer fields.

Algorithmic pattern used

The most efficient approach uses a Trie (Prefix Tree) augmented with a Hash Map for tracking overwrites.

1. The Hash Map stores the exact key -> val mappings so you can easily calculate the difference (delta) when a key is overwritten.
2. The Trie stores characters. However, each Trie node also stores a running score.
3. During insert, calculate the delta = new_val - old_val. Traverse down the Trie character by character, adding the delta to every node's score along the path.
4. During sum(prefix), traverse down the Trie following the prefix. If the prefix exists, the score stored at the final character's node is your exact $O(1)$ sum!

Example explanation

insert("apple", 3):

• Hash Map: {"apple": 3}. Delta = 3.
• Trie Nodes: a(3) -> p(3) -> p(3) -> l(3) -> e(3). insert("app", 2):
• Hash Map: {"apple": 3, "app": 2}. Delta = 2.
• Trie Nodes: a(3+2=5) -> p(5) -> p(5). sum("ap"):
• Traverse to p. The score at node p is 5. Return 5. insert("apple", 5):
• Key exists! Old val = 3. New val = 5. Delta = 2.
• Traverse apple and add 2 to all nodes.
• a(5+2=7) -> p(7) -> p(7) -> l(5) -> e(5). sum("ap") now returns 7.

Common mistakes candidates make

Candidates frequently use a pure Hash Map and iterate through every single key during the sum() operation, checking key.startsWith(prefix). While this works, it takes $O(N \times K)$ time per query (where $N$ is total keys and $K$ is prefix length). The Trie approach answers queries in strict $O(K)$ time. Another mistake when using the Trie is failing to handle the "overwrite" condition properly, adding the entire new value to the nodes instead of just the difference.

Interview preparation tip

To master the Map Sum Pairs interview pattern, practice writing Trie nodes that hold metadata. Usually, a Trie node just holds a boolean isEnd. By adding an int sum to your node definition, you turn a simple spell-checker into a powerful categorical aggregator. Always keep a backup Hash Map to instantly find the old_value for delta calculations.