Evaluate Division
Problem statement
You get a list of known ratios. equations[i] = [a, b] together with values[i] means a / b = values[i], where a and b are variable names. Then you get queries, each a pair [c, d], and for each you must return c / d using only the known ratios. If the answer can't be determined, return -1.0 for that query.
Think of it as unit conversion: if you know gigabytes to megabytes and megabytes to kilobytes, you can answer gigabytes to kilobytes by chaining. A variable that appears in no equation is unknown, so even x / x is -1.0 for it. All given values are positive and the equations never contradict each other.
Examples
Example 1
Input: equations = [["gb","mb"],["mb","kb"]], values = [1000.0,1000.0], queries = [["gb","kb"],["kb","mb"],["gb","tb"],["mb","mb"]]
Output: [1000000.0, 0.001, -1.0, 1.0]
Explanation: gb/kb chains two ratios. kb/mb inverts one. tb never appears. mb/mb is 1 because mb is known.
Example 2
Input: equations = [["cpu","core"]], values = [2.0], queries = [["core","cpu"],["x","x"]]
Output: [0.5, -1.0]
Explanation: x is not in any equation, so even x / x is undetermined.
Hints
Approach
Weighted union-find. Store for each variable a parent and a weight, meaning variable / parent = weight. find(x) returns the root of x and x / root, compressing the path as it goes so later lookups are quick.
For an equation a / b = v, find both roots: a = wa · ra and b = wb · rb. If the roots differ, attach ra under rb with weight v · wb / wa, which keeps every stored ratio consistent. A query c / d is answered by finding both: if they share a root, the answer is wc / wd; otherwise -1.0.
O((E + Q) · α(V))Space O(V)def calc_equation(equations, values, queries): parent, weight = {}, {} # weight[x] = x / parent[x] def find(x): if parent[x] != x: root, w = find(parent[x]) parent[x] = root weight[x] *= w return parent[x], weight[x] for (a, b), v in zip(equations, values): for x in (a, b): if x not in parent: parent[x], weight[x] = x, 1.0 ra, wa = find(a) rb, wb = find(b) if ra != rb: parent[ra] = rb weight[ra] = v * wb / wa out = [] for c, d in queries: if c not in parent or d not in parent: out.append(-1.0) continue rc, wc = find(c) rd, wd = find(d) out.append(wc / wd if rc == rd else -1.0) return out print(calc_equation([["gb", "mb"], ["mb", "kb"]], [1000.0, 1000.0], [["gb", "kb"], ["kb", "mb"], ["gb", "tb"], ["mb", "mb"]]))print(calc_equation([["cpu", "core"]], [2.0], [["core", "cpu"], ["x", "x"]]))Follow-up questions
- What if equations can arrive between queries? (Union-find handles online updates naturally; the DFS version has to search again.)
- How would you detect contradictory input, such as a/b = 2 and b/a = 2?
Frequently asked questions
Chained conversions are everywhere in ops tooling: bytes to gibibytes, requests per second to requests per day, cores to vCPUs to instance counts. The real test is spotting that a table of ratios is a weighted graph, and then knowing weighted union-find, which shows up in the harder SWE-style loops.
The problem defines an answer as determinable only from the given equations. A variable that appears nowhere has no value at all, so even dividing it by itself isn't defined. For a known variable, x / x is 1.0 because the path from a node to itself is empty.
We know a = wa · ra, b = wb · rb and a = v · b. Substituting gives wa · ra = v · wb · rb, so ra / rb = v · wb / wa. That is the ratio stored when ra is attached under rb.