FastPrepEvaluate Formulas with Cycle Detection
Problem · Graph

Evaluate Formulas with Cycle Detection

Learn this problem
â—Ź MediumInstacart logoInstacartFULLTIMEONSITE INTERVIEW

Problem statement

You are given an ordered array formulas. Each string is a space-separated assignment of the form name = operand or name = operand + operand - operand .... An operand is either a signed 64-bit integer literal or the name of another formula. Every name is defined exactly once, and references may point forward or backward in the array.

Evaluate every formula. Return one string name=value per formula in the original input order. If the dependency graph contains any cycle, return only ["CYCLE"].

Addition and subtraction are evaluated from left to right. All inputs follow the grammar below, every referenced name is defined, and every intermediate and final value fits in a signed 64-bit integer.

Function

evaluateFormulas(formulas: String[]) → String[]

Examples

Example 1

formulas = ["a = 5","b = a + 3","c = b - a + 2"]return = ["a=5","b=8","c=5"]

a is 5, then b is 5 + 3 = 8, and c is 8 - 5 + 2 = 5. The result keeps assignment order.

Example 2

formulas = ["x = y + 1","y = z - 2","z = x + 4"]return = ["CYCLE"]

The dependencies form x -> y -> z -> x, so no value in that component can be evaluated.

Constraints

  • 1 <= formulas.length <= 100000.
  • Every formula contains an ASCII-letter name, a separated = token, and a valid alternating sequence of operands and separated + or - tokens; adjacent tokens have exactly one ASCII space.
  • Each formula name is unique, and every referenced name has exactly one formula.
  • The total number of space-separated tokens across all formulas is at most 500000.
  • Every integer literal, intermediate value, and result fits in a signed 64-bit integer.

More Instacart problems

drafts saved locally
public String[] evaluateFormulas(String[] formulas) {
    // Write your solution here.
}
formulas["a = 5","b = a + 3","c = b - a + 2"]
expected["a=5", "b=8", "c=5"]
checking account