How do you expand nested placeholders in strings?
Company: Meta
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a dictionary of string templates. Keys are identifiers like `X`, `Y`, `Z`. A template may contain placeholders of the form `%KEY%`, which should be replaced by the fully-expanded value of `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%"`), return the fully expanded string.
Example:
- Input: `"%X% and %Z%"`
- Output: `"a and a and b"`
Assumptions/requirements to clarify in your solution:
- Templates can reference other templates (nested expansion).
- Decide how to handle missing keys and cyclic references (e.g., `A -> "%B%"`, `B -> "%A%"`).
- Provide time/space complexity for your approach.
Overview: This intermediate-level Coding & Algorithms problem for Data Scientist roles evaluates string parsing and manipulation skills along with dependency resolution techniques such as recursion or graph traversal, cycle detection, and memoization.
Expand %KEY% placeholders recursively. Missing keys stay unchanged; cycles become <CYCLE:key>.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ({'X':'a','Y':'b','Z':'%X% and %Y%'}, '%X% and %Z%')
Expected Output: 'a and a and b'
Explanation: Prompt example.
Input: ({'A':'%B%','B':'%A%'}, '%A%')
Expected Output: '<CYCLE:A>'
Explanation: Cycle marker.
Hints
- Model object-style prompts as operation streams when needed.
- Handle empty and boundary cases before the main logic.
Community answers
Answer by weian60333
public class Solution {
public String solution(Map templates, String input_string) {
Map memo = new HashMap<>();
// add visiting set to detect cycle
Set visiting = new HashSet<>();
return solve(input_string, templates, memo, visiting);
}
private String solve(String text, Map values, Map memo, Set visiting){
StringBuilder sb = new StringBuilder();
if (memo.containsKey(text)) return memo.get(text);
int i = 0;
while (i < text.length()){
char c = text.charAt(i);
// 1. c == %
if (c == '%'){
int j = text.indexOf('%', i + 1); // after i + 1
String key = text.substring(i+1, j); // [i+1, j-1]
if (!values.containsKey(key)) {
sb.append(text.substring(i,j+1));
}
else if (visiting.contains(key)){
sb.append(String.format("", key));
}
else if (memo.containsKey(key)){
sb.append(memo.get(key));
}
else {
visiting.add(key);
String rawValue = values.get(key);
String expandedText = solve(rawValue, values, memo, visiting);
// remove visiting
visiting.remove(key);
// update memo for the key
memo.put(key, expandedText);
sb.append(expandedText);
}
// move pointer
i = j + 1;
} else {
sb.append(c);
i++;
}
}
return sb.toString();
}
}