mediumGraphsPure DSA~30 min
Resolve Unit-Conversion Queries From Known Ratios
A service knows some pairwise conversion ratios between units (a/b). Answer queries asking for x/y by chaining known ratios; return -1 when no chain connects the two units.
Problem
You are given equations as pairs [a, b] with a parallel array values where values[i] = a / b. For each query [c, d], return c / d derived from the known ratios, or -1.0 if it cannot be determined (including when a unit never appears).
Input
A list equations of [a, b] string pairs, a values array, and a list queries of [c, d] string pairs.
Output
An array of doubles, one answer per query.
Constraints
- 1 <= equations.length, queries.length <= 100
- values[i] > 0
- Unit names are short non-empty strings.
Examples
Example 1
Input
equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["x","x"]]
Output
[6.0, 0.5, -1.0, -1.0]
a/c = 2*3 = 6; b/a = 1/2; e is unknown; x never appears so x/x is -1.
Example 2
Input
equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","a"]]
Output
[0.5, 2.0, 1.0]
Direct ratio, its inverse, and the trivial self-ratio.