Practice/Amazon/Leetcode 399. Evaluate Division

Leetcode 399. Evaluate Division

CodingOptional

Problem

You are given a set of equations that define division relationships between variables, along with their numeric results. Each equation is represented as a pair of variables, and each result is a positive real number.

For example, if you're given the equation ["x", "y"] with value 2.5, this means that x / y = 2.5.

Your task is to answer a series of queries, where each query asks for the result of dividing one variable by another. If a query can be answered using the given equations (either directly or through a chain of relationships), return the numeric result. If a query cannot be answered (because one or both variables are undefined, or there's no connection between them), return -1.0.

Requirements

1. Build a data structure that captures the division relationships between variables
2. For each query, determine if the two variables are connected through the known relationships
3. If connected, compute the division result by following the chain of relationships
4. Handle edge cases: undefined variables, same variable division, disconnected components
5. Return an array of results in the same order as the queries

Constraints

• 1 ≤ equations.length ≤ 20
• equations[i].length == 2
• 1 ≤ equations[i][0].length, equations[i][1].length ≤ 5
• values.length == equations.length
• 0.0 < values[i] ≤ 20.0
• 1 ≤ queries.length ≤ 20
• queries[i].length == 2
• 1 ≤ queries[i][0].length, queries[i][1].length ≤ 5
• All variable names consist of lowercase English letters
• All division values are guaranteed to be positive

Examples

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:

• a/b = 2.0 and b/c = 3.0, so a/c = (a/b) * (b/c) = 6.0
• b/a is the reciprocal of a/b = 1/2.0 = 0.5
• Variable 'e' is not defined, so return -1.0
• a/a = 1.0 (any variable divided by itself)
• Variable 'x' is not defined, so return -1.0 `

Example 2:

Input: equations = [["a","b"],["c","d"]] values = [2.0, 4.0] queries = [["a","d"]] Output: [-1.0] Explanation: Variables a,b form one connected component and c,d form another. No path exists between 'a' and 'd', so return -1.0.