Implement nested template string substitution
Company: Waymo
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
You are given a dictionary (map) from keys to string templates. Templates may reference other keys using placeholders of the form `%KEY%`.
Example dictionary:
- `X -> "a"`
- `Y -> "b"`
- `Z -> "%X% and %Y%"`
Given an input string that may also contain placeholders (e.g., `"%X% and %Z%"`), output the fully substituted string.
For the example above:
- Input: `"%X% and %Z%"`
- Output: `"a and a and b"`
### Requirements / edge cases
- Placeholders can be **nested** (a key can reference other keys).
- Multiple occurrences of the same placeholder may appear.
- Define how you handle:
- Missing keys (e.g., `%W%` not in dictionary)
- Cycles (e.g., `A -> "%B%"`, `B -> "%A%"`)
- Aim for efficient time complexity (avoid repeatedly expanding the same key).
Quick Answer: This question evaluates understanding of string processing, dependency resolution, recursive expansion, cycle detection, and efficiency techniques such as memoization for nested template substitution.
Expand %KEY% placeholders using a template map. Missing keys stay unchanged; cycles become <CYCLE:key>.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ({'X':'a','Y':'b','Z':'%X% and %Y%'}, '%X% and %Z%')
Expected Output: 'a and a and b'
Explanation: Prompt example.
Input: ({'A':'%B%','B':'%A%'}, '%A%')
Expected Output: '<CYCLE:A>'
Explanation: Cycle marker.
Input: ({'A':'hi'}, '%A% %MISSING%')
Expected Output: 'hi %MISSING%'
Explanation: Missing key is preserved.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.