Map Sum Pairs

Interview Problem Interview Medium Prefix Sum Hash Map Trie

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement MapSum.insert(key, val) and sum(prefix). Inserting an existing key replaces its value; sum returns values of all keys beginning with prefix.

Starter code

class MapSum:
    def __init__(self):
        pass

Test cases

insert-and-replace

{
  "operations": [
    "MapSum",
    "insert",
    "sum",
    "insert",
    "sum",
    "insert",
    "sum"
  ],
  "arguments": [
    [],
    [
      "apple",
      3
    ],
    [
      "ap"
    ],
    [
      "app",
      2
    ],
    [
      "ap"
    ],
    [
      "apple",
      2
    ],
    [
      "ap"
    ]
  ]
}

Expected: [null,null,3,null,5,null,4]

Wizard outline

Step 1: Initialize MapSum
Replace the empty starter with the first real state owned by MapSum. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Wizard Stateful Mapsum New Key case
Complete the readable core algorithm for one representative Interview case. Updating all prefixes at insertion makes each later sum query O(1).
Step 4: Harden the Wizard Stateful Mapsum Replacement boundary
Repair the reviewed boundary and pass the complete submission contract. Delta updates preserve totals shared with other keys while removing the old contribution exactly once.

Footguns and prerequisites

Adding the full replacement value again double-counts an existing key; update aggregates by new-old.
strings
dictionaries and sets

Reviewed references

LeetCode 677 — Map Sum Pairs

Practice prerequisites

Follow Trie Edges(opens in a new tab)
Follow Trie Edges isolates after matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match. That focused state discipline is required when implementing map sum pairs as a complete Interview Problem.

Recommended approach and implementation

Store current values by full key and aggregate totals by every non-empty prefix. On insert compute delta=val-old and add it to each prefix total.

Why it works: Each key contributes its current value once to every prefix it begins with. Applying only the replacement delta changes those aggregates from the old contribution to the new one, so every sum lookup is exact.

class MapSum:
    """
    Checkpoint 1: initialize the state owned by this Interview contract.
    Checkpoint 2: assemble the primary transition without hiding the boundary.
    """
    def __init__(self):
        self.values = {}
        self.prefix_totals = {}
    def insert(self, key, val):
        delta = val - self.values.get(key, 0)
        self.values[key] = val
        for end in range(1, len(key) + 1):
            prefix = key[:end]
            self.prefix_totals[prefix] = self.prefix_totals.get(prefix, 0) + delta
    def sum(self, prefix):
        return self.prefix_totals.get(prefix, 0)

Similar exercises

Implement Trie(opens in a new tab)