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 ```python 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** ```text 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** ```text 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`.