← All questions
Coding

Check for Contradictions in Equations

Asked atMicrosoftPhonePe
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The 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 here

javascript

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+
  1. 01Represent each variable in a weighted DSU with a ratio to its parent.
  2. 02When joining components, set the root ratio so Ai / Bi equals the supplied value.
  3. 03When already connected, compare the implied ratio with the new equation using tolerance.
  4. 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

Hiring now

PhonePe has 114 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

  • Software Engineer, Backend (3-5 years)

    Pune, Maharashtra, India

  • Software Engineer , Backend (5-7 years)

    Pune, Maharashtra, India

  • Software Engineer, App-Android

    Bengaluru, Karnataka, India

Or practice this question first

Next question