Evaluate Division Coding Problem Solution

Source: Dev.to

Evaluate Division Overview

Evaluate Division is a graph problem disguised as algebra. You are given a list of equations such as:

a / b = 2.0
b / c = 3.0

and queries like:

a / c = ?
c / a = ?
x / x = ?

Your task is to compute each query’s result using the relationships implied by the equations. If a query cannot be answered with the given information, return -1.0.

The key insight is to treat variables as nodes in a weighted graph. Each equation provides a direct conversion rate between two variables, turning the problem into finding a path between nodes and multiplying the edge weights along that path.

What Makes It Tricky

• Unordered equations – The equations may appear in any order, requiring multiple hops to answer a query.
• Disconnected components – Some variables may never be connected to others.
• Missing variables – Queries can involve variables that never appear in any equation; these must immediately return -1.0.

Solution Idea Expected by Interviewers

Model the Equations as a Weighted Graph

• Treat each variable as a node.
• For an equation u / v = k, add two directed edges:
  • u → v with weight k
  • v → u with weight 1 / k

The reciprocal edge is essential because division relationships are reversible.

Answer Queries Using Graph Traversal

For each query x / y:

1. Check existence – If either x or y is absent from the graph, return -1.0.
2. Search for a path – Perform a depth‑first search (DFS) or breadth‑first search (BFS) from x to y.
   • Carry a running product initialized to 1.0.
   • Multiply the product by the edge weight each time you traverse an edge.
   • When y is reached, the running product is the answer.
3. Avoid cycles – Maintain a visited set for the current search to prevent infinite loops.

Special Cases

• Self‑division (x / x)
  • If x exists in the graph, the result is 1.0.
  • If x does not exist, return -1.0.

Why This Approach Is Efficient in Interviews

• Graph construction – Linear time O(E) where E is the number of equations.
• Query processing – Each query costs O(V + E) in the worst case for the connected component explored, which is acceptable for typical interview constraints.
• Scalability – For many queries, you can cache results or use a weighted union‑find (disjoint set) structure to reduce repeated searches, though most interviewers are satisfied with the straightforward traversal solution.

Common Mistakes to Avoid

• Omitting the reciprocal edge – This breaks reverse‑direction queries.
• Not using a per‑query visited set – Can cause infinite recursion or redundant work on cyclic graphs.
• Returning 1.0 for x / x when x is unknown – The correct response is -1.0 in that case.

Related Coding Problem Solutions

• Maximum Sum Circular Subarray
• Coin Change II