Check for Contradictions in Equations
Microsoft
PhonePeThe problem
You are given a 2D array of strings equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] means that Ai / Bi = values[i].
Determine if there exists a contradiction in the equations. Return true if there is a contradiction, or false otherwise.
Note :
- When checking if two numbers are equal, check that their absolute difference is less than 10-5.
- The testcases are generated such that there are no cases targeting precision, i.e. using double is enough to solve the problem.
Input : equations = [ ["a", "b"], ["c", "a"], ["a", "a"] ], values = [1.5, 2.0, 1.0] Output : false **Explanation : ** The given equations are: a / b = 1.5, c / a = 2.0, a / a = 1.0 There are no contradictions in the equations. One possible assignment to satisfy all equations is: a = 3, b = 2 and c = 6.
Input : equations = [ ["a", "b"], ["c", "a"], ["a", "a"] ], values = [1.5, 2.0, 2.0] Output : false **Explanation : ** The given equations are: a / b = 1.5, c / a = 2.0, a / a = 2.0 Since the third equation is a / a= 2.0, we get a contradiction as same value division is 1.0.
Input : equations = [ ["take", "u"], ["u", "for"], ["ward", "for"] ], values = [2.0, 0.5, 3.0]
- 1 <= equations.length <= 100
- equations[i].length == 2
- 1 <= Ai.length, Bi.length <= 5
- Ai, Bi consist of lowercase English letters.
- equations.length == values.length
- 0.0 < values[i] <= 10.0
- values[i] has a maximum of 2 decimal places.
cpp
class Solution {
public:
bool checkContradictions(vector<vector<string>>& equations, vector<double>& values) {
//your code goes here
}
};java
class Solution {
public boolean checkContradictions(List<List<String>> equations, List<Double> values) {
//your code goes here
}
}python
class Solution:
def checkContradictions(self, equations, values):
#your code goes herejavascript
class Solution {
checkContradictions(equations, values) {
//your code goes here
}
}csharp
public class Solution
{
public bool CheckContradictions(List<List<string>> equations, double[] values)
{
//your code goes here
}
}go
func checkContradictions(equations [][]string, values []float64) bool {
}Stuck? Show a way to structure it+
- 01Represent each variable in a weighted DSU with a ratio to its parent.
- 02When joining components, set the root ratio so Ai / Bi equals the supplied value.
- 03When already connected, compare the implied ratio with the new equation using tolerance.
- 04Update stored parent ratios during path compression.
Reference answer
Then expect these follow-ups
Derive the weight needed when attaching rootA under rootB.
Tests: algebra
How would a graph-based solution detect contradictions?
Tests: alternative model
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question