Skip to main content
Advanced

Evaluate Division

mediumAdvanced graphsGoogleAmazonUber

Problem statement

You get a list of equations like a / b = 2.0, given as pairs of variable names in equations and their results in values. Then you get queries, each asking for c / d. Answer every query using only the equations you were given.

If a query can't be worked out — because a variable never appeared in any equation, or because the two variables are not linked through any chain of equations — its answer is -1.0. The input never contradicts itself and never divides by zero.

Think of it as converting between units when you only know some conversion rates: if 1 node = 2 vCPUs and 1 vCPU = 3 threads, how many threads is 1 node? And you can't answer anything about a unit you've never seen.

Examples

Example 1

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

Explanation: a / c = (a / b) × (b / c) = 2 × 3 = 6, and b / a is the flip of 2, which is 0.5. e and x never appear in any equation, so those queries are -1, even x / x; a / a is 1 because a is known.

Example 2

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]

Output: [3.75000,0.40000,5.00000,0.20000]

Explanation: a / c = 1.5 × 2.5 = 3.75 and c / b = 1 / 2.5 = 0.4. bc and cd are just two more variable names, so bc / cd = 5 and its flip is 0.2.

Example 3

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]

Output: [0.50000,2.00000,-1.00000,-1.00000]

Explanation: a / b is given as 0.5, and b / a is its flip, 2. Neither c nor x and y appear in the equations, so the last two queries can't be answered.

Hints

Hint 1: Draw each variable as a node. For a / b = 2, draw a link from a to b with weight 2 — and what weight should the link from b back to a have?

Approach

Optimal: Weighted union-find

Intuition

Put variables that are linked by equations into groups. Inside each group, pick one variable as the root, and store, for every variable, its value divided by the root's value. Then any query inside a group is easy: c / d = (c / root) / (d / root). Variables in different groups can't be compared, so the answer is -1.

A union-find (disjoint-set) keeps these groups. Each variable stores a parent and a weight, where weight[x] = x / parent[x]. find(x) walks up to the root, multiplying the weights, so it returns the root and x / root; on the way it points x straight at the root (path compression) so later finds are instant. For an equation a / b = v, if a and b are in different groups, attach a's root under b's root with the weight that keeps the equation true.

Steps

  1. For each equation [a, b] with value v:
    • Add a and b if new (each is its own root with weight 1).
    • find(a) gives root ra and wa = a / ra; find(b) gives rb and wb = b / rb.
    • If ra != rb: set parent[ra] = rb and weight[ra] = v × wb / wa. (That is ra / rb, because a / b = v.)
  2. For each query [c, d]:
    • If either is unknown, the answer is -1.
    • find(c) gives (rc, wc) and find(d) gives (rd, wd). If rc != rd, the answer is -1; otherwise it is wc / wd.
  3. Return the answers.

Dry run

Example 1: equations a / b = 2, b / c = 3.

step action parent / weight after
a / b = 2 roots a, b differ → parent[a] = b, weight[a] = 2 × 1 / 1 = 2 a → b (2)
b / c = 3 roots b, c differ → parent[b] = c, weight[b] = 3 × 1 / 1 = 3 a → b (2), b → c (3)
query a / c find(a): a → b → c, weight 2 × 3 = 6; find(c): c, weight 1 answer 6 / 1 = 6
query b / a find(b) = (c, 3), find(a) = (c, 6) answer 3 / 6 = 0.5

The unknown e and x give -1, and a / a gives 6 / 6 = 1.

Complexity

Time O((E + Q)·α(V)) - Each equation does one union and each query does two finds. With path compression, a find is close to O(1) on average (α is the inverse Ackermann function, at most 4 in practice). So the total is almost linear in equations plus queries. This wins when there are many queries on the same equations.

Space O(V) - We store one parent and one weight per variable. No adjacency list or queue is needed. The output list is not counted.

from typing import Dict, List, Tuple


class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float],
                     queries: List[List[str]]) -> List[float]:
        parent: Dict[str, str] = {}
        weight: Dict[str, float] = {}  # weight[x] = x / parent[x]

        def find(x: str) -> Tuple[str, float]:
            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] = x
                    weight[x] = 1.0
            ra, wa = find(a)
            rb, wb = find(b)
            if ra != rb:
                parent[ra] = rb
                weight[ra] = v * wb / wa

        answers = []
        for c, d in queries:
            if c not in parent or d not in parent:
                answers.append(-1.0)
                continue
            rc, wc = find(c)
            rd, wd = find(d)
            answers.append(wc / wd if rc == rd else -1.0)
        return answers


def fmt(xs: List[float]) -> str:
    return "[" + ",".join(f"{x:.5f}" for x in xs) + "]"


if __name__ == "__main__":
    s = Solution()
    print(fmt(s.calcEquation([["a", "b"], ["b", "c"]], [2.0, 3.0],
                             [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]])))
    print(fmt(s.calcEquation([["a", "b"], ["b", "c"], ["bc", "cd"]], [1.5, 2.5, 5.0],
                             [["a", "c"], ["c", "b"], ["bc", "cd"], ["cd", "bc"]])))
    print(fmt(s.calcEquation([["a", "b"]], [0.5],
                             [["a", "b"], ["b", "a"], ["a", "c"], ["x", "y"]])))
RecapThe whole problem in a few lines, for the night before
  • Spot it: equations like a / b = 2.0, then queries like a / c that need a chain of them
  • Idea: build a graph where a to b has weight v and b to a has weight 1/v; for each query, DFS or BFS from the numerator to the denominator and multiply the weights on the path
  • Cost: O(Q x (V + E)) time, O(V + E) space
  • Trap: an unknown variable or no path gives -1.0, and x / x is 1.0 only if x appears in the equations

Interview follow-ups

  • New equations keep arriving between queries. Which approach fits better?

    Weighted union-find. Each new equation is one union in near O(1), and each query is two finds in near O(1). The BFS approach would have to search again for every query. Removing an equation, though, is hard for union-find, so if equations can also be deleted, keep the graph and use BFS.

  • The input might contain a contradiction (like a / b = 2 and b / a = 3). How do you detect it?

    With union-find, when an equation's two variables are already in the same group, compute their ratio from the stored weights and compare it with the given value. If they differ by more than a small tolerance (say 1e-9), report a contradiction. This catches bad conversion tables before they give silently wrong numbers.

  • Return the chain of conversions used, not just the result.

    In the BFS approach, record the parent of each variable when you first reach it. When you reach d, walk back through the parents to c and reverse the list. That gives something like node → vCPU → thread, which is useful for showing how a figure in a report was derived.

Frequently asked questions

If a / b = v, then b / a is the same fraction flipped over, which is 1 / v. Adding both directions means any query can be answered by walking the graph either way. Without the reverse link, a query like b / a would find no path and wrongly return -1.

The problem treats a variable that never appears in an equation as undefined, so nothing about it can be determined — not even dividing it by itself. That's why the code checks "is this variable known?" before "are both variables the same?". Swapping those two checks is the most common bug on this problem.

No. The problem promises there are no contradictions, so every path between two variables gives the same product. BFS, DFS or union-find can each find a different route and still get the same answer. Only floating-point rounding might differ in the last digits, which the 5-decimal answer hides.

Yes. Floyd-Warshall-style precomputation fills in ratio[i][j] for every pair of variables: for each middle variable k, if i / k and k / j are known, set i / j to their product. That setup costs O(V³), then every query is a table lookup. With 40 variables that's 64,000 steps — fine here, but it grows fast.

It is unit and rate conversion with only partial information: instance sizes to vCPUs, vCPUs to threads, one cloud's pricing units to another's, or currency rates for a cost report. Knowing when you can't convert (a unit you've never seen, or two unconnected groups) matters as much as the conversion itself.