Как решать алгоритмические вопросы с помощью транзитивных зависимостей / графиков?

Question

Я немного борюсь, когда мне задают эти вопросы в интервью.Скажем, например, у меня есть вопрос, где мне нужно найти сумму конвертированной валюты из одной валюты в другую, и мне дают список валют.Как мне построить отображение смежности / отношений, чтобы я мог получить правильную сумму.Даже алгоритм, который объясняет логику, будет достаточно.Оцените ваши предложения по этому вопросу!100).Мне нужно найти конверсию от USD-> XXX = 7500. Я также должен быть в состоянии сделать конверсию в обратном направлении, скажем, INR-> USD.Как мне найти это, построив график?.

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

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

return convertedCurrency;
}

Answer 1

Я не уверен, как использовать алгоритм Флойд-Варшалла для решения этой проблемы. Однако мне удалось решить эту проблему с помощью динамического программирования. Вот мое решение:

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)];

    }

Я считаю, что лучший способ решить проблемы транзитивной зависимости - это сначала идентифицировать узлы и их взаимосвязи, а затем отследить их. Джокер из темного рыцаря говорит: «Иногда все, что нужно, это небольшой толчок»:)

Answer 2

В указанной вами задаче граф является ориентированным графом. Допустим, вы представляете граф с помощью матрицы смежности. Заполните матрицу данными, которые у вас есть для всех валют. Например, USD-> INR имеет курс R1, поэтому INR-> USD будет равен 1 / R1. После заполнения матрицы смежности используйте алгоритмы для вычисления транзитивного замыкания ориентированного графа , например Алгоритм Флойда – Варшалла .