Answer a large batch of variable-ratio queries from division equations

You are given a list of equations between variables. Equation i is equations[i] = [a, b] together with a real number values[i], and it states that a / b = values[i]. Every variable is a string that stands for an unknown positive real number.

For each query [c, d] in queries, return the value of c / d if it can be determined from the equations, or -1.0 if it cannot.

In the interview, the base problem came first. The follow-up asked what changes when the function is called millions of times a day. This version models that follow-up: one call receives one set of equations and a large batch of queries.

Function Signature

def evaluate_ratios(equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:

Rules

• An equation a / b = v may be used in either direction: it also states that b / a = 1 / v.
• A ratio c / d can be determined when c and d are linked through a chain of one or more equations; its value is the product of the ratios along the chain. When several chains link the same two variables, they all give the same value, because the equations never contradict each other.
• If c or d does not appear in any equation, the answer is -1.0, even when c == d.
• If c == d and that variable appears in at least one equation, the answer is 1.0.
• If both variables appear in equations but no chain links them, the answer is -1.0.
• Return one answer per query, in the order of queries.
• Every determinable ratio is positive, so -1.0 never collides with a real answer. A determinable answer is accepted when its relative error from the exact ratio is at most 1e-5. The value -1.0 must be returned exactly.

Constraints

• 1 <= len(equations) == len(values) <= 100000
• 1 <= len(queries) <= 100000
• len(equations[i]) == 2 and len(queries[j]) == 2
• Every variable name has 1 to 5 characters, each a lowercase English letter or a digit.
• In each equation, a != b.
• 0.001 <= values[i] <= 1000.0
• The equations are consistent: no two chains between the same pair of variables imply different ratios.
• For any two variables linked by a chain, the ratio between them lies between 1e-9 and 1e9, so no product along a chain overflows or underflows.
• Query variables may be names that appear in no equation.

Examples

Example 1

Input:  equations = [["x", "y"], ["y", "z"]]
        values    = [4.0, 2.5]
        queries   = [["x", "z"], ["z", "x"], ["y", "x"], ["x", "w"], ["y", "y"], ["w", "w"]]
Output: [10.0, 0.1, 0.25, -1.0, 1.0, -1.0]

x / z = (x / y) * (y / z) = 4.0 * 2.5 = 10.0, and z / x is its reciprocal. y / x uses the first equation in reverse. w appears in no equation, so both queries that use it return -1.0, including w / w.

Example 2

Input:  equations = [["p", "q"], ["r", "s"], ["t", "q"]]
        values    = [0.5, 8.0, 0.25]
        queries   = [["p", "t"], ["t", "p"], ["p", "s"], ["s", "r"]]
Output: [2.0, 0.5, -1.0, 0.125]

p / t = (p / q) * (q / t) = 0.5 * 4.0 = 2.0, using the third equation in reverse. p and s both appear in equations, but no chain links the group {p, q, t} to the group {r, s}, so p / s is -1.0. s / r is the reciprocal of 8.0.