CurrencyRateConversion.java

package berke;

import java.util.*;

public class Main
{
    private static Boolean found = false;
    private static Double answer = -1d;

    // "static void main" must be defined in a public class.
    public static void main(String[] args)
    {
        List<Node> data = new ArrayList<Node>();
        data.add(new Node("USD", "JPY", 110));
        data.add(new Node("USD", "AUD", 1.45));
        data.add(new Node("JPY", "GBP", 0.0070));
        data.add(new Node("USD", "TRY", 14.80));
        data.add(new Node("TRY", "JPY", 8.04));

        System.out.println(getRatioDFS("GBP", "AUD", data));
    }

    static class Node
    {
        String start;
        String end;
        double ratio;

        public Node(String s, String e, double r)
        {
            this.start = s;
            this.end = e;
            this.ratio = r;
        }

        @Override
        public String toString()
        {
            return "Node{" +
                    "start='" + start + '\'' +
                    ", end='" + end + '\'' +
                    ", ratio=" + ratio +
                    '}';
        }
    }

    public static double getRatioDFS(String start, String end, List<Node> data)
    {
        final Map<String, Map<String, Double>> map = generateMap(data);
        System.out.println(map);
        Set<String> visited = new HashSet<>();
        double ratio = 1.0;
        return visitDFS(start, visited, map, ratio, end);

    }
    private static double visitDFS(String visit, Set<String> visited, Map<String, Map<String, Double>> map,
                                   double ratio, String end)
    {
        if (end.equals(visit))
        {
            return ratio;
        }
        visited.add(visit);

        final Map<String, Double> ratiosOfCurrent = map.get(visit);
        double finalRate = -1;
        for (Map.Entry<String, Double> nextVisit : ratiosOfCurrent.entrySet())
        {
            if (!visited.contains(nextVisit.getKey()))
            {
                System.out.println("current: " + visit + " next: " + nextVisit + " ratio " + ratio + " finalrate " + finalRate + " end " + end);
                double rate = visitDFS(nextVisit.getKey(), visited, map, ratio * nextVisit.getValue(), end);
                finalRate = Math.max(finalRate, rate);
            }
        }
        return finalRate;
    }

    private static Map<String, Map<String, Double>> generateMap(List<Node> data)
    {
        Map<String, Map<String, Double>> map = new LinkedHashMap<>();
        for (Node node : data)
        {
            if (!map.containsKey(node.start))
                map.put(node.start, new HashMap());
            map.get(node.start).put(node.end, node.ratio);
            if (!map.containsKey(node.end))
                map.put(node.end, new HashMap());
            map.get(node.end).put(node.start, 1.0 / node.ratio);
        }
        return map;
    }
}