Expand Recursive Key-Value Placeholders in a Template

Question

The candidate is asked to implement a function that expands recursive key-value placeholders in a given template string.

Codemia · Accepted Answer

To solve the problem of expanding recursive key-value placeholders, I will use a recursive function that searches for placeholders in the template string. When a placeholder is found, I will replace it with its corresponding value from the provided dictionary. If the value itself contains placeholders, the function will call itself recursively until all placeholders are resolved.

1. Define a function `expand_template(template, values)` that takes a template string and a dictionary of values.
2. In the function, check for the presence of a placeholder using a regular expression.
3. If a placeholder is found, extract the key and look it up in the values dictionary.
4. Replace the placeholder with the corresponding value and call the function again on the new string if necessary.
5. Return the fully expanded string when no placeholders are left.

The time complexity of this solution is O(n * m) where n is the number of characters in the template string and m is the number of recursive calls made. The space complexity is O(m) due to the recursion stack.

Here is a sample implementation in Python:
```python
import re

def expand_template(template, values):
    pattern = re.compile(r'\{(\w+)\}')  # Regex to find placeholders
    while pattern.search(template):
        template = pattern.sub(lambda match: values.get(match.group(1), ''), template)
    return template
```
This function uses regex to find placeholders and replaces them with their corresponding values recursively.

It's important to consider edge cases such as:
- Missing keys in the values dictionary, which should return an empty string or a default value.
- Circular references, where a placeholder refers to another placeholder that eventually refers back to the original. This should be handled to avoid infinite loops.

Expand Recursive Key-Value Placeholders in a Template

Google

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string