# Expand Recursive Key-Value Placeholders in a Template Implement template expansion for a map of string keys to string values. A placeholder has the form `%KEY%`. Replace placeholders in the input template with their mapped values, and recursively expand placeholders that occur inside mapped values. For example: ```text values = { "USER": "admin", "HOME": "/%USER%/home" } template = "I am %USER% My home is %HOME%" output = "I am admin My home is /admin/home" ``` For the core task, assume every placeholder is well formed, every referenced key exists, and the dependency graph among map values is acyclic. Preserve all non-placeholder text exactly. ### Constraints & Assumptions - Placeholder names are matched exactly and case-sensitively. - A mapped value may reference more than one other key and may be referenced by many templates. - Repeated references to the same key should not require resolving its entire dependency chain again. ### Clarifying Questions to Ask - What should happen for an unknown key or malformed unmatched `%` character? - What escaping syntax should produce a literal percent sign? - Should a dependency cycle raise an error, preserve the unresolved placeholder, or use another explicit result? ```hint Model dependencies explicitly Each map entry can be viewed as a node with edges to the keys referenced in its value. ``` ```hint Cache completed expansions Distinguish a key currently being resolved from one whose final expansion has already been computed. ``` ### Evaluation Criteria - Correct parsing of `%KEY%` tokens without changing literal text. - Recursive expansion of values such as `HOME -> /%USER%/home`. - Memoization so shared dependencies are expanded once. - A defensible cycle-detection strategy using traversal states or topological ordering. - Complexity in terms of the template, map values, references, and produced output. ### Extensions to Discuss - How would you detect and report a cyclic dependency among keys? - How would you flatten all map values once for repeated template expansion? - What unambiguous escape rule would you choose for literal `%` characters and why?