Evaluate Division

Evaluate Division

What is this problem about?

The Evaluate Division interview question presents a set of variables and their relationships in the form of equations (e.g., a / b = 2.0). Based on these equations, you are given multiple queries (e.g., a / c = ?) and must calculate the result if it can be determined. If a path of relationships exists between two variables, you can compute the result by multiplying the weights along that path. If no path exists, or if a variable is unknown, you return -1.0.

Why is this asked in interviews?

Companies like Uber, Meta, and Amazon ask the Evaluate Division coding problem to see if you can model abstract relationships as a graph. It tests your proficiency with Graph traversal and your ability to handle numerical precision. It's a "Medium" problem that effectively evaluates if you can identify that a division relationship is just a weighted edge in a directed graph where a / b = k means a -> b with weight k and b -> a with weight 1/k.

Algorithmic pattern used

This problem is a classic Graph and Shortest Path problem.

1. Adjacency List: Build a graph where nodes are variables and edges represent division results.
2. Traversal (DFS or BFS): For each query x / y, perform a search starting from x to see if y is reachable. While traversing, multiply the weights of the edges.
3. Union Find (Alternative): You can also use a Disjoint Set Union (DSU) where each set stores the multiplier relative to the root of the set.

Example explanation

Equations: a / b = 2.0, b / c = 3.0. Graph:

• a --(2.0)--> b, b --(0.5)--> a
• b --(3.0)--> c, c --(0.33)--> b Query: a / c?

1. Start at a.
2. Move to b (weight 2.0).
3. From b, move to c (weight 3.0).
4. Total path weight: 2.0 * 3.0 = 6.0. Result: 6.0.

Common mistakes candidates make

• Ignoring Cycles: While division relationships usually don't have conflicting cycles in these problems, not using a "visited" set can lead to infinite recursion.
• Handling Unknown Variables: Forgetting to return -1.0 if a variable in the query was never seen in the equations.
• Precision Issues: Not using floating-point types for calculation.

Interview preparation tip

Whenever you see a problem involving "chaining" ratios or relationships, immediately think of a Weighted Directed Graph. The search for a ratio between two items is simply finding a path between two nodes and aggregating the weights.