Skip to main content

399. Evaluate Division

mediumAsked at Uber

Given a/b = k pairs, evaluate query x/y. Uber asks this to test whether you model it as a weighted graph and BFS/DFS the path, or as Union-Find with ratio compression — both are clean answers.

By Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber L4/L5 onsite reports list this as a recurring graph medium.
  • Blind (2025-12)— Recurring in Uber backend interview reports.

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]. Determine the answer to queries[j] = [Cj, Dj] which represents the question Cj / Dj. Return -1.0 if the answer cannot be determined.

Constraints

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1.0 <= values[i] <= 20.0
  • 1 <= queries.length <= 20
  • All variables are lowercase English letter strings.

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/b = 2, b/c = 3 -> a/c = 6, b/a = 1/2. e and x unknown -> -1.

Example 2

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]

Approaches

1. Build weighted graph + DFS per query

Each equation a/b = v becomes two edges: a -> b (weight v) and b -> a (weight 1/v). For each query, DFS from src multiplying edge weights until you hit dst.

Time
O(Q * (V + E)) per query
Space
O(V + E)
function calcEquation(equations, values, queries) {
  const graph = new Map();
  function add(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];
    add(a, b, values[i]);
    add(b, a, 1 / values[i]);
  }
  function dfs(src, dst, visited) {
    if (!graph.has(src) || !graph.has(dst)) return -1;
    if (src === dst) return 1;
    visited.add(src);
    for (const [nbr, w] of graph.get(src)) {
      if (visited.has(nbr)) continue;
      const r = dfs(nbr, dst, visited);
      if (r !== -1) return r * w;
    }
    return -1;
  }
  return queries.map(([s, t]) => dfs(s, t, new Set()));
}

Tradeoff: Cleanest answer — directly models the problem as 'find a path, multiply weights'. Fine for the constraint size.

2. Weighted Union-Find (ratio to root)

Union-Find where each node tracks its ratio to its root. When unioning a/b = k, attach b's root to a's root with the matching ratio. Query: find(x), find(y); if same root, answer is ratio(x)/ratio(y).

Time
O((E + Q) * alpha(V))
Space
O(V)
function calcEquationUF(equations, values, queries) {
  const parent = new Map();
  const ratio = new Map();
  function find(x) {
    if (!parent.has(x)) { parent.set(x, x); ratio.set(x, 1); return x; }
    if (parent.get(x) !== x) {
      const root = find(parent.get(x));
      ratio.set(x, ratio.get(x) * ratio.get(parent.get(x)));
      parent.set(x, root);
    }
    return parent.get(x);
  }
  function union(a, b, v) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return;
    parent.set(ra, rb);
    ratio.set(ra, v * ratio.get(b) / ratio.get(a));
  }
  for (let i = 0; i < equations.length; i++) {
    const [a, b] = equations[i];
    find(a); find(b);
    union(a, b, values[i]);
  }
  return queries.map(([s, t]) => {
    if (!parent.has(s) || !parent.has(t)) return -1;
    const rs = find(s), rt = find(t);
    if (rs !== rt) return -1;
    return ratio.get(s) / ratio.get(t);
  });
}

Tradeoff: Asymptotically optimal for many queries on the same graph. More bookkeeping than the DFS version; the ratio-update during path compression is the tricky part.

Uber-specific tips

Uber's bar on this is choosing the right framing. Say out loud: 'Each equation defines edge weights — a/b = v means a->b has weight v, b->a has 1/v. The product along any path equals the implied ratio.' If you reach for Union-Find, explain the ratio-to-root invariant. Skipping the framing step and writing code is a flag.

Common mistakes

  • Forgetting the reverse edge with reciprocal weight (a/b = v implies b/a = 1/v).
  • Returning 1 for a/a when 'a' isn't in the graph at all — must return -1 if the variable is unknown.
  • In Union-Find, computing the ratio update wrong during path compression.

Follow-up questions

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

  • What if equations could be added online? (Union-Find handles incremental updates; graph DFS needs rebuild.)
  • What if values could be 0 or negative? (Reciprocal undefined for 0; sign handling for negatives.)
  • Shortest weighted path variant — replace product with min.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

DFS or Union-Find — which does Uber prefer?

Both pass with clear narration. DFS is faster to write under pressure. Union-Find scales better if you imagine millions of queries on a stable graph.

Why is the ratio multiplied along the path?

If a/b = x and b/c = y then a/c = (a/b) * (b/c) = x*y. The graph encodes ratios as edge weights and path products give the implied ratio.

Free learning resources

Curated free links for this problem.

More Uber coding interview questions

See all Uber problems →

Companies that also ask Evaluate Division