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.