Evaluate Division
Learn this problem
InMobiFULLTIMEPHONE SCREENProblem statement
You are given variable pairs equations and positive real numbers values. For every index i, the pair equations[i] = [a, b] and value values[i] mean that a / b = values[i].
You are also given pairs queries. For each query [c, d], determine the value of c / d.
Return one answer for each query in the same order. Return -1.0 when the answer cannot be determined.
The equations are valid and mutually consistent. A variable that never appears in equations is undefined, even when it is queried against itself.
Function
calcEquation(equations: String[][], values: double[], queries: String[][]) → double[]Examples
Example 1
equations = [["a","b"],["b","c"]]values = [2.0,3.0]queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]return = [6.0,0.5,-1.0,1.0,-1.0]Following a / b = 2.0 and b / c = 3.0 gives a / c = 6.0. Reverse traversal gives b / a = 0.5. Variable e and variable x are undefined.
Example 2
equations = [["a","b"],["b","c"],["bc","cd"]]values = [1.5,2.5,5.0]queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]return = [3.75,0.4,5.0,0.2]The first two equations give a / c = 1.5 * 2.5 = 3.75 and c / b = 1 / 2.5 = 0.4. The last two answers use the listed bc / cd rate and its reciprocal.
Example 3
equations = [["a","b"]]values = [0.5]queries = [["a","b"],["b","a"],["a","c"],["x","y"]]return = [0.5,2.0,-1.0,-1.0]The direct rate is 0.5, its reciprocal is 2.0, and the other queries contain undefined variables.
Constraints
1 ≤ equations.length ≤ 20equations[i].length = 2values.length = equations.length0.0 < values[i] ≤ 20.01 ≤ queries.length ≤ 20queries[i].length = 2- Every variable name has length from
1through5and contains only lowercase English letters and digits. - The input contains no contradictory equations and no division by zero.