How to Solve Currency Conversion

Written By
Adam Bhula

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


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

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

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.