Design a Variable Store With Nested Reference Substitution and Cycle Detection

Design and implement a class that works as a small store of named variables and performs string substitution with them. The class must: - store variables: add or update a variable's value, read it, and remove it; - substitute: given a text, replace every variable reference in it with that variable's value. A variable's value may itself contain references to other variables, so substitution must keep expanding nested references at any depth. Those references can also form a cycle, for example a variable whose value refers, directly or through other variables, back to itself. The class must handle that case instead of looping forever. The reference syntax was not given. The examples below assume a reference is written as `${name}`; confirm the syntax with your interviewer. ```text set("host", "db.internal") set("port", "5432") set("url", "${host}:${port}/app") substitute("connect to ${url}") returns "connect to db.internal:5432/app" set("a", "x${b}") set("b", "${a}") substitute("${a}") must not loop forever ``` ### Constraints and Clarifications - Assume variable names consist of letters, digits and underscores and do not start with a digit. - Variables can be added, changed or removed between substitutions. - Not given: what to do with a reference to an undefined variable, and how a cycle should be reported. Clarify them, or state your choice. ### Clarifying Questions - Should a reference to an undefined variable be left as it is, replaced with an empty string, or reported as an error? - When the text reaches a cycle, should the whole substitution fail, or only the references involved? - Can a reference appear inside another reference's name, such as `${user_${env}}`, or only inside stored values? - Is there an escape for a literal `${` that must not be substituted? - Will substitutions be far more frequent than updates? ### Part 1 — Storage Define the class's storage interface and decide how values are kept. ```hint Raw or expanded Consider what storing values already expanded would mean when a variable that others refer to is changed later. ``` #### What This Part Should Cover - The public methods, and their behavior for invalid names and missing variables - Storing raw values versus expanded values, and the consequences for updates - How the storage could be backed by a database instead of memory ### Part 2 — Substitution with nested references Implement `substitute(text)` so that it expands nested references at any depth. ```hint Same problem, smaller input Expanding one stored value is the same task as expanding the input text. Think about what must be known before a value can be written out, and how to avoid doing that work twice. ``` #### What This Part Should Cover - Correct scanning of references, rather than repeated global find-and-replace - Depth-first expansion that reuses variables already expanded in the same call - Time and space complexity, including how large the output can grow ### Part 3 — Cycles Make `substitute` detect cycles and report them clearly, without rejecting valid inputs. ```hint Not every repeat is a loop Reaching the same variable twice does not always mean there is a cycle. Work out what extra state tells a shared dependency apart from a real loop. ``` #### What This Part Should Cover - Detection of direct, indirect and self-referencing cycles - Not mistaking a variable that is referenced twice (a shared dependency) for a cycle - The error reported, including which variables form the cycle - Test cases covering cycles and near-cycles ### What a Strong Answer Covers - Clarifies the reference syntax and the policies for undefined variables and cycles before coding - A clean class interface with raw storage and on-demand expansion, and a justified choice between the two storage options - A single-pass scanner with depth-first expansion and memoization within a call - Cycle detection that distinguishes variables in progress from finished ones and reports the cycle path - Complexity analysis, including output blow-up and recursion depth, plus a focused set of tests ### Follow-up Questions - Values change rarely and substitutions are very frequent. How would you cache expanded values, and what must an update invalidate? - How would you support references nested inside a reference name, such as `${user_${env}}`? - Detect cycles when a variable is set instead of when text is substituted. What does that cost, and what does it prevent? - A chain of references is thousands of variables deep. What breaks in a recursive implementation, and how do you fix it?