Currency Conversion

Medium Graphs (DFS / BFS) 3 parts 209 lines View on GitHub ↗

Question

Topic: Graphs (DFS / BFS) · Difficulty: Medium

You get exchange rates as one string, FROM:TO:RATE pairs separated by commas, e.g. "USD:CAD:1.3,EUR:USD:1.1,GBP:EUR:1.15". A rate also works in reverse (TO → FROM is 1 / RATE).

Part 1: direct conversion

Convert amount from one currency to another using a direct rate (either direction). Round to 2 decimals. Trim stray spaces ("USD :CAD:1.3 "). If there is no direct rate, return -1.

Part 2: convert through other currencies

If there is no direct rate, go through other currencies (AUD → USD → GBP). Return the route, the combined rate and the converted value, or “No available conversion”.

Part 3: shortest route

Several routes may exist. Return the one with the fewest hops.

input = "USD:EUR:0.85,EUR:GBP:0.87,USD:CAD:1.3,CAD:AUD:1.1,AUD:NZD:1.05,NZD:GBP:0.5"
USD → GBP  ⇒  route USD -> EUR -> GBP

Approach: build a graph with both directions. Part 2: DFS that multiplies rates along the path and backtracks. Part 3: BFS with a parent map, then walk back from the target to rebuild the route and rate.

CurrencyConversionPart1.java 35 lines GitHub ↗

/**
 * Problem: Currency Conversion
 * Difficulty: Medium
 * Topic: Graphs (DFS / BFS)
 * Question: Convert an amount using FROM:TO:RATE pairs: direct rate, then through other currencies, then the shortest route. Full statement in README.md.
 */
package dsa.question1;

import java.util.HashMap;

public class CurrencyConversionPart1 {

    public static Double convertCurrency(String inputstring, String fromcurreny , String tocurrency , Double amount) {
//        Input:
//        input_str = "USD:CAD:1.3,EUR:USD:1.1,GBP:EUR:1.15"
//        from_currency = "USD"
//        to_currency = "CAD"
//        amount = 100.0
         // note 1  : handle extra space
         // note 2  : handle if not present

          String[] conversion = inputstring.split(",");
          HashMap<String , Double> ratePerCurrency = new HashMap<>();

          for(int i=0; i<conversion.length; i++) {
              String[] parts = conversion[i].split(":");
              String currency1 = parts[0].trim();
              String currency2 = parts[1].trim();
              Double rate = Double.parseDouble(parts[2].trim());
              ratePerCurrency.put(currency1+"-"+currency2 , rate);
              ratePerCurrency.put(currency2+"-"+currency1 , 1.0/rate);
          }

          String key = fromcurreny + "-" + tocurrency;
          if(!ratePerCurrency.containsKey(key)) {
              return -1.0;
          }
          double rate = Math.round(amount * ratePerCurrency.get(key) * 100 ) / 100.0;
          return rate;
    }
}

CurrencyConversionPart2.java 68 lines GitHub ↗

package dsa.question1;

import java.util.*;

public class CurrencyConversionPart2 {

    private HashMap<String , List<Pair>> ratePerCurrency;
    private List<String> path;
    private Set<String> isvisited;
    private Double finalRate;

    private Boolean dfs(String currency, String finalcurrency) {
       // base condition
        if(currency.equals(finalcurrency)) {
            return true;
        }

        isvisited.add(currency);

        if(ratePerCurrency.containsKey(currency)) {

            List<Pair> connectedcurrency = ratePerCurrency.get(currency);

            for(Pair p : connectedcurrency) {
                String nextcurrency = p.currency;
                Double nextrate = p.rate;
                if(!isvisited.contains(nextcurrency)) {
                    // add in path
                    path.add(nextcurrency);
                    finalRate = finalRate*nextrate;
                    if(dfs(nextcurrency, finalcurrency)) {
                        return true;
                    }
                    finalRate = finalRate/nextrate;
                    path.remove(path.size()-1);
                }
            }
        }
        return false;

    }
    public Map<String, Object> convertCurrency(String inputstring, String fromcurreny, String tocurrency, Double amount) {

        String[] conversion = inputstring.split(",");
        ratePerCurrency = new HashMap<>();
        path = new ArrayList<>();
        isvisited = new HashSet<>();
        finalRate = 1.0;

        for(int i=0; i<conversion.length; i++) {

            String[] parts = conversion[i].split(":");
            String currency1 = parts[0].trim();
            String currency2 = parts[1].trim();
            Double rate = Double.parseDouble(parts[2].trim());

            ratePerCurrency.computeIfAbsent(currency1 ,k -> new ArrayList<>()).add(new Pair(currency2, rate));
            ratePerCurrency.computeIfAbsent(currency2 ,k -> new ArrayList<>()).add(new Pair(currency1, 1.0/rate));

        }

        Map<String, Object> result = new HashMap<>();
        path.add(fromcurreny);
        if(dfs(fromcurreny, tocurrency)) {
            result.put("route" , String.join(" -> " , path));
            result.put("rate" , Math.round(finalRate*100.0) / 100.0);
            result.put("convert_value" , Math.round(amount * finalRate * 100.0) / 100.0);
        }else{
            result.put("route", "No available conversion");
            result.put("rate", -1);
            result.put("convert_value", -1);
        }

        return result;
    }

    private static class Pair {
        String currency;
        double rate;
        public Pair(String currency , double rate) {
            this.currency = currency;
            this.rate = rate;
        }
    }


}

CurrencyConversionPart3.java 67 lines GitHub ↗

package dsa.question1;

import java.util.*;

public class CurrencyConversionPart3 {
  
    private HashMap<String , List<Pair>> ratePerCurrency;
    private List<String> path;
    private Double finalRate;

    public Map<String, Object> convertCurrency(String inputstring, String fromcurreny, String tocurrency, Double amount) {

        String[] conversion = inputstring.split(",");
        ratePerCurrency = new HashMap<>();
        path = new ArrayList<>();
        finalRate = 1.0;

        for(int i=0; i<conversion.length; i++) {

            String[] parts = conversion[i].split(":");
            String currency1 = parts[0].trim();
            String currency2 = parts[1].trim();
            Double rate = Double.parseDouble(parts[2].trim());

            ratePerCurrency.computeIfAbsent(currency1 ,k -> new ArrayList<>()).add(new Pair(currency2, rate));
            ratePerCurrency.computeIfAbsent(currency2 ,k -> new ArrayList<>()).add(new Pair(currency1, 1.0/rate));

        }

        HashMap<String , Pair> parentCurrency = new HashMap<>();

        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(fromcurreny , 1.0));
        parentCurrency.put(fromcurreny, new Pair(null, 1.0));

        while(!queue.isEmpty()) {
            Pair p = queue.poll();
            String currentcurrency = p.currency; Double rate = p.rate;

            if(currentcurrency.equals(tocurrency)) {
                break;
            }

            if(ratePerCurrency.containsKey(currentcurrency)) {
                for(Pair nextPair : ratePerCurrency.get(currentcurrency)) {
                    String nextcurrency = nextPair.currency; Double nextrate = nextPair.rate;
                    if(!parentCurrency.containsKey(nextcurrency)) {
                        parentCurrency.put(nextcurrency , new Pair(currentcurrency , nextrate));
                        queue.offer(new Pair(nextcurrency , nextrate));
                    }
                }
            }

        }
        Map<String, Object> result = new HashMap<>();

        if(parentCurrency.containsKey(tocurrency)) {
            String currency = tocurrency;
            while(currency != null) {
                path.add(currency);
                finalRate = finalRate * parentCurrency.get(currency).rate;
                currency = parentCurrency.get(currency).currency;
            }

            Collections.reverse(path);

            result.put("route" , String.join(" -> " , path));
            result.put("rate" , Math.round(finalRate * 100.0)/100.0);
            result.put("convert_value" , Math.round(amount * finalRate * 100.0) / 100.0);

        }else{
            result.put("route", "No available conversion");
            result.put("rate", -1);
            result.put("convert_value", -1);
        }

        return result;
    }

    private static class Pair {
        String currency;
        double rate;
        public Pair(String currency , double rate) {
            this.currency = currency;
            this.rate = rate;
        }
    }
}

Demo.java 39 lines GitHub ↗

package dsa.question1;

import java.util.Map;

public class Demo {
    public static void main(String[] args) {
        // part1
        String input = "USD:CAD:1.3,EUR:USD:1.1,GBP:EUR:1.15";
//        String currency1 = "EUR";
//        String currency2 = "GBP";
//        Double amount = CurrencyConversionPart1.convertCurrency(input, currency1, currency2, 100.0);
//        System.out.println(amount);
//
//        // part2 - space in currency or rate
//        String input2 = "USD :CAD:1.3,EUR:USD:1.1,GBP :EUR:1.15 ";
//        Double amount1 = CurrencyConversionPart1.convertCurrency(input2, "EUR", "GBP", 100.0);
//        System.out.println(amount1);
//
//
//        // part2 - if not prresnt
//        Double amount3 = CurrencyConversionPart1.convertCurrency(input2, "AUD", "GBP", 100.0);
//        System.out.println(amount3);

//        CurrencyConversionPart2 currencyConversionPart2 = new CurrencyConversionPart2();
//        // Format: FROM:TO:RATE
        String input1 = "AUD:USD:0.65,USD:GBP:0.80,GBP:INR:110";
//
//        Map<String, Object> result =
//                currencyConversionPart2.convertCurrency(input1, "AUD", "GBP", 100.0);
//
//        System.out.println("Route: " + result.get("route"));
//        System.out.println("Rate: " + result.get("rate"));
//        System.out.println("Converted Amount: " + result.get("convert_value"));

        String input3 = "USD:EUR:0.85,EUR:GBP:0.87,USD:CAD:1.3,CAD:AUD:1.1,AUD:NZD:1.05,NZD:GBP:0.5";

        CurrencyConversionPart3 currencyConversionPart3 = new CurrencyConversionPart3();
        Map<String, Object> result3 =
                currencyConversionPart3.convertCurrency(input3, "USD", "GBP", 100.0);

        System.out.println("Route: " + result3.get("route"));
        System.out.println("Rate: " + result3.get("rate"));
        System.out.println("Converted Amount: " + result3.get("convert_value"));

    }


}