Currency Exchange - Uber Coding Interview | ShowOffer

Problem Statement: You are given a list of currency exchange rates, represented as a list of pairs of strings, where the first string in each pair is the currency you have and the second string is the currency you want to exchange to. You need to determine if it's possible to exchange all your currency to the target currency, and if so, return the minimum number of exchanges required.

Examples:

1. Given the list ["USD:EUR", "EUR:JPY", "JPY:USD"], the answer is 2 because you can exchange USD to EUR, then EUR to JPY, and finally JPY back to USD.
2. Given the list ["USD:EUR", "EUR:GBP", "GBP:USD"], the answer is 2 because you can exchange USD to EUR, then EUR to GBP, and finally GBP back to USD.
3. Given the list ["USD:EUR", "JPY:GBP"], the answer is 0 because there is no way to exchange USD to GBP.

Constraints:

• The list of currency exchange rates will contain at least one pair of currencies.
• Each currency code is a unique string of 3 uppercase letters.
• The input list will not contain duplicate pairs.

Hints:

1. You can represent the currency exchange rates as a graph, where each currency is a node and each exchange rate is an edge.
2. Use a breadth-first search (BFS) or depth-first search (DFS) algorithm to traverse the graph and find the shortest path from the starting currency to the target currency.

Solution: `python from collections import deque

def min_exchanges(currencies): graph = {} for start, end in currencies: if start not in graph: graph[start] = [] graph[start].append(end)

visited = set()
queue = deque([("USD", 0)])

while queue:
    curr, exchanges = queue.popleft()
    if curr == "USD" and exchanges > 0:
        return exchanges
    visited.add(curr)
    for neighbor in graph.get(curr, []):
        if neighbor not in visited:
            queue.append((neighbor, exchanges + 1))

return 0

Example usage:

currencies = ["USD:EUR", "EUR:JPY", "JPY:USD"] print(min_exchanges(currencies)) # Output: 2 `

Explanation: This solution uses a breadth-first search (BFS) algorithm to traverse the graph of currency exchange rates. It starts from the "USD" currency and explores all possible exchanges, keeping track of the number of exchanges required to reach each currency. If it finds a path back to "USD" with more than 0 exchanges, it returns the number of exchanges. If no such path exists, it returns 0.

The time complexity of this solution is O(V + E), where V is the number of currencies and E is the number of exchange rates, since we visit each currency and exchange rate at most once. The space complexity is O(V), as we store the visited currencies in a set.