Katkat
Back

Design a Variable Store With Nested Reference Substitution and Cycle Detection

GoogleSoftware Engineer · Onsite
EasySoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Design a class that stores named variables and substitutes their values into text, where a stored value can reference other variables that must be expanded at any depth. It tests reference parsing, depth-first expansion with reuse of finished results, cycle detection with a clear error, and policies for undefined variables.

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.

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.

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.

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.

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

Hints

Hint 1

Raw or expanded: Consider what storing values already expanded would mean when a variable that others refer to is changed later.

Hint 2

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.

Hint 3

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.

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?