Recursion template for nested dicts/lists:if isinstance(v, dict): recurse(v) elif isinstance(v, list): for item in v: recurse(item) else: process(v)
— this covers virtually all nested-data problems.
P 32Coding ProblemMedium
Flatten Nested Dict (Dot-Notation Keys)
Given an arbitrarily nested dict, flatten it into a single-level dict where nested keys are joined by ".".
Example: {"a": {"b": {"c": 1}}} → {"a.b.c": 1}.
Non-dict values (int, str, list) should become leaf values.
from typing import Dict, Any
defflatten_dict(d: Dict, parent_key: str = "", sep: str = ".") -> Dict[str, Any]:
items: dict = {}
for k, v in d.items():
# Build the new key: prepend parent path if it exists
new_key = f"{parent_key}{sep}{k}"if parent_key else k
ifisinstance(v, dict):
# Recurse and merge the flattened sub-dict into items
items.update(flatten_dict(v, new_key, sep))
else:
items[new_key] = v # leaf valuereturn items
Key ideas: Pass the accumulated key path (parent_key) as a parameter through the recursion.
Use dict.update() to merge the results of recursive calls — each recursive call returns a flat dict.
The ternary f"{parent_key}{sep}{k}" if parent_key else k handles the root level cleanly (no leading dot).
Lists and other non-dict values are treated as leaf values.
P 33Coding ProblemMedium
Deep Merge Two Dicts
Merge two nested dicts. Where both dicts have the same key and both values are dicts themselves, recurse.
Otherwise, the second dict wins. Return a new dict — do not mutate the inputs.
recursionisinstance(v, dict)dict.copy() to avoid mutationdict.items() traversal
Solution
from typing import Dict, Any
defdeep_merge(base: Dict, override: Dict) -> Dict:
result = base.copy() # shallow copy — we'll update values as neededfor key, val in override.items():
if (key in result
andisinstance(result[key], dict)
andisinstance(val, dict)):
# Both sides are dicts: recurse to merge them
result[key] = deep_merge(result[key], val)
else:
# Override wins for non-dict values or new keys
result[key] = val
return result
Key ideas: Start with a copy of base, then apply override changes.
Only recurse when both the existing value and the new value are dicts — otherwise just overwrite.
dict.copy() gives a shallow copy: safe here because we replace dict values rather than mutating them.
This is cleaner than a plain base | override merge which would overwrite entire nested dicts.
P 34Coding ProblemMedium
JSON Diff — Find What Changed
Given two flat-or-shallow dicts old and new, return a diff dict with three keys:
added (keys only in new), removed (keys only in old), changed (keys in both but with different values — show as (old_val, new_val)).
set operations on dict keysset difference (-)set intersection (&)dict comprehension
Solution
from typing import Dict, Any
defjson_diff(old: Dict, new: Dict) -> Dict:
old_keys = set(old)
new_keys = set(new)
added = {k: new[k] for k in new_keys - old_keys}
removed = {k: old[k] for k in old_keys - new_keys}
changed = {
k: (old[k], new[k])
for k in old_keys & new_keys
if old[k] != new[k]
}
return {"added": added, "removed": removed, "changed": changed}
Key ideas: Converting dict keys to sets enables set algebra.
new_keys - old_keys = keys only in new (added).
old_keys - new_keys = keys only in old (removed).
old_keys & new_keys = keys in both — filter those where values differ.
Each line is a single dict comprehension — clean, readable, and O(n).
P 35Coding ProblemMedium
Extract All Values by Key (Deep Search)
Given a deeply nested JSON-like structure (dicts and lists), return all values associated with a given key name,
regardless of how deeply nested they are. Order: depth-first, left-to-right.
recursion on dict and listisinstance checkslist.extend from recursive callsDFS order
Solution
from typing import List, Any
defextract_values(data: Any, key: str) -> List[Any]:
results = []
ifisinstance(data, dict):
if key in data:
results.append(data[key]) # found a match at this levelfor v in data.values():
results.extend(extract_values(v, key)) # recurse into all valueselifisinstance(data, list):
for item in data:
results.extend(extract_values(item, key)) # recurse into list itemsreturn results
Key ideas: Three cases: dict (check for key, recurse into values), list (recurse into items), anything else (base case, return empty).
Use extend to merge results from recursive calls.
This is DFS — it processes the current level before descending, which gives the natural top-down order seen in the example.
Works for any mix of nesting depths.
P 36Coding ProblemEasy
Safe Nested Get (deep_get)
Implement deep_get(data, path, default=None) where path is a dot-separated key path like "a.b.c".
Safely traverse the nested dict without raising KeyError.
Return default if any key in the path is missing.
str.split('.')loop over key pathisinstance checkdict.get(key, sentinel)
Solution
from typing import Any
defdeep_get(data: Any, path: str, default: Any = None) -> Any:
keys = path.split(".")
current = data
for key in keys:
if notisinstance(current, dict):
return default # can't traverse into a non-dict
current = current.get(key)
if current is None:
return default
return current
Key ideas: Split the path once, then walk key by key.
Two failure modes: (1) the current value is not a dict (can't traverse further), (2) .get(key) returns None (key missing).
Note: this version can't distinguish between a stored value of None and a missing key.
A more robust version uses a sentinel: _MISSING = object() and checks current.get(key, _MISSING) is _MISSING.
P 37Coding ProblemMedium
CSV to Nested JSON
Given a CSV string where column names use dot-notation (e.g., user.name, user.age, address.city),
convert each row into a properly nested dict. Return a list of these dicts.
csv.DictReaderio.StringIOsplit key on '.'dict.setdefault for nested build
Solution
import csv
from io import StringIO
from typing import List, Dict
defcsv_to_nested(csv_text: str) -> List[Dict]:
reader = csv.DictReader(StringIO(csv_text))
results = []
for row in reader:
nested: dict = {}
for col, val in row.items():
keys = col.split(".")
d = nested
# Walk to the second-to-last key, creating dicts as neededfor k in keys[:-1]:
d = d.setdefault(k, {})
d[keys[-1]] = val # set the leaf value
results.append(nested)
return results
Key ideas:dict.setdefault(key, {}) is the elegant way to build nested dicts on the fly —
it returns the existing value if the key exists, or inserts and returns the default if it doesn't.
The loop for k in keys[:-1] walks all but the last key segment (building intermediate dicts).
Then d[keys[-1]] = val sets the leaf.
This handles arbitrary depth: "a.b.c.d" creates three nested dicts automatically.
P 38Coding ProblemHard
Recursive JSON PII Redactor
Given a deeply nested JSON-like object (dicts, lists, strings, numbers), redact all string values using a PII API.
The structure must be preserved — only string leaf values are processed.
Non-string values (int, float, bool, None) pass through unchanged.
The PII API takes a string and returns a list of {"start_offset", "end_offset", "type"} entities.
Return the redacted object and a total pii_count across all strings.
Example
data = {
"user": {
"name": "Alice Smith", # → "[NAME]"
"age": 30, # int — unchanged
"emails": ["alice@ex.com"] # → ["[EMAIL_ADDRESS]"]
},
"note": "Contact Alice Smith at alice@ex.com" # → "Contact [NAME] at [EMAIL_ADDRESS]"
}
redact_json(data, pii_api)
→ ({
"user": {"name": "[NAME]", "age": 30, "emails": ["[EMAIL_ADDRESS]"]},
"note": "Contact [NAME] at [EMAIL_ADDRESS]"
},
{"NAME": 2, "EMAIL_ADDRESS": 2})
recursion on dict / list / strisinstance checksCounter.update() to merge countsright-to-left PII replacementstructure-preserving traversal
Solution
from collections import Counter
from typing import Any, Callable, Dict, List, Tuple
def_redact_string(text: str, pii_api: Callable) -> Tuple[str, Counter]:
"""Redact a single string value using the PII API. Returns (redacted, counts)."""
entities = pii_api(text)
counts: Counter = Counter(e["type"] for e in entities)
# Sort ascending, then reverse for right-to-left replacementfor entity insorted(entities, key=lambda e: e["start_offset"], reverse=True):
s, e, t = entity["start_offset"], entity["end_offset"], entity["type"]
text = text[:s] + f"[{t}]" + text[e:]
return text, counts
def_redact_recursive(obj: Any, pii_api: Callable, total: Counter) -> Any:
"""Recursively traverse obj, redacting all string leaf values in-place."""ifisinstance(obj, str):
redacted, counts = _redact_string(obj, pii_api)
total.update(counts)
return redacted
elifisinstance(obj, dict):
return {k: _redact_recursive(v, pii_api, total) for k, v in obj.items()}
elifisinstance(obj, list):
return [_redact_recursive(item, pii_api, total) for item in obj]
else:
return obj # int, float, bool, None — pass through unchangeddefredact_json(data: Any, pii_api: Callable) -> Tuple[Any, Dict[str, int]]:
total: Counter = Counter()
redacted = _redact_recursive(data, pii_api, total)
return redacted, dict(total)
Pattern — recursive traversal with accumulator:
Three cases: string (redact it), dict (recurse into values), list (recurse into items), else (pass through).
The total Counter is passed by reference and updated across all recursive calls — no need to return it from every level.
Helper _redact_string encapsulates the single-string redaction logic (reused from Category A P09).
Dict/list comprehensions rebuild the structure cleanly — no in-place mutation.
This problem combines: Category A (PII offset replacement) + Category E (recursive JSON traversal) — exactly the kind of "composition" question that senior engineering interviews use.