Evaluate Division
Asked at Ripple, Uber
Problem
Given a set of equations (a/b = k) and queries (c/d), return the result of each query or -1 if no path exists. This problem models equations as a weighted graph where division becomes path multiplication.
Asked At
| Company | Difficulty | |
|---|---|---|
| Ripple | Medium | View all Ripple questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Graph modeling: each variable is a node. For a/b = k, add edge a->b with weight k and edge b->a with weight 1/k. For queries like c/d, find a path from c to d and multiply the edge weights along the way.
Why this works: a/b = 3 and b/c = 2 implies a/c = 6. In the graph, path a->b->c has weight 3 * 2 = 6. The path product equals the answer.
Visual walkthrough for equations: a/b = 2, b/c = 3:
Graph: a --2--> b --3--> c
a <--0.5-- b <--0.33-- c
Query a/c: path a->b->c, weight = 2*3 = 6
Query c/a: path c->b->a, weight = 0.33*0.5 = 0.1667 = 1/6
Algorithm: build the graph from equations. For each query, run BFS or DFS from the source to the target, tracking the running product. If the target is reached, return the product. If not, return -1.
Complexity: build graph in O(e) where e is number of equations. Each query: O(v + e) for BFS/DFS. Total: O(e + q*(v+e)) where q is number of queries and v is number of unique variables.
Optimal Approach
Build an adjacency list graph where each node is a variable. For equation a/b = k, add a->b with weight k and b->a with weight 1/k. For each query c/d, run BFS from c to d, tracking the running product of edge weights. Return the product if d is found, else -1.
Walkthrough with equations a/b=2, b/c=3, d/e=4 and query a/c:
- Graph: {a: [(b,2)], b: [(a,0.5),(c,3)], c: [(b,0.33)], d: [(e,4)], e: [(d,0.25)]}
- BFS from a: visit a, product=1
- Visit b from a: product = 1*2 = 2
- Visit c from b: product = 2*3 = 6. Found c. Return 6.
Query a/e: BFS from a reaches {a,b,c}. e is unreachable. Return -1.
Time: O(e + q*(v+e)). Space: O(v+e) for the graph.
What Trips People Up in Real Interviews
Forgetting the reverse edge. If a/b = k, you must also add b/a = 1/k. Without it, you cannot traverse from b to a, and queries like b/a will incorrectly return -1.
Not handling disconnected components. If c and d are not in the same connected component, return -1. The BFS/DFS naturally handles this by returning -1 if the target is not found.
Floating point precision. Multiplying many weights can cause precision issues. For this problem, comparing with a small epsilon (like 1e-9) is acceptable. In interviews, mention the precision concern.
Confusing this with a different equation type. This is division equations (a/b = k), not addition equations (a+b = k). Addition would require a different graph model (weighted sums).
Not checking if both variables in a query exist in the graph. If either variable was never seen in any equation, return -1 immediately.
Solution Code
from collections import defaultdict, deque
def calcEquation(equations, values, queries):
graph = defaultdict(list)
for (a, b), val in zip(equations, values):
graph[a].append((b, val))
graph[b].append((a, 1.0 / val))
def bfs(start, end):
if start not in graph or end not in graph:
return -1.0
if start == end:
return 1.0
visited = {start}
queue = deque([(start, 1.0)])
while queue:
node, product = queue.popleft()
for neighbor, weight in graph[node]:
if neighbor == end:
return product * weight
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, product * weight))
return -1.0
return [bfs(s, e) for s, e in queries]Frequently Asked Questions
What is the Evaluate Division problem?
Given a set of equations (a/b = k) and queries (c/d), return the result of each query or -1 if no path exists. This problem models equations as a weighted graph where division becomes path multiplication.
How do you solve Evaluate Division?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Evaluate Division?
Evaluate Division is asked at Ripple, Uber. It is a medium difficulty problem.
What are common mistakes on Evaluate Division?
- Forgetting the reverse edge. If a/b = k, you must also add b/a = 1/k. Without it, you cannot traverse from b to a, and queries like b/a will incorrectly return -1.
- Not handling disconnected components. If c and d are not in the same connected component, return -1. The BFS/DFS naturally handles this by returning -1 if the target is not found.
- Floating point precision. Multiplying many weights can cause precision issues. For this problem, comparing with a small epsilon (like 1e-9) is acceptable. In interviews, mention the precision concern.
- Confusing this with a different equation type. This is division equations (a/b = k), not addition equations (a+b = k). Addition would require a different graph model (weighted sums).
- Not checking if both variables in a query exist in the graph. If either variable was never seen in any equation, return -1 immediately.