How to solve algorithmic questions with transitive dependencies/graphs?

Question

I kind of struggle when I get asked these questions in interviews. Say for example, I have a question where I need to find the converted currency amount from one currency to another and I am given the list of currencies. How do I build the adjacency/relationship mapping so that I could get to the correct amount. Even an algorithm that explains the logic would suffice. Appreciate your suggestions on this !.

For example:

Lets say I am given a list of currency Objects that contains different conversion rates(USD->INR = 75, INR -> XXX = 100). I need to find the conversion from USD-> XXX = 7500. I should also be able to do the conversion backwards say INR->USD. How do I find it by building a graph ?.

public Currency{
String fromCurrency;
String toCurrency;
double rate;
}

public double currencyConverter(List<Currency> currencies, fromCurrency, toCurrency){

return convertedCurrency;
}

Answer 1

I am not sure how to use Floyd-Warshall Algorithm to solve this problem. However, I was able to solve this problem using dynamic programming. Here is my solution:

class Currency{

    String fromCurrency;
    String toCurrency;
    double rate;

    public Currency(String fromCurrency, String toCurrency, double rate) {
        this.fromCurrency = fromCurrency;
        this.toCurrency = toCurrency;
        this.rate = rate;
    }
}

public class CurrencyConverter {

    public static double currencyConverter(List<Currency> currencies, String fromCurrency, String toCurrency) {

        Set<String> currencyNotes = new LinkedHashSet<>();

        for(Currency currency : currencies) {
            currencyNotes.add(currency.fromCurrency);
            currencyNotes.add(currency.toCurrency);
        }

        Map<String, Integer> currencyMap = new TreeMap<>();
        int idx = 0;

        for(String currencyNote : currencyNotes) {
            currencyMap.putIfAbsent(currencyNote, idx++);
        }

        double[][] dp = new double[currencyNotes.size()][currencyNotes.size()];

        for(double[] d : dp) {
            Arrays.fill(d, -1.0);
        }

        for(int i=0;i<currencyNotes.size();i++) {
            dp[i][i] = 1;
        }

        for(Currency currency : currencies) {
            Integer fromCurrencyValue = currencyMap.get(currency.fromCurrency);
            Integer toCurrencyValue = currencyMap.get(currency.toCurrency);

            dp[fromCurrencyValue][toCurrencyValue] = currency.rate;
            dp[toCurrencyValue][fromCurrencyValue] = 1/(currency.rate);
        }

        for(int i=currencyNotes.size()-2;i>=0;i--) {
            for(int j= i+1;j<currencyNotes.size();j++) {
                dp[i][j] = dp[i][j-1]*dp[i+1][j]/(dp[i+1][j-1]);
                dp[j][i] = 1/dp[i][j];
            }
        }

        return dp[currencyMap.get(fromCurrency)][currencyMap.get(toCurrency)];

    }

I believe the best way to solve transitive dependency problems is to first identify the nodes and their relationships, and backtrack it. As joker from the dark knight says "Sometimes all it takes is a little push" :)