A kitchen app knows some conversion facts, like "1 gallon is 4 quarts". Fact i is facts[i] = [a, b] together with ratios[i], meaning one a equals ratios[i] of b. Every fact also works backwards: one b equals 1 / ratios[i] of a.
Implement convert_units(facts, ratios, queries) -> list[float]. For each query [x, y], answer how many y make one x, using any chain of facts. If there is no chain linking x to y, or either unit never appears in a fact, the answer is -1.0. A unit that appears in some fact converts to itself as 1.0.
facts = [["gallon", "quart"], ["quart", "pint"], ["cup", "tbsp"]]
ratios = [4.0, 2.0, 16.0]
queries = [["gallon", "pint"], ["pint", "gallon"], ["cup", "gallon"], ["tbsp", "tbsp"], ["mile", "mile"]]
convert_units(facts, ratios, queries)
# [8.0, 0.125, -1.0, 1.0, -1.0]
- The facts never contradict each other, and every ratio is positive.
- Up to 20,000 facts and 20,000 queries. Answers are compared with a relative tolerance of
1e-6. - Searching the facts afresh for every query is O(facts · queries), too slow here. Aim for about O(facts + queries).
Show hint
Within one linked group of units, pick one unit as a yardstick and work out once how many yardsticks each unit is worth. Then any query inside the group is a single division.