Evaluate division: answer ratio queries from known equations

You get equations of the form a / b = value between variables, each standing for an unknown positive number, and a large batch of queries c / d. Answer each query from the equations, or -1.0 if it cannot be determined. The batch is large and the function may be called often, so think about what to precompute so each query is cheap.

Interface

Unless you agree on a different interface with the interviewer, assume:

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

Example

equations = [["a", "b"], ["b", "c"], ["x", "y"]]
values    = [2.0, 3.0, 5.0]
queries   = [["a", "c"], ["c", "a"], ["b", "a"], ["a", "x"], ["a", "a"], ["e", "e"]]
->  [6.0, 0.16667, 0.5, -1.0, 1.0, -1.0]
    # a/c = 2 · 3; a and x are in different groups; e appears in no equation

Constraints

• Up to 10^5 equations and 10^5 queries; values between 0.001 and 1000.
• The equations never contradict each other.
• A query on a variable that appears in no equation returns -1.0, even e / e.
• Answers within a relative error of 1e-5 are accepted.

Clarifying questions

• Can equations contradict each other, and should that be detected?
• What is x / x when x is unknown?
• Are equations added over time, or all known up front?
• How big are the values, and is floating-point error a concern over long chains?

What a strong answer covers

• A graph with an edge a → b of weight v and b → a of weight 1 / v; a query is the product of weights along any path.
• Per-query BFS or DFS works but costs O(V + E) each, too slow for the batch.
• Precompute per connected component: pick a root, store each variable's ratio to the root, and answer c / d = ratio[c] / ratio[d] in O(1) when they share a root.
• Or weighted union-find with path compression, which also handles equations arriving one at a time.
• Total O((E + Q) · α(V)); edge cases for unknown variables, x / x, and separate groups.

Follow-ups

• Equations arrive while queries are being answered. Which approach still works?
• Detect when a new equation contradicts the existing ones.
• How do you limit floating-point error on long chains?