Evaluate a Target Variable from Assignments with Plus, Minus, Cycles and Conflicts

You are given a list of assignment equations, each of which assigns a value to one variable, and the name of a target variable. Compute the value of the target variable. The task grows in three parts: first each right-hand side is a number or another variable, then right-hand sides can add and subtract terms, and finally inputs in which the target's value cannot be determined must return an empty string. The exact input format was not reported. The illustration below writes each equation as a string; agree on the real format with the interviewer. ```text Part 1 ["a = 5", "b = a", "c = b"] target "c" -> "5" Part 2 ["z = y - x + 1", "y = x + 4", "x = 3"] target "z" -> "5" Part 3 ["p = q + 1", "q = p - 1"] target "p" -> "" (cycle) ["r = s + 2"] target "r" -> "" (s is never defined) ["t = 4", "t = 7"] target "t" -> "" (conflicting values) ``` ### Constraints and Clarifications - Part 1: every right-hand side is either a number or a single variable name. - Part 2: a right-hand side can combine numbers and variables with `+` and `-`, and variables can refer to variables assigned anywhere in the list. - Part 3: when the target's value cannot be determined, return an empty string. The reported causes are a cycle of references, a variable that is never defined, and the same variable assigned conflicting values. - Because failure is reported as an empty string, the function returns its result as a string. ### Clarifying Questions - Are all numbers integers, can they be negative, and how should the result be written as a string? - Is each equation a single string such as `"y = x + 4"`, or already split into a name and tokens? Can the spacing vary? - Will there be many target queries against the same equations, so that work can be shared between queries? ### Part 1 — A number or another variable Implement `evaluate(equations, target)` for equations whose right-hand side is a number or one other variable. ```hint Follow the chain Each variable is either given directly or equal to exactly one other variable. Decide how to follow that chain to a number, and how to avoid following the same chain again the next time it is referenced. ``` #### What This Part Should Cover - Parsing the equations into a lookup from variable name to its right-hand side - Resolving the target by following references, with memoization - Time and space complexity in terms of the number of equations ### Part 2 — Addition and subtraction Right-hand sides can now be sums and differences of numbers and variables, such as `y - x + 1`, and a variable can depend on several others, defined earlier or later in the list. ```hint Many dependencies per variable A variable now depends on several others. Think of the equations as a graph and decide in which order values can be computed, and how the parser should handle signs and multi-digit numbers. ``` #### What This Part Should Cover - Tokenizing an expression into signed terms, including multi-digit numbers, names and missing spaces - Evaluating through the dependency graph so that each variable is computed once - Complexity in terms of the total number of terms ### Part 3 — When the value cannot be determined Detect the cases in which the target's value cannot be determined and return an empty string for them: a cycle of references, a reference to a variable that is never defined, and one variable assigned conflicting values. ```hint Finished versus in progress To detect a cycle, you need to tell apart a variable whose value is already known from one that is still being computed on the current path. Decide also whether a conflict is found while parsing or while evaluating. ``` #### Clarifying Questions for this Part - If a variable is assigned twice and both assignments produce the same value, is that a conflict? - Should a problem that the target never depends on, such as a cycle among unrelated variables, still make the answer empty? #### What This Part Should Cover - Cycle detection that does not misreport shared dependencies as cycles - Undefined references and conflicting assignments, with an explicit policy for each - Clean propagation of failure to the empty-string result, and caching of variables that failed ### What a Strong Answer Covers - Pins down the input format, number type, conflict policy and error scope before coding - A parser that handles signs, multi-digit numbers, spacing and malformed lines - Memoized evaluation that is linear in the size of the input - Correct handling of cycles, undefined variables and conflicts, each leading to the empty-string result - Part 1 code that extends to Parts 2 and 3 without a rewrite, with tests for each failure mode ### Follow-up Questions - Add multiplication and parentheses. What changes in the parser and in the evaluator? - Equations arrive one at a time, interleaved with queries. How do you avoid recomputing everything after each new equation? - A chain of 100,000 variables each refers to the previous one. What breaks in a recursive solution, and how do you fix it? - Instead of an empty string, report why the value cannot be determined and which variables are involved.