String Meltdown: Parse and Evaluate Nested String Transformation Rules
Question Details
Problem
You are given a string and a sequence of transformation rules. Each rule is one of:
- REPLACE a b — replace all occurrences of a with b
- REVERSE — reverse the string
- TRUNCATE n — keep only the first n characters
- REPEAT n — repeat the string n times
- IF len>n THEN rule — apply rule only if current string length > n
Apply the rules in order and return the final string.
python
def apply_rules(s: str, rules: list[str]) -> str:
pass
Example
**Input**:
s = "hello"
rules = [
"REPLACE l r",
"REVERSE",
"IF len>4 THEN TRUNCATE 3",
"REPEAT 2"
]
Steps:
REPLACE l->r: "herro"
REVERSE: "orreh"
IF len(5)>4: TRUNCATE 3 -> "orr"
REPEAT 2: "orrorr"
**Output**: "orrorr"
Follow-ups
- How would you add nested conditionals (
IF ... THEN IF ... THEN ...)? - How do you detect rule sequences that could produce exponentially long strings (REPEAT inside a loop)?
- What parsing technique (recursive descent vs. regex) works best for this grammar?
Full Details
Problem
You are given a string and a sequence of transformation rules. Each rule is one of:
- REPLACE a b — replace all occurrences of a with b
- REVERSE — reverse the string
- TRUNCATE n — keep only the first n characters
- REPEAT n — repeat the string n times
- IF len>n THEN rule — apply rule only if current string length > n
Apply the rules in order and return the final string.
python
def apply_rules(s: str, rules: list[str]) -> str:
pass
Example
**Input**:
s = "hello"
rules = [
"REPLACE l r",
"REVERSE",
"IF len>4 THEN TRUNCATE 3",
"REPEAT 2"
]
Steps:
REPLACE l->r: "herro"
REVERSE: "orreh"
IF len(5)>4: TRUNCATE 3 -> "orr"
REPEAT 2: "orrorr"
**Output**: "orrorr"
Follow-ups
- How would you add nested conditionals (
IF ... THEN IF ... THEN ...)? - How do you detect rule sequences that could produce exponentially long strings (REPEAT inside a loop)?
- What parsing technique (recursive descent vs. regex) works best for this grammar?
About This Question
This is a reported interview question from a whatnot interview during the phone round.
It covers the following topics: Strings, Phone, Recursion, Coding, Onsite .