Coding - Evaluate Division

Problem Statement

Given a list of equations representing an equation system and a list of queries, return the result of each query. Equations of the form A / B = k are given, and for each query C / D, determine the result. If the result cannot be determined from the given equations, return -1.0.

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0, 3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

Output: [6.0, 0.5, -1.0, 1.0, -1.0]

Explanation:

• For the first query "a" / "c", we have "a" / "b" = 2 and "b" / "c" = 3. Therefore, "a" / "c" = 2 * 3 = 6.
• For the second query "b" / "a", we have "a" / "b" = 2. Therefore, "b" / "a" = 1 / 2 = 0.5.
• For the third query "a" / "e", we do not have enough information to determine the result, so we return -1.0.
• For the fourth query "a" / "a", we return 1.0 since any number divided by itself is 1.
• For the fifth query "x" / "x", we return -1.0 as we do not have information about "x".

Constraints:

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= values.length == equations.length <= 20
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• equations[i][0] and equations[i][1] are different letters.
• queries[i][0] and queries[i][1] are different letters.

Hints:

• Union Find (Union-Find or Disjoint Set Union) is useful to solve this problem.
• You can represent each equation as a graph where each variable is a node, and an edge between two nodes represents a division relationship.
• Use the Union Find data structure to connect nodes that are related through equations.
• Once connected, you can calculate the result of a query by finding the path between two nodes and multiplying/dividing the values along the path.