Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Currency Convert

Sharing is caring!

Problem Statement
Given the following input CSV file:

From    To  Rate
USD;EUR;0.89
USD;GBP;0.79
GBP;CHF;1.26
CHF;JPY;108.66
... ... ...

Implement an algorithm to convert from a source currency to a target currency.

package problems;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

/**
 * Given the following input CSV file:
 *
 * From To  Rate
 * USD;EUR;0.89
 * USD;GBP;0.79
 * GBP;CHF;1.26
 * CHF;JPY;108.66
 * ...  ... ...
 *
 *
 * Implement an algorithm to convert from a source currency to a target currency.
 */
public class ConvertCurrency {

    static class CurrencyGraph {
        Map<String, Set<String>> nodeToNeighbors;
        Map<String, Map<String, Double>> sourceToTargetRate;

        public CurrencyGraph() {
            nodeToNeighbors = new HashMap<>();
            sourceToTargetRate = new HashMap<>();
        }

        void addEdge(String source, String target, Double rate) {
            if (!nodeToNeighbors.containsKey(source)) {
                nodeToNeighbors.put(source, new HashSet<>());
            }
            nodeToNeighbors.get(source).add(target);

            if (!sourceToTargetRate.containsKey(source)) {
                sourceToTargetRate.put(source, new HashMap<>());
            }
            sourceToTargetRate.get(source).put(target, rate);
        }

        Set<String> getNeighborsOf(String node) {
            if (!nodeToNeighbors.containsKey(node)) {
                throw new IllegalStateException("Node " + node + " does not exist!");
            }

            return nodeToNeighbors.get(node);
        }

        double getRateFor(String source, String target) {
            if (!nodeToNeighbors.containsKey(source)) {
                throw new IllegalStateException("Node " + source + " does not exist!");
            }

            if (!(sourceToTargetRate.get(source)).containsKey(target)) {
                throw new IllegalStateException("Node " + target + " does not exist!");
            }

            return sourceToTargetRate.get(source).get(target);
        }

        double dfs(String source, String target, double currentAmount, Set<String> visited) {
            visited.add(source);

            Set<String> neighbors = getNeighborsOf(source);
            for (String neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    double rate = getRateFor(source, neighbor);
                    if (neighbor.equals(target)) {
                        return currentAmount * rate;
                    } else {
                        double tempResult = dfs(neighbor, target, currentAmount * rate, visited);
                        if (tempResult != -1) {
                            return tempResult;
                        }
                    }
                }
            }

            return -1;
        }


        double convert(String source, String target, double amount) {
            if (source.equals(target)) {
                return amount;
            }

            double result = dfs(source, target, amount, new HashSet<>());

            if (result != 1) {
                return result;
            } else {
                throw new IllegalStateException("Unable to solve!");
            }
        }
    }


    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "currencies.csv"));
        Scanner scanner = new Scanner(System.in);

        CurrencyGraph graph = new CurrencyGraph();

        while (scanner.hasNext()) {
            String line = scanner.next();
            String[] lineSplit = line.split(";");

            String source = lineSplit[0];
            String target = lineSplit[1];
            Double rate = Double.parseDouble(lineSplit[2]);

            graph.addEdge(source, target, rate);
            graph.addEdge(target, source, 1 / rate);
        }


        String searchSource = "USD";
        String searchTarget = "EUR";
        double amount = 5;
        System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget));

        searchSource = "EUR";
        searchTarget = "EUR";
        amount = 5;
        System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget));

        searchSource = "EUR";
        searchTarget = "USD";
        amount = 5;
        System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget));

        searchSource = "EUR";
        searchTarget = "GBP";
        amount = 5;
        System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget));

        searchSource = "EUR";
        searchTarget = "JPY";
        amount = 5;
        System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget));

        searchSource = "JPY";
        searchTarget = "USD";
        amount = 5;
        System.out.println(String.format("%f%s is %f%s", amount, searchSource, graph.convert(searchSource, searchTarget, amount), searchTarget));
    }
}