Data Structures19 sections · 729 units
Open in Course

Problem - Evaluate Division

Division as graph traversal

Given equations like a/b=2.0a/b = 2.0 and b/c=3.0b/c = 3.0, answer queries like a/c=?a/c = ? and a/a=?a/a = ?.

Return 1.0-1.0 for undefined queries (variables not in equations or not connected).

Example:

equations = [["a","b"],["b","c"]]
values = [2.0, 3.0]
queries = [["a","c"],["b","a"],["a","e"]]
Output: [6.0, 0.5, -1.0]

a/c=(a/b)(b/c)=23=6a/c = (a/b) \cdot (b/c) = 2 \cdot 3 = 6

You're implementing weighted Union-Find: edge weights are division ratios.

Constraints: up to 20 equations and 20 queries.