Satisfiability of Equality Equations

Satisfiability of Equality Equations

What is this problem about?

The Satisfiability of Equality Equations interview question gives you a list of equations where each equation is either "x==y" or "x!=y" for single-character variable names. Determine whether all equations can be simultaneously satisfied. This is a graph connectivity problem solvable with Union-Find.

Why is this asked in interviews?

This problem is asked at Microsoft, Meta, UiPath, and Google because it demonstrates a non-obvious application of Union-Find (Disjoint Set Union): use equality equations to build connected components, then verify that no inequality equation contradicts the established components. It models constraint satisfaction — directly applicable to type inference in compilers, logical consistency checking, and database constraint validation.

Algorithmic pattern used

The pattern is two-pass Union-Find. Pass 1: process all "==" equations and union the two variables (treat each letter as a node 0–25). Pass 2: process all "!=" equations and check that the two variables are NOT in the same component. If any "!=" equation has both variables in the same component (they are forced equal by "==" equations), return false. Otherwise, return true.

Example explanation

Equations: ["a==b", "b!=c", "c==a"]

Pass 1 (unions): a==b → union(a,b). c==a → union(c,a). Now {a,b,c} are in one component.

Pass 2 (check !=): b!=c → find(b) == find(c)? Yes (same component) → contradiction → return false.

Equations: ["a==b", "b!=c"]

• Union a and b. {a,b} one component, c separate.
• b!=c: find(b) ≠ find(c) → no contradiction → return true.

Common mistakes candidates make

• Processing != equations in the first pass — they cannot be used to establish unions.
• Not processing ALL == equations before checking ANY != — the order matters: build unions first, check inequalities second.
• Using a simple color/visited array instead of a proper DSU with path compression — the find() function must be correct.
• Treating multi-character variable names (the problem uses single characters 'a'–'z' only).

Interview preparation tip

For the Satisfiability of Equality Equations coding problem, the Union-Find graph interview pattern is the right tool. Two-pass processing — union all equalities first, then validate all inequalities — is the clean strategy. Google interviewers may ask "why not process them together?" — the answer is that equalities must propagate transitively through all nodes before inequalities can be checked. Practice implementing DSU with path compression for O(α(n)) amortized performance.