Map Sum Pairs

📋

Map Sum Pairs

Edge cases:

</>

IDE

def insert(self, key: str, val: int) -> None: def sum(self, prefix: str) -> int:public void insert(String key, int val) public int sum(String prefix)void insert(string key, int val) int sum(string prefix)function insert(key, val) function sum(prefix)

class MapSum:
    def __init__(self):
        # Write your solution here
        pass
    def insert(self, key: str, val: int) -> None:
        pass
    def sum(self, prefix: str) -> int:
        pass

class MapSum {
    public MapSum() {
        // Write your solution here
    }
    public void insert(String key, int val) {
        // Write your solution here
    }
    public int sum(String prefix) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

class MapSum {
public:
    MapSum() {
        // Write your solution here
    }
    void insert(string key, int val) {
        // Write your solution here
    }
    int sum(string prefix) {
        // Write your solution here
        return 0;
    }
};

class MapSum {
    constructor() {
        // Write your solution here
    }
    insert(key, val) {
        // Write your solution here
    }
    sum(prefix) {
        // Write your solution here
        return 0;
    }
}

Common Bugs to Avoid

Wrong: Sum returns total of all keys regardless of prefixSum method does not filter keys by prefix, sums all values✅ In sum method, only add values for keys starting with the given prefix.

Wrong: Sum returns outdated values after updating existing keyInsert does not update prefix sums correctly when key is overwritten✅ Track old value of key and update prefix sums by subtracting old and adding new value.

Wrong: Sum returns non-zero for prefix not presentSum method does not handle missing prefix nodes, returns garbage or error✅ Return 0 if prefix path does not exist in trie.

Wrong: Sum with empty prefix returns 0 instead of total sumSum method does not handle empty prefix as sum of all keys✅ If prefix is empty, return sum of all keys stored in trie root node.

Wrong: Solution times out on large inputsSum queries scan all keys instead of using trie prefix sums✅ Implement trie with prefix sums to achieve O(k) insert and sum operations.

✓

Test Cases

Focus on handling edge cases like empty keys and prefix sums for missing prefixes.

Test your solution against tricky updates and nested prefix sums.

Ensure your solution runs efficiently on large inputs using trie prefix sums.

t1_01basic

Input[{"method":"insert","args":["apple",3]},{"method":"sum","args":["ap"]},{"method":"insert","args":["app",2]},{"method":"sum","args":["ap"]}]

Expected[null,3,null,5]

⏱ Performance - must finish in 2000ms

After inserting 'apple' with value 3, sum('ap') returns 3. Then inserting 'app' with value 2, sum('ap') returns 3 + 2 = 5.

💡 Think about storing prefix sums to quickly answer sum queries.

💡 Use a trie where each node keeps track of the sum of all keys passing through it.

💡 Update sums on insert by adding the difference between new and old values for the key.

Why it failed: Basic case failed - likely not updating prefix sums correctly on insert or summing all keys instead of prefix keys. Fix by maintaining prefix sums in trie nodes and updating them properly.

✓ Core insert and sum operations correctly handle prefix sums.

t1_02basic

Input[{"method":"insert","args":["banana",4]},{"method":"sum","args":["ban"]},{"method":"insert","args":["band",3]},{"method":"sum","args":["ban"]}]

Expected[null,4,null,7]

⏱ Performance - must finish in 2000ms

Insert 'banana' with 4, sum('ban') returns 4. Insert 'band' with 3, sum('ban') returns 4 + 3 = 7.

💡 Check that sum queries return sums of all keys starting with the prefix.

💡 Ensure insert updates sums for all prefixes of the key.

💡 When inserting a key that shares prefix, sums should accumulate correctly.

Why it failed: Sum query returned incorrect total - likely sums not updated for all prefix nodes during insert. Fix by propagating value changes along the prefix path.

✓ Sum queries correctly aggregate values for all keys with the given prefix.

t2_01edge

Input[{"method":"sum","args":["xyz"]}]

Expected[0]

⏱ Performance - must finish in 2000ms

Sum on prefix 'xyz' that does not exist returns 0.

💡 What should sum return if prefix is not found in trie?

💡 Check if your sum method handles missing prefix nodes gracefully.

💡 Return 0 if prefix path does not exist in trie.

Why it failed: Sum returned non-zero or error for non-existent prefix. Fix by returning 0 when prefix node is missing.

✓ Sum correctly returns 0 for prefixes not present.

t2_02edge

Input[{"method":"insert","args":["apple",3]},{"method":"insert","args":["apple",5]},{"method":"sum","args":["app"]}]

Expected[null,null,5]

⏱ Performance - must finish in 2000ms

Insert 'apple' with 3, then update 'apple' with 5. Sum('app') returns updated value 5.

💡 Inserting a key that already exists should update its value, not add.

💡 Track old values to adjust prefix sums correctly on update.

💡 Subtract old value and add new value to prefix sums during insert.

Why it failed: Sum returned incorrect total after updating existing key. Fix by storing previous key value and adjusting prefix sums accordingly.

✓ Insert correctly updates existing keys and prefix sums.

t2_03edge

Input[{"method":"insert","args":["",10]},{"method":"sum","args":[""]}]

Expected[null,10]

⏱ Performance - must finish in 2000ms

Insert empty string key is invalid and ignored. Sum with empty prefix returns sum of all keys, which is 10 here.

💡 Empty string keys are invalid; decide how to handle them.

💡 Ignore insertions with empty keys to avoid corrupting trie.

💡 Sum with empty prefix should return sum of all keys inserted.

Why it failed: Empty key insertion affected trie or sum returned non-zero incorrectly. Fix by ignoring empty keys on insert.

✓ Empty key insertions ignored; sum with empty prefix returns total sum.

t2_04edge

Input[{"method":"insert","args":["z",7]},{"method":"sum","args":["z"]},{"method":"sum","args":[""]}]

Expected[null,7,7]

⏱ Performance - must finish in 2000ms

Insert single element 'z' with 7. Sum('z') returns 7. Sum('') returns total sum 7.

💡 Test single element insert and sum with prefix equal to key.

💡 Sum with empty prefix returns total sum of all keys.

💡 Ensure sums are consistent for single element and empty prefix.

Why it failed: Sum returned incorrect values for single element or empty prefix. Fix by correctly handling sums for single keys and empty prefix.

✓ Single element sums and empty prefix sums handled correctly.

t3_01corner

Input[{"method":"insert","args":["a",1]},{"method":"insert","args":["ab",2]},{"method":"insert","args":["abc",3]},{"method":"sum","args":["a"]},{"method":"sum","args":["ab"]},{"method":"sum","args":["abc"]}]

Expected[null,null,null,6,5,3]

⏱ Performance - must finish in 2000ms

Sum queries test prefix sums with nested prefixes: sum('a')=1+2+3=6, sum('ab')=2+3=5, sum('abc')=3.

💡 Check if sums include all keys with the prefix, including nested longer keys.

💡 Verify prefix sums accumulate correctly for all prefixes.

💡 Ensure sum returns correct totals for prefixes of varying lengths.

Why it failed: Sum queries returned incorrect totals for nested prefixes. Fix by correctly accumulating sums for all prefixes in trie nodes.

✓ Sum queries correctly handle nested prefixes.

t3_02corner

Input[{"method":"insert","args":["abc",2]},{"method":"insert","args":["abcd",3]},{"method":"insert","args":["abc",5]},{"method":"sum","args":["abc"]}]

Expected[null,null,null,8]

⏱ Performance - must finish in 2000ms

Insert 'abc' with 2, 'abcd' with 3, update 'abc' to 5. Sum('abc') returns 5 + 3 = 8.

💡 Updating a key should adjust sums without double counting.

💡 Track previous values to update prefix sums correctly.

💡 Subtract old value and add new value on insert update.

Why it failed: Sum returned incorrect total after key update due to double counting. Fix by adjusting prefix sums with value difference.

✓ Sum correctly reflects updated key values without double counting.

t3_03corner

Input[{"method":"insert","args":["a",1]},{"method":"insert","args":["b",2]},{"method":"sum","args":[""]},{"method":"sum","args":["c"]}]

Expected[null,null,3,0]

⏱ Performance - must finish in 2000ms

Sum with empty prefix returns sum of all keys (1+2=3). Sum with prefix 'c' returns 0 as no keys start with 'c'.

💡 Sum with empty prefix should return total sum of all keys.

💡 Sum with prefix not present should return 0.

💡 Ensure sum handles empty prefix and missing prefix cases distinctly.

Why it failed: Sum with empty prefix or missing prefix returned wrong values. Fix by returning total sum for empty prefix and 0 for missing prefix.

✓ Sum handles empty and missing prefixes correctly.

t4_01performance

Input[{"method":"insert","args":["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",100000]},{"method":"insert","args":["bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb",99999]},{"method":"insert","args":["cccccccccccccccccccccccccccccccccccccccccccccccccc",88888]},{"method":"sum","args":["a"]},{"method":"sum","args":["b"]},{"method":"sum","args":["c"]},{"method":"sum","args":[""]},{"method":"insert","args":["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",1]},{"method":"sum","args":["a"]}]

Expected[null,null,null,100000,99999,88888,288887,null,100000]

⏱ Performance - must finish in 2000ms

n=9 calls with max key length 50; O(k) insert and sum must complete within 2s.

💡 Brute force scanning all keys for sum is too slow for large inputs.

💡 Use a trie with prefix sums to achieve O(k) per operation.

💡 Avoid recomputing sums by storing cumulative values in trie nodes.

Why it failed: TLE due to O(n*k) sum scanning all keys. Fix by implementing trie with prefix sums for O(k) operations.

✓ Efficient trie-based solution meets performance constraints.

Practice

1. Given the following code snippet implementing the trie-based autocomplete, and the input products = ["mobile", "mouse", "moneypot"] and searchWord = "mo", what is the value of the variable result after processing the entire searchWord?

easy

A. [["mobile", "moneypot", "mouse"], ["moneypot", "mobile", "mouse"]]

B. [["mobile", "moneypot", "mouse"], ["mobile", "moneypot", "mouse"]]

C. [["mobile", "mouse", "moneypot"], ["mobile", "mouse", "moneypot"]]

D. [["mobile", "mouse", "moneypot"], ["mouse", "mobile", "moneypot"]]

Solution

1. Step 1: Sort products lexicographically

   Sorted products: ["mobile", "moneypot", "mouse"]

2. Step 2: Build trie and collect suggestions

   For prefix 'm': suggestions are ["mobile", "moneypot", "mouse"]. For prefix 'mo': same suggestions as all start with 'mo'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Result matches expected suggestions for prefixes 'm' and 'mo' [OK]

Hint: Sorted products determine suggestion order at each prefix [OK]

Common Mistakes:

• Mixing order of suggestions
• Off-by-one in prefix traversal
• Appending suggestions after node moves

2. You are given a list of words and need to find the shortest prefix for each word that uniquely identifies it among all words. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Build a trie where each node tracks how many words pass through it, then find the prefix where frequency is 1.

B. Sort the words and compare only adjacent words to find the shortest unique prefix.

C. Compare each word's prefixes pairwise with all other words to find uniqueness.

D. Use dynamic programming to store prefix uniqueness states for all words.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding shortest unique prefixes efficiently for all words, which suggests a data structure that can share prefixes.

2. Step 2: Evaluate approaches

   Brute force (A) is too slow (O(n^2 * m)). Sorting + adjacent comparison (C) can miss conflicts with non-adjacent words. DP (D) is not a natural fit here. Trie with frequency counts (B) efficiently tracks prefix usage and finds unique prefixes in O(n*m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie frequency counting matches problem needs [OK]

Hint: Trie frequency counts track prefix uniqueness efficiently [OK]

Common Mistakes:

• Assuming sorting adjacent words is sufficient for uniqueness
• Trying brute force despite inefficiency

3. Consider the following code snippet implementing the optimal trie-based solution for shortest unique prefixes. Given the input words = ["dog", "dove", "duck"], what is the output of shortest_unique_prefix(words)?

easy

A. ["do", "dov", "du"]

B. ["d", "dov", "du"]

C. ["dog", "dove", "duck"]

D. ["dog", "dov", "du"]

Solution

1. Step 1: Trace insertion frequencies

   Insert "dog": d(1), o(1), g(1); "dove": d(2), o(2), v(1), e(1); "duck": d(3), u(1), c(1), k(1).

2. Step 2: Find unique prefixes

   For "dog": prefix "dog" (g freq=1) unique; for "dove": prefix "dov" (v freq=1) unique; for "duck": prefix "du" (u freq=1) unique.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefixes match first node with freq=1 [OK]

Hint: Unique prefix ends where node freq equals 1 [OK]

Common Mistakes:

• Stopping prefix too early
• Assuming first letter always unique

4. The following code attempts to find index pairs of substrings matching words using a trie + DFS approach. Identify the line containing the subtle bug that causes incorrect or incomplete results.

medium

A. Line: return res # Missing sorting before return

B. Line: if i == n: return

C. Line: for i in range(n): dfs(root, i, i)

D. Line: if node.word_end: res.append([start, i-1])

Solution

1. Step 1: Identify expected output order

   The problem requires the output list of index pairs to be sorted. The code returns res without sorting.

2. Step 2: Understand impact of missing sort

   Without sorting, the output order may differ from expected, causing wrong answer in tests even if all pairs are found.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding res.sort() before return fixes the bug [OK]

Hint: Output must be sorted before returning [OK]

Common Mistakes:

• Forgetting to sort results before returning

5. Suppose the problem is modified so that root words can be reused multiple times to replace multiple prefixes in a single word (e.g., 'catcat' could be replaced by 'catcat' if 'cat' is a root). Which modification to the trie-based approach correctly handles this variant?

hard

A. Use the existing shortest prefix search once per word; no change needed as reuse is irrelevant.

B. After finding the shortest prefix, continue searching the remaining suffix recursively for more prefixes to replace.

C. Modify search to find the longest prefix instead of shortest, then recursively replace the suffix with roots.

D. Replace the entire word only if it exactly matches a root; otherwise, leave it unchanged.

Solution

1. Step 1: Understand reuse requirement

   Words can be replaced by concatenations of multiple root prefixes, so partial replacements must continue recursively.

2. Step 2: Modify search logic

   After finding a shortest prefix, recursively apply the same prefix search on the remaining suffix to replace all possible prefixes.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursive prefix replacement handles multiple root reuse correctly [OK]

Hint: Recursively replace suffixes after shortest prefix [OK]

Common Mistakes:

• Stopping after first prefix
• Searching for longest prefix only