You are given several exact relationships between currencies. Use these relationships to determine the conversion rate between any two currencies.

A conversion may pass through multiple intermediate currencies.

Conversion Graph Representation

The currency conversion graph is represented by a List<String>. Each string has the format "fromCurrency,toCurrency,rate".

For example, "USD,CAD,2.0" means that one unit of USD equals 2.0 units of CAD.

Class

CurrencyConverter

Constructor

CurrencyConverter

public CurrencyConverter()

• Creates a new currency converter.

Method

getConversionRate

public double getConversionRate(List<String> conversionGraph, String fromCurrency, String toCurrency)

• conversionGraph contains the available currency relationships.
• Returns the number of units of toCurrency equal to one unit of fromCurrency.
• Returns -1.0 if either currency is unknown or no conversion chain connects them.

Follow-up Method

getConversionRates

public List<Double> getConversionRates(List<String> conversionGraph, List<String> queries)

• Answers all conversion queries using the supplied conversionGraph.
• Each string in queries has the format "fromCurrency,toCurrency".
• The returned list contains one result for each query.
• Results appear in the same order as their corresponding queries.
• A result is -1.0 if either currency is unknown or the currencies are not connected.

Rules

• Every supplied conversion may be used in both directions.
• If one unit of currency A equals rate units of currency B, then one unit of B equals 1.0 / rate units of A.
• The rate along a conversion chain is the product of all rates in that chain.
• All supplied relationships are mutually consistent. Therefore, every valid path between the same two currencies produces the same rate.
• Converting a known currency to itself produces 1.0.
• Converting an unknown currency to itself produces -1.0.
• The supplied conversion graph must not be modified.

Constraints

• n = conversionGraph.size()
• 1 ≤ n ≤ 100,000
• q = queries.size()
• 1 ≤ q ≤ 100,000
• Every conversion entry contains exactly three comma-separated values.
• Every query contains exactly two comma-separated currency codes.
• 1 ≤ fromCurrency.length(), toCurrency.length() ≤ 20
• Currency codes contain only uppercase English letters and are case-sensitive.
• 0.001 ≤ rate ≤ 1,000.0
• Every supplied rate is positive.
• All reachable conversion results fit in a finite positive double.
• Answers within 10-4 of the expected value are accepted. Round final answer after 4 decimal places and remove trailing zeros after decimal.

Examples

Example 1

getConversionRate(conversionGraph = List.of("USD,CAD,2.0", "CAD,MXN,5.0"), fromCurrency = "USD", toCurrency = "MXN")

Output: 10.0

One USD equals two CAD, and one CAD equals five MXN. Therefore, one USD equals 2.0 * 5.0 = 10.0 MXN.

Example 2

getConversionRate(conversionGraph = List.of("GBP,EUR,2.0", "EUR,JPY,2.0"), fromCurrency = "JPY", toCurrency = "GBP")

Output: 0.25

One GBP equals four JPY, so one JPY equals 1.0 / 4.0 = 0.25 GBP.

Example 3: Multiple Queries

getConversionRates(conversionGraph = List.of("USD,CAD,2.0", "CAD,MXN,5.0", "EUR,CHF,0.5"), queries = List.of("USD,MXN", "MXN,USD", "USD,CHF", "CAD,CAD", "XYZ,XYZ"))

Output: List.of(10.0, 0.1, -1.0, 1.0, -1.0)

USD converts to MXN through CAD, and the reverse rate is 0.1. USD and CHF are disconnected, CAD is known, and XYZ is unknown.