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.
Quick Answer: 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.
Input: ({'A':'x'}, '%A% %M%')
Expected Output: 'x %M%'
Explanation: Missing key preserved.
Hints
- Model object-style prompts as operation streams when needed.
- Handle empty and boundary cases before the main logic.