How to Solve Currency Conversion
Currency Conversion Introduction
Currency Conversion Introduction
The Currency Conversion problem involves finding the conversion rate that maps to the 'from' currency to the 'to' currency for every single query. The challenge is in building the graph, using either DFS or BFS to traverse, and then keeping track of the visited nodes.
Currency Conversion Problem
Currency Conversion Problem
Parameters:
- An array of currency conversion rates. E.g. ['USD', 'GBP', 0.77] which means 1 USD is equal to 0.77 GBP
- A list of queries containing a 'from' currency and a 'to' currency
Question: Given the above parameters, find the conversion rate that maps to the 'from' currency to the 'to' currency from every single query. Your return value should be a number.
Example: You are given the following parameters:
Rates: ['USD', 'JPY', 100] ['JPY', 'CHN', 20] ['CHN', 'THAI', 200] Queries: [['USD', 'CHN'], ['JPY', 'THAI'], ['USD', 'AUD']] Output: [1000.0, 4000.0, -1.0]
Currency Conversion Solutions
Currency Conversion Solutions
This solution uses a graph to represent the currency conversion rates. Each currency is a node, and the value of the edge between two nodes represents the ratio of their values. The graph is built by iterating through the given rates and adding the appropriate edges to the graph.
To find the conversion rate for each query, we use a depth-first search algorithm. The DFS function takes the starting node, ending node, and a set of visited nodes as input and recursively traverses the graph to find the path value between the starting and ending nodes. The visited set ensures that nodes already visited in the current path are not visited again, preventing infinite loops in cyclic graphs. If the path value is found, the DFS function returns the product of the current edge value and the path value. If the path value is not found, the DFS function returns -1.0 to indicate that the query cannot be evaluated.
Finally, the solution iterates through the given queries, performs the DFS algorithm for each query, and adds the resulting value to the output list.
from collections import defaultdict
def calculate_conversion_rates(rates, queries):
# Build graph
graph = defaultdict(dict)
for rate in rates:
from_currency, to_currency, value = rate
graph[from_currency][to_currency] = value
graph[to_currency][from_currency] = 1/value
# Perform DFS for each query
result = []
for query in queries:
from_currency, to_currency = query
visited = set()
rate = dfs(graph, from_currency, to_currency, 1.0, visited)
result.append(rate)
return result
def dfs(graph, start, end, value, visited):
if start not in graph or start in visited:
return -1.0
if start == end:
return value
visited.add(start)
neighbors = graph[start]
for neighbor, neighbor_value in neighbors.items():
rate = dfs(graph, neighbor, end, value * neighbor_value, visited)
if rate != -1.0:
return rate
return -1.0
rates = [['USD', 'JPY', 100], ['JPY', 'CHN', 20], ['CHN', 'THAI', 200]]
queries = [['USD', 'CHN'], ['JPY', 'THAI'], ['USD', 'AUD']]
# Run the function and print the result
print(calculate_conversion_rates(rates, queries))1from collections import defaultdict
2
3def calculate_conversion_rates(rates, queries):
4 # Build graph
5 graph = defaultdict(dict)
6 for rate in rates:
7 from_currency, to_currency, value = rate
8 graph[from_currency][to_currency] = value
9 graph[to_currency][from_currency] = 1/value
10
11 # Perform DFS for each query
12 result = []
13 for query in queries:
14 from_currency, to_currency = query
15 visited = set()
16 rate = dfs(graph, from_currency, to_currency, 1.0, visited)
17 result.append(rate)
18
19 return result
20
21def dfs(graph, start, end, value, visited):
22 if start not in graph or start in visited:
23 return -1.0
24 if start == end:
25 return value
26 visited.add(start)
27 neighbors = graph[start]
28 for neighbor, neighbor_value in neighbors.items():
29 rate = dfs(graph, neighbor, end, value * neighbor_value, visited)
30 if rate != -1.0:
31 return rate
32 return -1.0
33
34rates = [['USD', 'JPY', 100], ['JPY', 'CHN', 20], ['CHN', 'THAI', 200]]
35queries = [['USD', 'CHN'], ['JPY', 'THAI'], ['USD', 'AUD']]
36
37# Run the function and print the result
38print(calculate_conversion_rates(rates, queries))Time/Space Complexity
- Time complexity:
O(n * m), where n is the number of exchange rates and m is the longest path in the graph. This is because we perform a DFS for each query and the worst-case scenario is that all the vertices in the longest path are visited. - Space complexity:
O(n). The space complexity is also O(n), because the graph is represented using a defaultdict that may have at most n keys.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
