Expand Nested Substitutions and Detect Reachable Cycles

A template contains references to replacement strings. First explain one-level substitution. Then support replacement strings that themselves contain references, and detect a cycle while expanding the template. Use `%key%` as the placeholder notation for this practice formulation. A dictionary maps each key to a string containing literal text and zero or more placeholders. Expand the requested template fully, or report a cycle error if expansion reaches a cyclic dependency. Do not perform a separate cycle scan over the entire dictionary before expanding. ### Constraints & Assumptions - Placeholder syntax is well formed, keys are nonempty, and every referenced key is present. These are explicit practice preconditions because malformed and missing-key behavior was not specified in the report. - Values may share dependencies or refer to the same key several times. - A key being expanded on the current dependency path is different from a key that was expanded earlier and completed. - No numerical size or output-length bounds were reported. - For the on-demand cycle check, an unused cyclic dictionary entry is not visited merely because it exists. ### Illustrative Examples These examples explain the normalized notation; they are not reported interview samples. ```text replacements = {A: "hello", B: "%A% world"} template = "%B% / %A%" Expanded result: "hello world / hello" ``` ```text replacements = {A: "%B%", B: "%A%"} template = "%A%" Result: cycle error ``` ### Clarifying Questions to Ask - Does substitution apply recursively to inserted values? The final version requires it. - What should missing keys or malformed placeholders do? This formulation excludes them pending a separate policy. - Should an unreachable cycle fail the request? The requested detection is during expansion, so only reached dependencies are examined. ### Part 1 — One-Level and Nested Expansion Describe parsing and substitution, then extend it to recursively resolve referenced values. #### What This Part Should Cover - Literal text preservation and placeholder boundaries. - The difference between scanning original input and recursively expanding inserted text. - Reuse of completed expansions without changing their meaning. ### Part 2 — Detect Cycles During Expansion Add cycle detection to the expansion process itself. #### What This Part Should Cover - A current recursion-path marker and correct removal on exit. - A distinction between active, completed, and not-yet-visited keys. - A clear error result without returning a partially expanded template. ```hint A key referenced twice by separate branches is not a cycle if its first expansion has already finished. ``` ### What a Strong Answer Covers The algorithm should correctly expand shared nested replacements, detect self and indirect cycles only when reached, and avoid false cycles caused by never clearing the active-path set. Complexity must include the potentially large expanded output. ### Follow-up Questions - How would you avoid call-stack exhaustion for a very deep dependency chain? - Why can expanded output be much larger than the dictionary text? - What changes if replacements can be updated between requests?