Katkat
Back

Layer Config Trees with Pluggable Per-Path Merge Strategies

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Combine a default configuration tree with an environment overlay where each path can pick a merge strategy such as deep, override, preserve, concat, union, or keyed list matching, and new strategies plug in without touching the traversal. Tests simultaneous tree recursion, registry-based extensibility, ordering rules and type-conflict handling.

A deployment tool builds each service's final configuration by layering an environment overlay on top of a default config. Both have already been parsed from YAML/JSON into plain Python values: dicts with string keys, lists, and scalars (str, int, float, bool, None).

How two corresponding nodes combine is chosen per node by a strategy table keyed by path:

def layer(default, overlay, strategies: dict[str, str]):
    ...

Paths start at / and join dict keys with /, so /app/queues is default["app"]["queues"]. Items inside a list that is merged with keyed: get the path of the list plus [], so a strategy for /app/queues[]/labels applies to the labels of every matched queue item.

StrategyValid forResult
deepdict + dictKeys present on one side are copied as-is. Keys present on both are layered recursively. Key order: default's keys, then keys new in overlay.
overrideanythingthe overlay value
preserveanythingthe default value
concatlist + listdefault items, then overlay items
unionlist + list of scalarsconcat with later duplicates removed, first-seen order kept
keyed:<field>list + list of dictsItems with the same <field> value are layered recursively. Unmatched default items keep their positions, and unmatched overlay items are appended in overlay order.

A node with no entry in the table uses deep if both sides are dicts and override otherwise. If a strategy is applied to the wrong types, raise TypeError naming the path. Inputs must not be mutated.

The set of strategies will grow (teams have asked for max, prepend, sorted-union, ...). Adding one must not require editing the tree-walking code.

Example

default = {"app": {
    "name": "ledger", "workers": 4,
    "plugins": ["auth", "metrics"],
    "tags": ["prod", "eu"],
    "queues": [{"id": "email", "concurrency": 2, "retry": 3},
               {"id": "sms", "concurrency": 1}],
}}
overlay = {"app": {
    "name": "ledger-v2", "workers": 8,
    "plugins": ["tracing"],
    "tags": ["eu", "canary"],
    "queues": [{"id": "sms", "concurrency": 5}, {"id": "push", "concurrency": 2}],
    "region": "eu-west-1",
}}
strategies = {"/app/name": "preserve", "/app/plugins": "concat",
              "/app/tags": "union", "/app/queues": "keyed:id"}

layer(default, overlay, strategies) == {"app": {
    "name": "ledger", "workers": 8,
    "plugins": ["auth", "metrics", "tracing"],
    "tags": ["prod", "eu", "canary"],
    "queues": [{"id": "email", "concurrency": 2, "retry": 3},
               {"id": "sms", "concurrency": 5},
               {"id": "push", "concurrency": 2}],
    "region": "eu-west-1",
}}

Implement layer, explain how a new strategy is plugged in, and give the time complexity.

Hints

Hint 1

Write one recursive function that looks up the rule for the current path and delegates. Don't put strategy logic in the walker.

Hint 2

Give strategies a callback into the walker so deep and keyed can recurse without knowing how rules are resolved.

Hint 3

For keyed lists, index the default items by key value first. Then decide where matched and unmatched overlay items go.

Hint 4

Copy one-sided subtrees instead of sharing them, so mutating the result can't change the inputs.

Follow-up questions

  • Support wildcard rule paths like /services/*/ports. How do you resolve conflicts between a wildcard and an exact rule?
  • How would you let the overlay file itself declare strategies inline (e.g. a special !concat YAML tag)?
  • Users want to know where each final value came from. How would you record provenance during the merge?
  • How would you layer N files (default, region, env, host) efficiently?