key-store

Key Store With Sum-Dependency Cascades

Implement a key store supporting set_value(k, v), set_sum(k, [other_keys]), and get_value(k). Updating a base key cascades through all dependent sum keys.

Requirements

• set_value(key, value) — store an integer under key.
• set_sum(key, refs) — define key as the sum of the current values of refs (multiplicity matters: ["C", "C", "A"] means 2*C + A).
• get_value(key) — return the integer for key. If key was defined via set_sum, return the live computed sum.

Updating any base key must propagate the new sum through every dependent.

Example:

set_value("A", 5)             # A = 5
set_value("B", 10)            # B = 10
set_sum("C", ["A", "B"])      # C = 15
set_sum("D", ["C", "C", "A"]) # D = 2*15 + 5 = 35
get_value("C") -> 15
get_value("D") -> 35
set_value("A", 100)           # cascade: C = 110, D = 320
get_value("D") -> 320

Follow-up: "If get_value is rare and set_value is frequent, optimize set_value." → swap the eager-propagation model for lazy evaluation with a dependency graph that recomputes on read.

Notes

• Two natural designs:
• Eager: maintain a dependents[base_key] -> set[dependent_key] reverse index; on set_value recompute the topological order over the affected subgraph and update cached values. Reads are O(1), writes are O(subgraph).
• Lazy: store only the formula on set_sum; resolve on read by recursive expansion with memoization invalidated on set_value. Reads are O(formula tree), writes are O(1).
• Watch the multiplicity rule: set_sum("D", ["C", "C", "A"]) is 2*C + A, not {C, A}.
• Detect cycles on set_sum — a sum key that transitively depends on itself is undefined. Reject with an error.
• Topological order is computed via Kahn's algorithm on the dependents subgraph.
• Edge cases: redefining a key with set_value after it was a sum key (clarify whether to wipe the formula), unknown reference in set_sum, deleting a key.

Preparation

• Implement the eager version with explicit reverse-index propagation in 20 minutes.
• Layer a set_value micro-optimization: bail out early if the new value equals the old.
• Drill the lazy variant on paper; be ready to switch based on the follow-up's read / write skew.
• Pre-script the cycle-detection answer ("Kahn's algorithm on the proposed set_sum; reject if the graph has a back-edge") — this is the most common follow-up after the main implementation.

eagar-propagation

注意维护children和parents，在set的时候上下都要清理

class KeyStore:
    def __init__(self):
        self.children = {}
        self.parents = {}
        self.val = {}

    def update_sum(self, key):
        val = 0
        for child in self.children[key]:
            val += self.val[child]
        self.val[key] = val

    def update_parent(self, key):
        if key not in self.parents:
            self.parents[key] = set()
            return
        p = deque()
        p.append(key)
        while p:
            node = p.popleft()
            for parent in self.parents[node]:
                self.update_sum(parent)
                p.append(parent)

    def set_value(self, key: str, val: int) -> None:
        if key in self.children:
            for c in self.children[key]:
                self.parents[c].remove(key)
        self.children[key] = []
        self.val[key] = val
        self.update_parent(key)

    def set_sum(self, key: str, refs: List[str]) -> None:
        self.children[key] = refs
        for child in refs:
            if key not in self.parents[child]:
                self.parents[child].add(key)
        self.update_sum(key)
        self.update_parent(key)

    def get_value(self, key: str) -> int:
        return self.val[key]

lazy-propagation

loop detect