Currency Exchange
Adhikram Maitra
9928
Mar 24, 2024
UberInterview

Currency Exchange

This implementation demonstrates a solution for calculating currency exchange rates using a disjoint set (union-find) data structure.

Approach

  • Disjoint Set Representation: Each currency is represented as a node in a disjoint set. The parent map maintains the parent currency for each currency, and the exchangeRate map stores the exchange rate between each currency and its parent.
  • Adding New Currency: When adding a new currency with its parent and exchange rate using the addCurrency method, the corresponding entries are updated in the parent and exchangeRate maps. Additionally, the exchange rate of the parent currency is set to 1.0 if not already present.
  • Finding Ultimate Parent: The findUltimateParent method recursively finds the ultimate parent of a currency and updates its exchange rate along the path to maintain accurate conversion rates.
  • Calculating Conversion Rate: The calculateConversionRate method finds the ultimate parent of both the source and target currencies and checks if they are the same. If they are, it returns the conversion rate from the source currency to the target currency. Otherwise, it returns -1, indicating that the conversion is not possible.
  • Example: The provided main method demonstrates adding exchange rates for GBP, EUR, USD, and JPY currencies and calculating the conversion rate from GBP to USD and JPY for 10 units of GBP.
import java.util.HashMap;
import java.util.Map;

public class CurrencyExchange {

    private Map<String, String> parent;
    private Map<String, Double> exchangeRate;

    public CurrencyExchange() {
        parent = new HashMap<>();
        exchangeRate = new HashMap<>();
    }

    // Add a new currency with its parent and exchange rate
    public void addCurrency(String currency, String parentCurrency, double rate) {
        parent.put(currency, parentCurrency);
        exchangeRate.put(currency, rate);
        exchangeRate.put(parentCurrency, 1.0);
    }

    // Find the ultimate parent of a currency and update its exchange rate along the
    // path
    private String findUltimateParent(String currency) {
        if (!parent.containsKey(currency)) {
            return currency;
        }
        String ultimateParent = findUltimateParent(parent.get(currency));
        exchangeRate.put(currency, exchangeRate.get(currency) * exchangeRate.get(parent.get(currency)));
        parent.put(currency, ultimateParent);
        return ultimateParent;
    }

    // Calculate the conversion rate between two currencies
    public double calculateConversionRate(String fromCurrency, String toCurrency) {
        String ultimateParentFrom = findUltimateParent(fromCurrency);
        String ultimateParentTo = findUltimateParent(toCurrency);
        if (!ultimateParentFrom.equals(ultimateParentTo)) {
            return -1; // Conversion not possible
        }
        return exchangeRate.get(fromCurrency) / exchangeRate.get(toCurrency);
    }

    public static void main(String[] args) {
        CurrencyExchange exchange = new CurrencyExchange();

        // Example exchange rates
        exchange.addCurrency("GBP", "EUR", 10);
        exchange.addCurrency("EUR", "USD", 1.1);
        exchange.addCurrency("USD", "JPY", 108.3);

        // Example queries
        System.out.println("10 GBP to USD: " + exchange.calculateConversionRate("GBP", "USD") * 10); // 10 * 1.1 = 11
        System.out.println("10 GBP to JPY: " + exchange.calculateConversionRate("GBP", "JPY") * 10); // 10 * 1.1 * 108.3 =
                                                                                                // 1191.3
    }

}
Comments (4)