How should I practice Nested Substitutions with Cycle Detection?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Kikoff phone screen problems in FastPrep.

Is Nested Substitutions with Cycle Detection associated with Kikoff?

FastPrep tags this as a Kikoff phone screen coding practice problem when the problem catalog has that company and stage context.

Nested Substitutions with Cycle Detection

Kikoff● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given a dictionary replacements, where each row [key, value] maps a one-letter key to a value, and a string text. A placeholder %X% in the text stands for the value of key X.

Replace every placeholder in text with its value. A value can contain placeholders too, and those must be replaced as well, so keep going until no placeholder is left. Return the final string.

The dictionary can contain a cycle, such as A using %B% while B uses %A%. If replacing the placeholders of text needs a key while that same key is still being expanded, return "ERROR". A cycle among keys that the text never reaches does not matter.

The interviewer wanted the cycle found during the normal replacement work, not by a separate pass over the whole dictionary first.

Stages

Stage 1: values have no placeholders, so one pass of replacement is enough.
Stage 2: values can contain placeholders (nested replacement).
Stage 3: report a cycle with "ERROR".

The tests cover all three stages through the same function.

Function

applySubstitutions(replacements: String[][], text: String) → String

Examples

Example 1

replacements = [["A","bob"],["B","ana"]]text = "hi_%A%_and_%B%"return = "hi_bob_and_ana"

No value has a placeholder, so each placeholder in the text is replaced once: hi_bob_and_ana.

Example 2

replacements = [["A","x_%B%"],["B","%C%_y"],["C","z"]]text = "%A%_%B%"return = "x_z_y_z_y"

Expanding %A% needs %B%, which needs %C% = z. So %B% becomes z_y and %A% becomes x_z_y. The text becomes x_z_y_z_y.

Example 3

replacements = [["A","%B%"],["B","b_%A%"],["C","c"]]text = "go_%C%_%A%"return = "ERROR"

%C% is fine, but expanding %A% needs %B%, and %B% needs %A% again while it is still being expanded. That is a cycle, so the answer is ERROR.

Constraints

1 <= replacements.length <= 26
Each replacements[i] is [key, value]. Every key is one uppercase English letter, and keys are all different.
Each value has 1 to 20 characters.
1 <= text.length <= 100
text and every value are made of lowercase English letters, underscores _, and placeholders %X% where X is a key in replacements.
If the text reaches no cycle, its result has at most 2000 characters. Every key that reaches no cycle also expands to at most 2000 characters.