algorithm - 检查货币转换文件是否一致

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 对 USD 的汇率为 0.02
• 利率相乘。确保正确比较 float (预计会有一些小差异)。

由于您可以将一些东西相乘以获得精心制作的示例，因此您可能会得到非常大或非常小的值，这会使比较变得更加困难。处理这种情况的更好方法是获取数字的日志(基数无关紧要)。现在乘法被加法代替了，而且更加稳定。副作用是加法和减法比乘法和除法快得多。