How should I practice Evaluate Division?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Apple phone screen problems in FastPrep.

Is Evaluate Division associated with Apple?

FastPrep tags this as a Apple phone screen coding practice problem when the problem catalog has that company and stage context.

Evaluate Division

Apple● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given equations between variables. equations[i] = [a, b] and values[i] together mean a / b = values[i]. Every value is a positive number.

For each query [c, d] in queries, return the value of c / d that follows from the equations. Return -1.0 when it cannot be worked out:

c or d does not appear in any equation. This includes a query like [x, x] when x is unknown.
No chain of equations links c to d.

A query [x, x] returns 1.0 when x appears in at least one equation. Return the answers in the same order as queries.

An answer is accepted when it is within 10^-5 * max(1, |expected|) of the expected value.

Interview Follow-up

Equations can form cycles, such as a / b, b / c and c / a. The interviewer asked how the solution deals with cycles. Here every cycle is consistent, so a search only has to make sure it never visits the same variable twice.

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]

From a / b = 2 and b / c = 3, a / c = 2 * 3 = 6. b / a is 1 / 2 = 0.5. e and x appear in no equation, so a / e and x / x are -1.0. a / a is 1.0 because a is known.

Example 2

equations = [["a","b"],["b","c"],["c","a"]]values = [2.0,4.0,0.125]queries = [["a","c"],["c","b"],["b","a"]]return = [8.0,0.25,0.5]

The three equations form a cycle, and it is consistent: 2 * 4 * 0.125 = 1. a / c = 2 * 4 = 8, c / b = 1 / 4 = 0.25 and b / a = 1 / 2 = 0.5. A search that does not remember the variables it has visited can go around this cycle forever.

Example 3

equations = [["x1","x2"],["y1","y2"]]values = [2.5,0.4]queries = [["x2","x1"],["x1","y1"],["y2","y1"],["y2","y2"]]return = [0.4,-1.0,2.5,1.0]

There are two separate groups, x1, x2 and y1, y2. x2 / x1 = 1 / 2.5 = 0.4 and y2 / y1 = 1 / 0.4 = 2.5. No equation links x1 to y1, so that query is -1.0. y2 / y2 is 1.0.

Constraints

1 <= equations.length <= 100
equations[i].length == 2 and queries[j].length == 2
values.length == equations.length
0.1 <= values[i] <= 20.0
1 <= queries.length <= 100
Every variable name has 1 to 5 characters, each a lowercase English letter or a digit.
The two variables in one equation are different.
The equations never contradict each other.