Evaluate Division

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in companies
UberIBMSalesforce

Problem statement

You are given an array of pairs of strings 'EQUATIONS', and an array of real numbers 'VALUES'. Each element of the 'EQUATIONS' array denotes a fraction where the first string denotes the numerator variable and the second string denotes the denominator variable, and the corresponding element in 'VALUES' denotes the value this fraction is equal to.

You are given ‘Q’ queries, and each query consists of two strings representing the numerator and the denominator of a fraction. You have to return the value of the given fraction for each query. Return -1 if the value cannot be determined.

Example : 
'EQUATIONS' = { {“a”, ”s”} , {“s”, “r”} }
'VALUES' = { 1.5, 2 }
queries = { {“a”, “r” } }

For the above example (a / s) = 1.5 and (s / r) = 2 therefore (a / r) = 1.5 * 2 = 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case contains two integers, ‘N’ and ‘Q,’ separated by a single space denoting the number of the equations and the number of queries, respectively.

The second line of each test case contains ‘N’ strings denoting the numerator variable of the 'EQUATIONS'.

The third line of each test case contains ‘N’ strings denoting the denominator variable of the 'EQUATIONS'.

The fourth line of each test case contains ‘N’ real numbers denoting the 'VALUE' of each fraction.

The fifth line of each test case contains ‘Q’ strings denoting the numerator variable for each query.

The sixth line of each test case contains ‘Q’ strings denoting the denominator variable for each query.
Output Format : 
For each test case, return the value of the fraction up to 5 decimal places or -1 if the value of the fraction cannot be determined. All values are separated by a single space.

Your output will be considered correct if the relative error does not exceed 10^(-6).
Note : 
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
1 <= N <= 100
1 <= Q <= 100
1 <= |S| <= 10
0.0 < values[i] <= 100.0

Where '|S|' denotes the length of the variables, and 'VALUES[i]' denotes the value of the i’th equation.

Time limit: 1 sec
Sample Input 1 :
2
2 1
a s
s r
1.5 2
a
r
3 2
a abc ab
x xyz xy
0.5 1 3.4
abc pqr
xyz rew
Sample Output 1 :
3.00000
1.00000 -1.00000
Explanation of Sample Output 1 :
In test case 1, (a / s) = 1.5 and (s / r) = 2 therefore (a / r) = 1.5 * 2 = 3.

In test case 2, for the first query, the value of (abc / xyz) is given as 1, and the value of (pqr / rew) cannot be determined.
Sample Input 2 :
2
4 2
a r w p
r w p e
1.2 2.6 1 0.5
e a
p p
2 1
a x
b y
0.5 0.4
a
y
Sample Output 2 :
2.00000 3.12000
-1.00000
Explanation of Sample Output 2 :
In test case 1, for the first query we have p / e = 0.5 ,therefore e / p = 1 / 0.5 = 2, for the second query (a / r) * (r / w) * (w / p) = a / p which is equal to 1.2 * 2.6 * 1 = 3.12.

In test case 2, we can not determine the value of the a / y, by the given set of equations. Thus return -1.
Hint

Can you think about representing the equations by a directed graph?

Approaches (3)
DFS based Approach

The idea is to construct a weighted directed graph from the given equations. For each given equation, let’s make an edge from the numerator variable to the denominator variable with weight equal to the value of the equation and another edge from the denominator to the numerator with weight equal to the inverse of the value of the equation. After making the graph to solve any query, we will need to find a path from the numerator to the denominator.

 

Let’s consider any two nodes in the graph ‘A’ and ‘B, then the path from ‘A’ to ‘B’ will denote the fraction ‘A' / ‘B’, and its value will be equal to the multiplication of the weights of all edges on the path from ‘A’ to ‘B’.

 

Let’s consider the following path from ‘A’ to ‘B’ (A -> X -> Y -> B); we know that each directed of the form P->Q represents a fraction P/Q. Hence the value of this path will be (A / X) * (X / Y) * (Y / B) = A / B.

 

The steps are as follows :

 

  1. Iterate through the ‘EQUATIONS’ array; let’s say we are currently at index ‘i’.
    • Insert an edge from the numerator variable to the denominator variable with weight equal to ‘VALUES[i]’.
    • Also, insert an edge from the denominator variable to the numerator variable with a weight equal to 1 / ‘VALUES[i]’.
  2. Iterate through the queries; let’s say the numerator and denominator for the current query are ‘NUM' and ’DEN'.
    • Traverse the graph to find a path from ‘NUM' and ‘DEN’ using Depth First Search Algorithm.
    • If there is no such path, then the value cannot be determined. Hence the result for this query will be -1.
    • Otherwise, the answer for this query will be the product of all values on the path from ‘NUM' to ‘DEN’.
Time Complexity

O(N * Q), Where ‘N’ is the number of equations, and ‘Q’ is the number of queries.

 

Since we are answering Q queries, and for each query, we are traversing the graph which will have N nodes and a total of 2 * N edges thus the total time taken to traverse the graph will be (N + 2 * N) in the worst case. Thus, the overall time complexity is O(N * Q).

Space Complexity

O(N), Where 'N' is the number of equations.

 

Since we are creating a graph in which we are representing each equation with an edge. Since there are N equations storing the graph will take O(N) space. Thus, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Evaluate Division
All tags
Sort by
Search icon
profile
Nimesh Nikhil

Interview problems

Using BFS

#include<bits/stdc++.h>

using namespace std;

 

unordered_map<string,vector<pair<string,double>>> adj;

 

double bfs(string src, string d) {

    if (src == d) return 1.0;

 

    queue<pair<string,double>> q;

    q.push({src, 1.0});

    unordered_map<string, bool> vis;

    vis[src] = true;

 

    while (!q.empty()) {

        auto x = q.front();

        q.pop();

        string node = x.first;

        double dis = x.second;

 

        if (node == d) 

            return dis;

 

        for (auto& c : adj[node]) {

            if (!vis[c.first]) {

                vis[c.first] = true;

                q.push({c.first, dis * c.second});

            }

        }

    }

    return -1;

}

 

vector<double> evaluateEquations(vector<pair<string, string>> &a, vector<pair<string, string>> &q, vector<double> &b) {

    adj.clear(); // Clear the adjacency map at the start of the function

    int n = a.size();

 

    for (int i = 0; i < n; i++) {

        adj[a[i].first].push_back({a[i].second, b[i]});

        adj[a[i].second].push_back({a[i].first, 1 / b[i]});

    }

 

    vector<double> ans;

    for (auto& x : q) {

        if (adj.find(x.first) == adj.end() || adj.find(x.second) == adj.end()) 

            ans.push_back(-1);

        else 

            ans.push_back(bfs(x.first, x.second));

    }

 

    return ans;

}

 

35 views
0 replies
0 upvotes
profile
Codestudio

Interview problems

Discussion thread on Interview Problem | Evaluate Division

Hey everyone, creating this thread to discuss the interview problem - Evaluate Division.

 

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Evaluate Division

 

418 views
1 reply
0 upvotes
Full screen
Console