Rippling 汇率换算图：DFS 权重、逆边与矛盾环检测

题目重点：把可见的汇率 DFS 方向写成单快照训练契约，精确处理倒数和多跳查询；两日交易最优路径留待原题核证。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练输入为同一时间快照的 (from,to,rate)，表示 1 单位 from = rate 单位 to，rate>0；查询给金额、源币和目标币，返回精确 Fraction 或不可达 None。
假设所有同连通块路径乘积一致；若闭环推出互相矛盾的比率，训练实现拒绝输入。真实货币市场因买卖价差、时间变化和手续费可能有不同路径收益，不能套用该一致性模型。
题目称 3387 简化版但没有确认是否还有两天、最大化回报、重复兑换或原始币种约束；这些仅列追问，不假冒已知原题。

解题路线

每条报价建立正向乘 rate 与反向乘 1/r 的边；用 Fraction 解析字符串比率，避免浮点比较导致假阳性矛盾环。
对每个连通块 DFS/BFS：根权重 1，沿 u→v 的 rate 设 weight[v]=weight[u]×rate；已访问 v 再遇边时核对预期权重一致。
查询 s→t 若不在同连通块返回不可达，否则 amount×weight[t]/weight[s]；同币种且已出现于图返回原金额。大量查询时一次预处理比每次 DFS 更划算；若费率更新，需重新计算相关块或用带权并查集维护稳定快照。
若原题真的要求 LC3387 两日最大可兑换金额，应分别处理两日图、两日之间币种连接与最大化规则；若存在可盈利循环和不限兑换次数，目标可能无界。先从原题核对，不将该优化直接塞进单日一致图。

手动走一遍

1 USD=0.9 EUR，1 EUR=150 JPY，则 2 USD=270 JPY；1 JPY=1/135 USD。若再给 1 USD=130 JPY，则与既有路径 135 JPY/USD 矛盾，训练实现报错而非任取首条 DFS 路径。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Training variant: exact, internally consistent single-snapshot rates.

An edge (A, B, r) means one unit of A converts to r units of B. The posts do
not disclose exact original inputs, two-day rules, update semantics or cycles.
"""

from collections import defaultdict
from fractions import Fraction


class CurrencyGraph:
    def __init__(self, rates: list[tuple[str, str, str]]):
        graph: dict[str, list[tuple[str, Fraction]]] = defaultdict(list)
        for source, target, raw_rate in rates:
            rate = Fraction(raw_rate)
            if not source or not target or rate <= 0:
                raise ValueError("currency names and positive rates required")
            graph[source].append((target, rate))
            graph[target].append((source, 1 / rate))

        self.component: dict[str, str] = {}
        self.weight: dict[str, Fraction] = {}
        for root in graph:
            if root in self.component:
                continue
            self.component[root] = root
            self.weight[root] = Fraction(1)
            stack = [root]
            while stack:
                current = stack.pop()
                for neighbor, rate in graph[current]:
                    expected = self.weight[current] * rate
                    if neighbor in self.component:
                        if self.weight[neighbor] != expected:
                            raise ValueError("inconsistent conversion cycle")
                        continue
                    self.component[neighbor] = root
                    self.weight[neighbor] = expected
                    stack.append(neighbor)

    def convert(self, amount: str, source: str, target: str) -> Fraction | None:
        if source not in self.component or target not in self.component:
            return None
        if self.component[source] != self.component[target]:
            return None
        return Fraction(amount) * self.weight[target] / self.weight[source]


if __name__ == "__main__":
    graph = CurrencyGraph([("USD", "EUR", "9/10"), ("EUR", "JPY", "150")])
    assert graph.convert("2", "USD", "JPY") == 270
    assert graph.convert("1", "JPY", "USD") == Fraction(1, 135)

复杂度

V 币种、E 报价，建图与遍历 O(V+E) 时间和空间；一致权重建成后每次查询平均 O(1)。Fraction 的大整数乘除位复杂度另计；真实金额结算需另定精度与舍入。

易错点与追问

容易失分的边界

反向边误写同一个 rate 而非倒数。
多跳比率相加而非相乘。
同块不同路径矛盾时任意选 DFS 首路径却不声明策略。
用浮点精确相等比较环。
把‘LC3387 简化版’直接推断为完整两日规则。

继续深挖

费率每秒更新时怎样给查询提供一致快照？
若允许点差和手续费，最优路径如何建模？
两日换算的跨日币种连接和是否可重复交易怎样定义？
乘积环>1 且不限次交易时结果是否有界？