Home » Technical Interview Questions » Algorithm Interview Questions » Evaluate Division

Evaluate Division


Reading Time - 11 mins

In evaluate division problem we have given some equations, in the form, A/B = k, where A and B are strings and k is a real number. Answer some queries, if the answer does not exist return -1.

Example

Input:
equations: a/b = 2.0 and b/c = 3.0
queries: a/c = ?, b/a = ?, a/e = ?, a/a = ?, x/x = ?
Output:
{6.0, 0.5, -1.0, 1.0, -1.0}

Equations are represented as list of list of strings, values are represented as array of double and queries are also represented as list_of_list_of strings, that is, for above example, input is represented as

equations = {{“a”, “b”}, {“a”, “c”}}
values = {2.0, 3.0}
queries = {{“a”, “c”}, {“b”, “a”}, {“a”, “e”}, {“a”, “a”}, {“x”, “x”}}

Algorithm for Evaluate Division

The above problem represents a graph.
Variables in the equations are nodes and the value of equations is the weight of edges.
An edge from vertex x to vertex y has a weight equals to x / y.
The graph for the above example is,

Evaluate Division

Answer to a query is found by doing a DFS search in the graph.

  1. Build the graph as mentioned above.
  2. Each query is of the form of source and destination, we have to start from the source and reach the destination.
  3. For every query, start from the source, if the source does not exists, return -1.
  4. If the source has a direct edge to the required destination, return the value of the edge.
  5. Else mark source as visited and recur for all the neighbors of source that are not visited yet, neighbor becomes the source and destination remains the same, if the answer of any of the neighbor is not -1, return edge weight from source to the neighbor plus answer of neighbor.
READ  KMP Algorithm

JAVA Code for Evaluate Division

import java.util.*;

public class EvaluateDivision {
    private static double[] calcEquation(List<List<String>> equations, double[] values,
                                         List<List<String>> queries) {
        // Build the graph
        HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String from = equations.get(i).get(0);
            String to = equations.get(i).get(1);

            // From source to destination the weight of edge is values[i]
            if (graph.containsKey(from)) {
                graph.get(from).put(to, values[i]);
            } else {
                HashMap<String, Double> map = new HashMap<>();
                map.put(to, values[i]);
                graph.put(from, map);
            }

            // From destination to source the weight of edge is (1 / values[i])
            if (graph.containsKey(to)) {
                graph.get(to).put(from, 1 / values[i]);
            } else {
                HashMap<String, Double> map = new HashMap<>();
                map.put(from, 1 / values[i]);
                graph.put(to, map);
            }
        }

        // Solve queries
        double ans[] = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            // Visited set
            HashSet<String> visited = new HashSet<>();
            ans[i] = dfs(graph, queries.get(i).get(0), queries.get(i).get(1), visited);
        }

        return ans;
    }

    private static double dfs(HashMap<String, HashMap<String, Double>> graph, String from, String to,
                              HashSet<String> visited) {
        // Source not found
        if (!graph.containsKey(from)) {
            return -1.0;
        }

        // Direct edge
        if (graph.get(from).containsKey(to)) {
            return graph.get(from).get(to);
        }

        // Mark source as visited
        visited.add(from);

        for (Map.Entry<String, Double> entry : graph.get(from).entrySet()) {
            if (!visited.contains(entry.getKey())) {
                // For all unvisited neighbors of source do dfs
                // neighbor becomes the source and destination remains same
                double ans = dfs(graph, entry.getKey(), to, visited);
                if (ans != -1.0) {
                    // If ans of any neighbor is not -1, return (edge weight * ans of neighbor)
                    return (ans * entry.getValue());
                }
            }
        }

        // All neighbors returned -1, return -1
        return -1.0;
    }

    public static void main(String[] args) {
        // Example
        List<List<String>> equations = new ArrayList<>();
        ArrayList<String> eq1 = new ArrayList<>();
        eq1.add("a");
        eq1.add("b");
        equations.add(eq1);
        ArrayList<String> eq2 = new ArrayList<>();
        eq2.add("b");
        eq2.add("c");
        equations.add(eq2);

        double values[] = new double[2];
        values[0] = 2.0;
        values[1] = 3.0;

        List<List<String>> queries = new ArrayList<>();
        ArrayList<String> q1 = new ArrayList<>();
        q1.add("a");
        q1.add("c");
        queries.add(q1);
        ArrayList<String> q2 = new ArrayList<>();
        q2.add("b");
        q2.add("a");
        queries.add(q2);
        ArrayList<String> q3 = new ArrayList<>();
        q3.add("a");
        q3.add("e");
        queries.add(q3);
        ArrayList<String> q4 = new ArrayList<>();
        q4.add("a");
        q4.add("a");
        queries.add(q4);
        ArrayList<String> q5 = new ArrayList<>();
        q5.add("x");
        q5.add("x");
        queries.add(q5);

        double ans[] = calcEquation(equations, values, queries);
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}

C++ Code for Evaluate Division

#include<bits/stdc++.h>
using namespace std;

double dfs(unordered_map<string, unordered_map<string, double>> &graph, 
    string from, string to, unordered_set<string> &visited) {
    // Source not found
    if (graph.find(from) == graph.end()) {
        return -1.0;
    }
    
    // Direct edge
    if (graph[from].find(to) != graph[from].end()) {
        return graph[from][to];
    }
    
    // Mark source as visited
    visited.insert(from);
    
    for (auto i : graph[from]) {
        if (visited.find(i.first) == visited.end()) {
            // For all unvisited neighbors of source do dfs
            double ans = dfs(graph, i.first, to, visited);
            if (ans != -1.0) {
                // If ans of any neighbor is not -1, return (edge weight * ans of neighbor)
                return (ans * i.second);
            }
        }
    }
    
    // All neighbors returned -1, return -1
    return -1.0;
}

vector<double> calcEquation(vector<vector<string>>& equations, 
                vector<double>& values, 
                vector<vector<string>>& queries) {
  // Build the graph
  unordered_map<string, unordered_map<string, double>> graph;
  for (int i = 0; i < equations.size(); i++) {
      string from = equations[i][0];
      string to = equations[i][1];
      
      // From source to destination the weight of edge is values[i]
      if (graph.find(from) == graph.end()) {
          unordered_map<std::string, double> m;
          m.insert(make_pair(to, values[i]));
          graph.insert(make_pair(from, m));
      } else {
          graph[from].insert(make_pair(to, values[i]));
      }
      
      // From destination to source the weight of edge is (1 / values[i])
      if (graph.find(to) == graph.end()) {
          unordered_map<std::string, double> m;
          m.insert(make_pair(from, 1 / values[i]));
          graph.insert(make_pair(to, m));
      } else {
          graph[to].insert(make_pair(from, 1 / values[i]));
      }
  }
  
  // Solve queries
  vector<double> ans;
  for (int i = 0; i < queries.size(); i++) {
      unordered_set<string> visited;
      ans.push_back(dfs(graph, queries[i][0], queries[i][1], visited));
  }
  return ans;
}

int main() {
    // Example
    vector<vector<string>> equations;
    vector<string> eq1;
    eq1.push_back("a");
    eq1.push_back("b");
    equations.push_back(eq1);
    vector<string> eq2;
    eq2.push_back("b");
    eq2.push_back("c");
    equations.push_back(eq2);
    
    vector<double> values;
    values.push_back(2.0);
    values.push_back(3.0);
    
    vector<vector<string>> queries;
    vector<string> q1;
    q1.push_back("a");
    q1.push_back("c");
    queries.push_back(q1);
    vector<string> q2;
    q2.push_back("b");
    q2.push_back("a");
    queries.push_back(q2);
    vector<string> q3;
    q3.push_back("a");
    q3.push_back("e");
    queries.push_back(q3);
    vector<string> q4;
    q4.push_back("a");
    q4.push_back("a");
    queries.push_back(q4);
    vector<string> q5;
    q5.push_back("x");
    q5.push_back("x");
    queries.push_back(q5);
    
    vector<double> ans = calcEquation(equations, values, queries);
    for (int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    
    return 0;
}
6 0.5 -1 1 -1

Complexity Analysis

Time Complexity = O(q * (V + E)), where
q –> Number of queries
V –> Number of vertices in the graph(or number of variables)
E –> Number of edges in the graph(or number of equations)

READ  Container with Most Water

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions