Check for Contradictions in Equations

Check for Contradictions in Equations

What is this problem about?

The "Check for Contradictions in Equations interview question" involves validating a system of mathematical relationships. You are given equations like A / B = 2.0 and B / C = 3.0. Your task is to determine if a new equation (or the set itself) contradicts existing information. A contradiction occurs if, for example, the input says A / C = 5.0 when the previous equations implied A / C = 6.0.

Why is this asked in interviews?

Uber and Amazon use the "Check for Contradictions coding problem" to evaluate a candidate's ability to model relationships as a graph. It tests knowledge of Union Find (with weights) or Graph Traversal (DFS/BFS). It evaluations your ability to manage floating-point precision and perform path-based calculations in a directed, weighted graph.

Algorithmic pattern used

This problem follows the Union Find with Weights or Graph Reachability pattern.

1. Graph Construction: Treat each variable as a node and each equation X / Y = val as a directed edge from X to Y with weight val (and an edge from Y to X with weight 1/val).
2. Path Product: To find the ratio between two variables A and C, find any path between them and multiply the weights along that path.
3. Consistency Check:
   • If two variables are already connected in the Union Find structure, check if their existing ratio matches the new equation's value.
   • Use a small epsilon (e.g., $10^{-6}$) to account for floating-point errors during comparison.

Example explanation

Equations: [A/B=2, B/C=3, A/C=5]

1. A/B=2: Node A and B are linked.
2. B/C=3: Node B and C are linked. Implied A/C = (A/B) * (B/C) = 2 * 3 = 6.
3. A/C=5: New information! But we already calculated A/C = 6.
4. Result: Contradiction found.

Common mistakes candidates make

• Floating Point Equality: Comparing floats using == instead of checking if the difference is within a small range.
• Ignoring Disconnected Components: Failing to handle cases where equations involve groups of variables that have no relationship to each other.
• Path Search Inefficiency: Using a simple DFS for every check without memoization or a Union Find structure, leading to $O(N^2)$ complexity.

Interview preparation tip

This is a variation of the "Evaluate Division" problem. Practice using Union Find to store relative weights. In this "Graph interview pattern," the "root" of each component can store the ratio of each node relative to the root, making comparisons $O(1)$.