FastPrepCheck Inequality Constraint Consistency

Check Inequality Constraint Consistency

Google logoGoogle● MediumNEW GRADPHONE SCREEN
Learn

Problem statement

You are given comparisons between named variables. Each string has the form left<right, left<=right, left>right, or left>=right. Variable names contain lowercase English letters.

Decide whether real values can be assigned to all variables so that every comparison is true.

Whitespace does not occur. Repeated comparisons are allowed.

Function

areInequalitiesConsistent(relations: String[]) → boolean

Examples

Example 1

relations = ["a>b","b>c","d<e"]return = true

For example, choose a=2,b=1,c=0,d=0,e=1.

Example 2

relations = ["a>b","b>c","c>a"]return = false

The strict cycle would require a>b>c>a.

Example 3

relations = ["a<=b","b<=a"]return = true

Both relations hold when a=b.

Constraints

  • 0 <= relations.length <= 200000.
  • Each variable name has length in [1,20] and contains only lowercase English letters.
  • Every relation uses exactly one of <, <=, >, or >=.

More Google problems

See Google hiring insights
public boolean areInequalitiesConsistent(String[] relations) {
    // Write your code here.
}
relations["a>b","b>c","d<e"]
expectedtrue
Checking account…