Implement nested template string substitution

Q: Implement nested template string substitution

This question evaluates understanding of string processing, dependency resolution, recursive expansion, cycle detection, and efficiency techniques such as memoization for nested template substitution.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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).

Implement nested template string substitution

Overview

Requirements / edge cases

Comments (0)