Implement templated string replacement
Company: Crowdstrike
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given:
1. A dictionary (map) of placeholder keys to values, for example:
```python
values = {
"db_host": "example.com",
"db_port": 5001
}
```
2. A template string that may contain placeholders wrapped in double curly braces `{{` and `}}`, for example:
```text
"application is now connecting to {{db_host}}:{{db_port}}"
```
### Task 1
Implement a function that replaces each placeholder in the template string with the corresponding value from the dictionary. For the example above, the output should be:
```text
"application is now connecting to example.com:5001"
```
Assume:
- All placeholders appearing in the template exist as keys in the dictionary.
- Placeholders consist of letters, digits, and underscores only.
Describe your approach and then implement the function in a programming language of your choice.
### Task 2 (Follow-up)
Now, instead of a single template string, you are given another dictionary where **each value is a template string** that may contain the same kind of `{{key}}` placeholders, and you are also given the same `values` dictionary used for substitution.
Example:
```python
values = {
"db_host": "example.com",
"db_port": 5001
}
templates = {
"conn_msg": "application is now connecting to {{db_host}}:{{db_port}}",
"short_msg": "{{db_host}}:{{db_port}}"
}
```
Implement a function that takes `values` and `templates` and returns a new dictionary where each value in `templates` has had its placeholders replaced using `values`.
Explain your algorithm, including its time complexity in terms of:
- `L` = total length of all template strings
- `K` = number of distinct keys in the `values` dictionary.
Quick Answer: This question evaluates proficiency in string parsing and template substitution, efficient use of dictionaries for key lookups, and the ability to reason about algorithmic time and space complexity.
Part 1: Replace Placeholders in a Single Template String
You are given a dictionary `values` that maps placeholder keys to values, and a template string that may contain placeholders in the form `{{key}}`. Replace every placeholder with its corresponding value from the dictionary and return the fully rendered string.
All placeholders are well-formed, every placeholder key exists in `values`, and keys contain only letters, digits, and underscores. If a value in `values` is not already a string, convert it to text before inserting it.
Constraints
- 0 <= len(template) <= 100000
- 0 <= len(values) <= 100000
- Every placeholder in `template` is well-formed as `{{key}}`
- Every placeholder key appearing in `template` exists in `values`
- Keys contain only letters, digits, and underscores
Examples
Input: ({"db_host": "example.com", "db_port": 5001}, "application is now connecting to {{db_host}}:{{db_port}}")
Expected Output: "application is now connecting to example.com:5001"
Explanation: Both placeholders are replaced with their mapped values.
Input: ({}, "plain text only")
Expected Output: "plain text only"
Explanation: Edge case: the template contains no placeholders, so it is returned unchanged.
Hints
- Scan the template from left to right. When you see `{{`, keep moving until you find the matching `}}` to extract the key.
- Build the answer using a list of string pieces and join at the end, instead of repeatedly concatenating strings.
Part 2: Replace Placeholders Across a Dictionary of Template Strings
You are given two dictionaries:
- `values`: maps placeholder keys to values
- `templates`: maps names to template strings
Each template string may contain placeholders in the form `{{key}}`. Return a new dictionary with the same keys as `templates`, where every template string has been rendered using `values`.
All placeholders are well-formed, every placeholder key exists in `values`, and keys contain only letters, digits, and underscores. Non-string replacement values should be converted to text before insertion.
Constraints
- 0 <= len(templates) <= 100000
- Let L be the total length of all strings in `templates`; L can be up to 200000
- Let K be the number of distinct keys in `values`
- Every placeholder in every template is well-formed as `{{key}}`
- Every placeholder key appearing in any template exists in `values`
- Keys contain only letters, digits, and underscores
Examples
Input: ({"db_host": "example.com", "db_port": 5001}, {"conn_msg": "application is now connecting to {{db_host}}:{{db_port}}", "short_msg": "{{db_host}}:{{db_port}}"})
Expected Output: {"conn_msg": "application is now connecting to example.com:5001", "short_msg": "example.com:5001"}
Explanation: Both template strings are rendered using the same `values` dictionary.
Input: ({"db_host": "example.com"}, {})
Expected Output: {}
Explanation: Edge case: if there are no templates, the result is an empty dictionary.
Hints
- Solve one template string at a time using the same parsing idea as in the single-template version.
- If some values are integers, convert each `values[key]` to a string once before processing all templates.