399. Evaluate Division

Q: Why is graph + DFS the right framing?

Each equation establishes a known ratio between two variables. Combining ratios across a path multiplies them. The structure is identical to a weighted directed graph.

Q: When should I use union-find vs DFS?

DFS is fine when queries are few and graph is small. Union-find shines when queries dominate and you want amortized α(N) per query. Default to DFS for the whiteboard; mention UF as the optimization.

mediumAsked at Google

Given variable equations like a/b = 2.0 and b/c = 3.0, answer queries like a/c. Google asks this to test whether you can model the equations as a weighted graph and reach for DFS or union-find.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Google loops.

Glassdoor (2026-Q1)— Google L4 onsite reports cite this as the graph-modeling round.
Blind (2025-11)— Recurring Google interview problem.

Problem

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable. You are also given some queries, where queries[j] = [Cj, Dj] represents the j-th query where you must find the answer for Cj / Dj = ?. Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Constraints

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20

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.0,0.5,-1.0,1.0,-1.0]

Approaches

1. Build graph + DFS per query (optimal whiteboard)

Each equation is a directed edge with weight (forward) and 1/weight (backward). DFS from numerator to denominator, multiplying edge weights.

Time: O(Q * (V + E))
Space: O(V + E)

function calcEquation(equations, values, queries) {
  const graph = new Map();
  function addEdge(u, v, w) {
    if (!graph.has(u)) graph.set(u, new Map());
    graph.get(u).set(v, w);
  }
  for (let i = 0; i < equations.length; i++) {
    const [a, b] = equations[i];
    addEdge(a, b, values[i]);
    addEdge(b, a, 1 / values[i]);
  }
  function dfs(src, dst, seen) {
    if (!graph.has(src) || !graph.has(dst)) return -1.0;
    if (src === dst) return 1.0;
    seen.add(src);
    for (const [next, w] of graph.get(src)) {
      if (seen.has(next)) continue;
      const r = dfs(next, dst, seen);
      if (r !== -1.0) return w * r;
    }
    return -1.0;
  }
  return queries.map(([a, b]) => dfs(a, b, new Set()));
}

Tradeoff: Clean whiteboard solution. Re-runs DFS per query — fine because constraints are small.

2. Union-find with weighted edges (alternative)

Treat each variable as a node. Track parent + ratio-to-parent. Find with path compression also updates the ratio.

Time: O((E + Q) * α(N))
Space: O(V)

function calcEquationUF(equations, values, queries) {
  const parent = new Map();
  const ratio = new Map(); // ratio[x] = x / parent[x]
  function find(x) {
    if (parent.get(x) === x) return x;
    const root = find(parent.get(x));
    ratio.set(x, ratio.get(x) * ratio.get(parent.get(x)));
    parent.set(x, root);
    return root;
  }
  function union(a, b, val) {
    if (!parent.has(a)) { parent.set(a, a); ratio.set(a, 1); }
    if (!parent.has(b)) { parent.set(b, b); ratio.set(b, 1); }
    const ra = find(a), rb = find(b);
    if (ra !== rb) {
      parent.set(ra, rb);
      ratio.set(ra, val * ratio.get(b) / ratio.get(a));
    }
  }
  for (let i = 0; i < equations.length; i++) {
    union(equations[i][0], equations[i][1], values[i]);
  }
  return queries.map(([a, b]) => {
    if (!parent.has(a) || !parent.has(b)) return -1.0;
    if (find(a) !== find(b)) return -1.0;
    return ratio.get(a) / ratio.get(b);
  });
}

Tradeoff: Faster on large query counts (amortized near-linear). More fiddly to whiteboard. Reach for DFS first; mention this if interviewer asks for query optimization.

Google-specific tips

Google interviewers want you to recognize this as a weighted graph problem. State out loud: 'Each variable is a node. Each equation a/b = v gives me an edge a→b with weight v and b→a with weight 1/v. Now any query is a path traversal where I multiply edge weights.' That framing is the unlock.

Common mistakes

Forgetting to add the reverse edge with 1/value.
Returning -1.0 when both variables exist but no path connects them (correct — they're in separate components).
Returning -1.0 when src === dst for unknown variables (should be -1.0 only if the variable wasn't declared).

Follow-up questions

An interviewer at Google may pivot to one of these next:

What if equations could create contradictions (a/b = 2 AND a/b = 3)?
What if you needed the shortest path (fewest hops) instead of any path?
Stream of equations + queries — keep online state.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is graph + DFS the right framing?

Each equation establishes a known ratio between two variables. Combining ratios across a path multiplies them. The structure is identical to a weighted directed graph.

When should I use union-find vs DFS?

DFS is fine when queries are few and graph is small. Union-find shines when queries dominate and you want amortized α(N) per query. Default to DFS for the whiteboard; mention UF as the optimization.

Practice these live with InterviewChamp.AI

Drill Evaluate Division and other Google interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →