Conflicting Ratio Facts

Hard

Each name stands for an unknown positive number. You are given facts about their ratios: pairs[i] = [a, b] together with ratios[i] means that a / b = ratios[i]. Return True if the facts contradict each other, that is, no choice of numbers for the names satisfies all facts at once, and False otherwise. Two numbers count as equal when they differ by less than 10⁻⁵. The tests do not hinge on precision: an ordinary float is enough.

Example 1

pairs=[['tea', 'cup'], ['cup', 'jug'], ['tea', 'jug']], ratios=[0.5, 4, 2] → False

The first two facts give tea / jug = 0.5 · 4 = 2, which matches the third. For example tea = 2, cup = 4, jug = 1, so there is no conflict.

Example 2

pairs=[['x', 'y'], ['y', 'z'], ['x', 'z']], ratios=[3, 2, 5] → True

The first two facts give x / z = 6, but the third says x / z = 5. That is a conflict.

Example 3

pairs=[['ab', 'ab']], ratios=[1.5] → True

Constraints

1 ≤ len(pairs) = len(ratios) ≤ 100
Each name is 1 to 5 lowercase English letters
0 < ratios[i] ≤ 10, with at most four decimal places

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Union Find Graph Array

Similar problems

Which Machine to Cure Hard Which Machine to Unplug Hard Spread the News to Everyone Hard Ratio Chain Queries Medium Rooms Open from the Hall Medium

Input

pairs=[['tea', 'cup'], ['cup', 'jug'], ['tea', 'jug']], ratios=[0.5, 4, 2]

Expected

False

Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.