Evaluate Division — Weighted Graph BFS, DFS, and Union Find

Problem Statement#

You are given a list of equations of the form A / B = k, encoded as pairs of variable names with a corresponding value. You are also given a list of queries C / D and must compute each result using the known equations. If the answer cannot be determined, return -1.0 for that query. All values are positive and there are no contradictions.

Variables are strings; the equation graph may contain disconnected components, and a query may reference variables that never appeared in any equation, in which case the result is -1.0.

Why This Problem Matters#

Evaluate Division is a graph-modeling classic asked at Amazon, Google, Facebook, and Bloomberg. It tests whether a candidate can convert an algebraic relation into a weighted directed graph and traverse it correctly. The reduction is elegant once you see it: A / B = k becomes a directed edge from A to B with weight k and a reverse edge from B to A with weight 1 / k. Any product of weights along a path from C to D equals C / D.

The problem is also a great showcase for Union Find with weights, where each variable maintains a multiplicative offset to its representative. This data structure compresses queries to near-linear amortized time and is a frequent follow-up in senior engineering interviews.

The Core Insight#

Treat each variable as a graph node. For each equation A / B = k, add a directed edge A -> B with weight k and a directed edge B -> A with weight 1 / k. For a query C / D, the answer is the product of edge weights along any path from C to D, because telescoping cancels intermediate variables: C / X * X / Y * Y / D = C / D.

If either query variable is missing from the graph, return -1.0. If the variables are present but disconnected, BFS or DFS will fail to reach the destination and you return -1.0. If C equals D and C is in the graph, the answer is 1.0 by definition.

The Union Find variant maintains, for each variable, a parent pointer plus a weight representing the ratio of the variable to its parent. Union of A / B = k updates the weights so that the multiplicative path from any descendant to the root is consistent. A query becomes a find with weight aggregation and a comparison of roots.

Visual Dry Run (BFS/DFS trace)#

Take equations [[a, b], [b, c]] with values [2.0, 3.0] and the query a / c.

Build adjacency. Adjacency from a contains b with weight 2.0. Adjacency from b contains a with weight 0.5 and c with weight 3.0. Adjacency from c contains b with weight 1/3.

BFS from a for query a / c. Visited equals the set with a. Push (a, 1.0).

Pop (a, 1.0). a not equal to c. Neighbors of a: b with weight 2.0. Push (b, 2.0). Mark b visited.

Pop (b, 2.0). b not equal to c. Neighbors of b: a already visited; c with weight 3.0. Push (c, 6.0). Mark c visited.

Pop (c, 6.0). c equals destination. Return 6.0.

Now query a / e where e is not in any equation. Return -1.0 immediately because e is absent from adjacency.

Now query b / a. BFS from b. Push (b, 1.0). Pop (b, 1.0). Neighbors include a with weight 0.5. Push (a, 0.5). Pop (a, 0.5). Equals destination. Return 0.5.

Solution (Optimal)#

Python — Weighted BFS#

from collections import defaultdict, deque
 
class Solution:
    def calcEquation(self, equations, values, queries):
        adj = defaultdict(dict)
        for (a, b), v in zip(equations, values):
            adj[a][b] = v
            adj[b][a] = 1 / v
 
        def bfs(src, dst):
            if src not in adj or dst not in adj:
                return -1.0
            if src == dst:
                return 1.0
            visited = {src}
            q = deque([(src, 1.0)])
            while q:
                node, prod = q.popleft()
                if node == dst:
                    return prod
                for nb, w in adj[node].items():
                    if nb not in visited:
                        visited.add(nb)
                        q.append((nb, prod * w))
            return -1.0
 
        return [bfs(s, d) for s, d in queries]

JavaScript — DFS#

var calcEquation = function(equations, values, queries) {
    const adj = new Map();
    const addEdge = (a, b, v) => {
        if (!adj.has(a)) adj.set(a, new Map());
        adj.get(a).set(b, v);
    };
    equations.forEach(([a, b], i) => {
        addEdge(a, b, values[i]);
        addEdge(b, a, 1 / values[i]);
    });
    const dfs = (src, dst, visited) => {
        if (!adj.has(src) || !adj.has(dst)) return -1.0;
        if (src === dst) return 1.0;
        visited.add(src);
        for (const [nb, w] of adj.get(src)) {
            if (visited.has(nb)) continue;
            const sub = dfs(nb, dst, visited);
            if (sub !== -1.0) return sub * w;
        }
        return -1.0;
    };
    return queries.map(([s, d]) => dfs(s, d, new Set()));
};

Time complexity per query is O(V plus E) for BFS or DFS, giving O(Q times (V plus E)) total. Space is O(V plus E) for the adjacency map plus O(V) per traversal.

Common Mistakes#

Forgetting to add the reverse edge with reciprocal weight breaks queries that travel against the original direction. Returning 0 instead of -1.0 when variables are missing because of an absent default value tricks integer-loving habits in Python and JavaScript. Treating src equals dst for unknown variables as 1.0 is wrong; if the variable does not exist, the answer is -1.0. Mutating the adjacency map during traversal corrupts later queries; always use a fresh visited set per query. Caching results without keying on the entire path can yield stale ratios when equations are added later in a streaming variant.

Interview Tips#

Lead with the modeling step and write a tiny graph diagram so the interviewer sees the weighted edges. State the reverse-edge invariant explicitly. Mention all three approaches: BFS, DFS, and Union Find. Pick BFS for clarity but volunteer that Union Find with weights is the right answer when queries vastly outnumber equations. Discuss the variable-missing edge case and the same-source-as-destination edge case. If asked about cycles like A / B = 2, B / A = 0.5, note that the reverse-edge construction handles them automatically.

Follow-up Questions#

How would Union Find with weights solve this? Each node stores a parent and a weight representing the ratio to the parent. Union of A / B = k rewires roots so that the multiplicative path from any node to the root is preserved. Query C / D succeeds when C and D share a root; the answer is weight[C] / weight[D]. What if equations arrive online and queries can come at any time? Union Find is the right answer; each query is amortized near-constant. What if values can be zero? The reciprocal trick fails, so you must filter or special-case zero values. How do you detect contradictions? After unioning, if a future equation conflicts with the existing weight ratio, raise an error.

Key Takeaways#

• Evaluate Division becomes a weighted directed graph where edges are forward and reciprocal
• Path products telescope so C to D traversal yields C / D
• BFS, DFS, and weighted Union Find all solve the problem; Union Find is best for many queries
• Always check that both variables exist; otherwise return -1.0
• Handle src equals dst as 1.0 only when the variable exists in the graph
• Pattern transfers to currency conversion, unit conversion, and dependency-ratio analysis