How to Solve Currency Conversion

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

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

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))

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.