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 answer for  Cj / Dj = ? .

Return the answers to all queries. If a single answer cannot be determined, return  -1.0 .

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

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.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 ]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints:

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= Ai.length, Bi.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= Cj.length, Dj.length <= 5
  • Ai, Bi, Cj, Dj  consist of lower case English letters and digits.

Solution:

For example:
Given:
a/b = 2.0, b/c = 3.0
We can build a directed graph:
a — 2.0 –> b — 3.0 –> c
If we were asked to find a/c, we have:
a/c = a/b * b/c = 2.0 * 3.0
In the graph, it is the product of costs of edges.

Do notice that, 2 edges need to added into the graph with one given equation,
because with a/b we also get result of b/a, which is the reciprocal of a/b.

so the previous example also gives edges:
c — 0.333 –> b — 0.5 –> a

Now we know how to model this problem, what we need to do is simply build the
graph with given equations, and traverse the graph, either DFS or BFS, to find a path
for a given query, and the result is the product of costs of edges on the path.

One optimization, which is not implemented in the code, is to “compress” paths for
past queries, which will make future searches faster. This is the same idea used in
compressing paths in union find set. So after a query is conducted and a result is found,
we add two edges for this query if these edges are not already in the graph.

Given the number of variables N, and number of equations E,
building the graph takes O(E), each query takes O(N), space for graph takes O(E)

I think if we start to compress paths, the graph will grow to O(N^2), and we
can optimize the query to O(1), please correct me if I’m wrong.

class Solution(object):
def calcEquation(self, equations, values, queries):
graph = {}
def build_graph(equations, values):
def add_edge(f, t, value):
if f in graph:
graph[f].append((t, value))
else:
graph[f] = [(t, value)]
for vertices, value in zip(equations, values):
f, t = vertices
add_edge(f, t, value)
add_edge(t, f, 1/value)
def find_path(query):
b, e = query
if b not in graph or e not in graph:
return -1.0
q = collections.deque([(b, 1.0)])
visited = set()
while q:
front, cur_product = q.popleft()
if front == e:
return cur_product
visited.add(front)
for neighbor, value in graph[front]:
if neighbor not in visited:
q.append((neighbor, cur_product*value))
return -1.0
build_graph(equations, values)
return [find_path(q) for q in queries]
IAMISHAAN Ads
Categories: InterviewPython

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content is protected !!
IAMISHAAN

FREE
VIEW