LeetCode: Evaluate Division

 This question is asked at Bloomberg, Uber, Amazon, and Microsoft.

You are given an Array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai/Bi = values[i]. Each Ai or Bi is a string that represents a single variable. 

You are also given some queries where queries[j] = [Cj, Dj] represents the jth query where you must find the Cj/Dj. Return the answer to all of the queries. If there isn't any answer that menas that we need to return 1.0. 

So let's have an example here. 

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

Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

Explanation: 

Given: a / b = 2.0, b / c = 3.0

queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?

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

Now, let's see how one would approach this problem and the corresponding solution. So, let's go over the graph solution here.

Let's say a/b = 2 and b/c = 3. so this means that

b/a = 1/2 and c/b = 1/3. This means that a/c = a/b * b/c which is equivalent to 2 * 3 = 6 and c/a = 1/6.

As a result, we can reformulate the equations with a graph data structure, where each variable can be represented as a node in the graph and the division relationship between the variables can be modelled as an edge between the node and its corresponding weight. 

So we can just transform this problem into a path searching problem and return the cumulative products as a result. This can be either done through BFS or DFS. 

So as a result, we take the list of input equations and build the corresponding grah. The evaluation is done by searching the path between 2 given variables, and we need to handle if the node doesn't exist in the graph or if th eorigina and destination are in the same node. So far, since we're in Java, I start thinking about using a HashMap to represent a dictionary. The time complexity of this is O(MN) to traverse the entire graph and the total evaluation of the queries. 

class Solution {

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

    //build the graph from the equation. 

        for(int i = 0; i < equations.size(); i++) {

            List<String> equation = equations.get(i); 

            String dividend = equation.get(0), divisor = equation.get(1); 

            double quotient = values(i);

            //add the dividend and the divisor 

            if(!graph.containsKey(dividend) {graph.put(dividend, new HashMap<String, Double>()};

            if(!graph.containsKey(divisor) {graph.put(dividend, new HashMap<String, Double>()};

            //put dividend/divisor in the graph. 

            graph.get(dividend).put(divisor, quotient);

            graph.get(divisor).put(dividend, 1/quotient); 

       }

        //evaluate each query through backtracking and verifying there exists a path from dividend to divisor 

        double[] results = new double[queries.size()]; 

        for(int i = 0; i < queries.size(); i++) {

            List<String> query = queries.get(i); 

            String dividend = query.get(0), divisor = query.get(1);

            if(!graph.containsKey(dividend) || !graph.containsKey(divisor)) results[i] = -1.0;

            else if (dividend == divisor) results[i] = 1.0; 

            else {

                HashSet<String> visited = new HashSet<>(); 

                results[i] = backtrackEvaluate(graph, dividend, divisor, 1, visited); 

            }

        }

        return results; 

    }

    private double backtrackEvaluate(HashMap<String, HashMap<String, Double>> graph, String currNode, String targetNode, double accProduct, Set<String> visited) {

    //mark visit

    visited.add(currNode); 

    double ret = -1.0; 

    Map<String, Double> neighbors = graph.get(currNode);

    if(neighbors.containsKey(targetNode)) ret = accProduct * neighbors.get(targetNode);

    else {

        for(Map.Entry<String, Double> pair: neighbors.entrySet()) {

            String nextNode = pair.getKey(); 

            if(visited.contains(nextNode)) continue; 

            ret = backtrackEvaluate(graph, nextNode, targetNode, accProduct * pair.getValue(), visited); 

               if(ret != -1.0) break;

        }

    }

    //unmark node

    visited.remove(currNode); 

    return ret; 

}

}