Evaluate Division

Evaluate Division is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.

Problem statement

You are given symbolic division relationships in equations. Each two-element entry [a, b] states that a / b equals the corresponding number in values at the same index. Every variable is represented by a string, and variables may be connected through several equations.

For every two-element entry [x, y] in queries, determine the value of x / y using the supplied relationships. A variable divided by itself has value 1.0 when that variable is known. If either variable is absent from the equations, or no chain of relationships connects them, the answer is -1.0.

Return a list of floating-point answers in the same order as queries. The input contains no contradictory relationships and no division by zero. Answers whose absolute or relative error is at most 1e-5 are accepted.

Example 1:

Input: equations = [["p","q"],["q","r"]], values = [4.0,0.5], queries = [["p","r"],["r","p"],["p","p"],["p","x"]] Output: [2,0.5,1,-1] Explanation: The path from p to r multiplies the ratios 4.0 and 0.5, while reversing the path gives 0.5. p is known, but x is not present.

Example 2:

Input: equations = [["red","blue"],["sun","moon"]], values = [2.5,7.0], queries = [["blue","red"],["red","moon"],["sun","moon"],["green","green"]] Output: [0.4,-1,7,-1] Explanation: Reversing red / blue gives 1 / 2.5. The red-blue and sun-moon groups are disconnected, and green never appears in an equation.

Example 3:

Input: equations = [["a","b"],["b","c"],["c","d"]], values = [3.0,2.0,0.25], queries = [["a","d"],["d","a"],["b","d"],["d","d"]] Output: [1.5,0.6666666666666666,0.5,1] Explanation: a / d is 3.0 × 2.0 × 0.25 = 1.5, and reversing the route takes its reciprocal. The query b / d uses 2.0 × 0.25.

Constraints:

- 1 <= equations.length <= 20 - equations.length == values.length - 1 <= queries.length <= 20 - Each entry in equations and queries has exactly 2 strings - Variable names contain one or more lowercase English letters - 0 < values[i] and no division by zero is required - The input contains no contradictory relationships

Topics and companies

Topics: Graph, Depth-First Search, Breadth-First Search, Hash Table.

How to practise Evaluate Division on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(E + Q(V + E)), where E is the number of equations, V is the number of variables, and Q is the number of queries. time and O(V + E) for the graph, visited sets, and recursion stack. space.

Open Evaluate Division in the code editor, or read the Evaluate Division editorial for a worked solution with its approach and complexity analysis.

Where Evaluate Division sits in the DSA pattern sheet

Problems related to Evaluate Division

Other problems that use the same Graph DFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.