Katkat
Back

Implement nested template string substitution

WaymoData Scientist · Onsite
EasyData ScientistOnsiteCoding & Algorithms

Last updated

This problem tests your ability to handle recursive data structures and string parsing by expanding nested placeholders within a template string while identifying potential circular dependencies.

Problem Statement

You are given a dictionary of template definitions where keys are variable names and values are strings that may contain placeholders in the format {variable_name}. Your task is to implement a function that resolves all placeholders in a given target string into a fully expanded string.

If a placeholder refers to a variable that does not exist or if there is a circular dependency (e.g., A depends on B, and B depends on A), you should raise an error or return a specific indicator (e.g., None).

Function Signature

resolve_template(template_str, definitions)

Constraints

  • definitions is a dictionary of size N (up to 1000).
  • The recursion depth will not exceed 100.
  • template_str can contain multiple placeholders.

Examples

Example 1:

  • definitions: {"a": "Hello", "b": "{a} World"}
  • template_str: "{b}"
  • Output: "Hello World"

Example 2:

  • definitions: {"a": "{b}", "b": "{a}"}
  • template_str: "{a}"
  • Output: None (Circular dependency detected)

Edge Cases

  • A variable referencing itself.
  • Placeholders that have no definition in the map.
  • A template string with no placeholders.

Hints

Hint 1

Use a recursive function that tracks the current path of visited keys to detect cycles during the expansion process.

Hint 2

Consider using memoization to store the result of already expanded variables to improve performance for recurring placeholders.

Hint 3

Use a regular expression or a simple string search to identify all segments that follow the `{...}` pattern.

Follow-up questions

  • How would you modify your solution to handle cases where the definitions themselves are updated frequently?
  • What is the time complexity of your solution in the worst-case scenario given N variables and M nested levels?
  • How would you implement this iteratively instead of using recursion to avoid stack overflow errors for very deep nesting?