Ali VO Interview Question: Best Currency Exchange Rate via Multiple Conversions

Problem Description

We have a currency exchange requirement. Now we need to convert CNY to USD and hope to get as much USD as possible. Multiple exchanges are allowed, and only the optimal exchange rate matters.

For example, if CNY can first be converted to EUR and then converted to USD to get a better exchange rate, we need to find the optimal rate.

Example

Case 1

input = [{"src":"CNY","tar":"USD","rate":"0.16"},
         {"src":"CNY","tar":"EUR","rate":"0.14"},
         {"src":"EUR","tar":"USD","rate":"1.09"},
         {"src":"EUR","tar":"JPY","rate":"136.54"},
         {"src":"JPY","tar":"MYR","rate":"0.008"}]

output = 0.16

This problem is a graph-based optimization task: currencies are nodes, and exchange rates are directed edges with multiplicative weights. We need the best conversion rate from CNY to USD, potentially through multiple intermediate currencies, so the direct edge is not always the answer. A typical solution is to traverse all reachable paths with DFS or BFS while tracking the cumulative product, or to transform rates with logarithms and solve it as a shortest-path problem. In the sample, although CNY -> EUR -> USD exists, the direct rate CNY -> USD = 0.16 is already optimal.