Проверьте, соответствует ли файл конвертации валюты

Question

Об этом спросили в интервью. Вам предоставляется файл, содержащий курсы обмена валюты.

Sample File :  
Currency1      Currency2      Rate  
USD            INR            50
GBP            INR            100  
GBP            USD            3       
....

Нам нужно сказать, является ли этот файл согласованным или нет? например, чтобы вышеуказанный файл был непротиворечивым, третья запись должна быть GBP->USD = 2 вместо 3. Как подойти к этой проблеме? Это проблема с графиком?

Answer 1

Да, это проблема с графиком.

Таблица непротиворечива, если для любой пары валют (A, B) ЛЮБОЙ путь конвертации всегда будет давать одинаковый курс.

Так что вы пытаетесь найти два пути, которые дают вам разные скорости.

Предполагая, что у вас есть связанный граф (вы можете конвертировать из чего угодно во что-то, возможно, через некоторую промежуточную валюту). Вы можете просто выбрать любую начальную валюту, а затем расширить ее, например, с помощью DepthFirstSearch или BreadthFirstSearch (не имеет значения, какая из них здесь), и рассчитать курсы. Если вы достигли валюты, которую вы не видели ранее, сохраните курс, который вы получили, если вы уже достигли его, курсы должны быть одинаковыми (в противном случае остановитесь и скажите, что они несовместимы).

Если у вас нет подключенного графика, убедитесь, что вы охватили все валюты. Вы можете использовать алгоритм выше, просто запустите его снова, пока вы можете найти недостигнутые валюты (используя недостигнутую валюту в качестве начальной точки).

Несколько вещей, на которые стоит обратить внимание:

• У вас есть некоторые неявные ставки. В вашем талбе INR к доллару США курс составляет 0,02
• Ставки объединяются путем умножения. Убедитесь, что вы правильно сравниваете поплавки (ожидайте небольшие различия).

Поскольку вы можете умножать вещи вместе для созданных примеров, вы можете получить действительно большие или действительно маленькие значения, и это усложнит сравнение. Лучший способ справиться с подобными ситуациями - взять журнал (база не имеет значения) чисел. Теперь умножение заменено сложением, и оно более стабильно. Побочным эффектом является то, что сложения и вычитания намного быстрее, чем умножения и деления.