Currency Conversion Through Exchange Paths
Stripe● MediumFULLTIMENEW GRADPHONE SCREENProblem statement
You are given directed currency rates as from,to,rate. A rate of USD,CAD,1.26 means one USD converts to 1.26 CAD. Every supplied rate may also be used in reverse with reciprocal value.
For each source,target query, return the conversion rate from source to target. The currencies may be directly related, connected through one intermediate currency, or connected through an arbitrary number of intermediate currencies.
All queries are connected, rates are positive, and every cycle is consistent, so every valid path between the same two currencies gives the same result.
Function
convertCurrencies(rates: String[], queries: String[]) → double[]Examples
Example 1
rates = ["USD,CAD,1.26","USD,AUD,0.75","USD,JPY,109.23"]queries = ["CAD,USD","CAD,AUD"]return = [0.7936507937,0.5952380952]CAD to USD uses the reciprocal of 1.26. CAD to AUD follows CAD → USD → AUD.
Example 2
rates = ["EUR,GBP,0.86","GBP,JPY,190","JPY,KRW,9.1"]queries = ["EUR,KRW","KRW,GBP"]return = [1486.94,0.0005786008]The first query multiplies three forward edges. The second uses the reciprocals of KRW → JPY and JPY → GBP.
Constraints
1 <= rates.length, queries.length <= 10000.- Currency codes are non-empty and contain no commas.
- Every rate is finite and strictly positive.
- Every query's currencies exist in the same connected component.
- All supplied rates are mutually consistent.
- Answers are accepted within
1e-6absolute or relative error.