Best currency conversion rate across exchange quotes

Treat every currency as a node and every quote A -> B: r as a directed edge
with weight r. Quotes are one-way: a desk that sells EUR for USD at one rate
buys it back at a slightly worse one, and the reverse is only available if it
is quoted. Converting along a path multiplies the edge weights, so the best
rate from src to dst is the largest product over all paths.

Ask about direction early. If the interviewer says every quote also works
backwards at exactly 1 / r, the problem changes: in a consistent market
every path then gives the same rate, so any BFS/DFS answer is the answer,
and two paths with different products would form a money-making cycle.

Brute force. DFS over simple paths from src, carrying the running
product, and keep the best product seen at dst. This is correct, but the
number of simple paths can grow exponentially, so it only works on tiny
inputs. It is still a good thing to say out loud first, because it shows the
"max product over paths" model.

Why not plain Dijkstra? Dijkstra with a max-heap (multiply and maximize)
is the tempting answer. It is only correct when every edge weight is <= 1,
which is the multiplicative version of "no negative edges". Real quotes
include weights above 1 (USD -> JPY is about 150), so a node can be finalized
too early and a better path found later is ignored.

Optimal: Bellman-Ford in the multiplicative domain. Take logarithms:
maximizing r1 * r2 * ... * rk is the same as minimizing
-log r1 - log r2 - ... - log rk. That is a shortest-path problem with
possibly negative edges, which is exactly what Bellman-Ford solves. We do
not need the logs in code: keep best[c] = best rate found so far from
src to c, start with best[src] = 1, and relax every edge u -> v
with best[v] = max(best[v], best[u] * w).

Invariants:

• After round k, best[c] is at least the best rate over paths with at
  most k edges.
• With no arbitrage (no cycle whose product is above 1), the best path is
  simple, so n - 1 rounds are enough.
• If anything still improves in round n, there is an arbitrage cycle and
  "best rate" is unbounded. We report that instead of a number.

A small relative epsilon guards the comparisons, because products of floats
picked up along a cycle can come out as 1.0000000002 even when the market
is consistent.

from collections import defaultdict
from typing import Dict, List, Optional, Tuple

Quote = Tuple[str, str, float]
EPS = 1e-9


class ArbitrageError(Exception):
    """Raised when a cycle of conversions multiplies money (rate unbounded)."""


class CurrencyExchange:
    def __init__(self, quotes: List[Quote]) -> None:
        self.edges: List[Tuple[str, str, float]] = []
        self.currencies: set = set()
        for src, dst, rate in quotes:
            if rate <= 0:
                raise ValueError(f"rate must be positive: {src}->{dst}")
            self.edges.append((src, dst, rate))
            self.currencies.update((src, dst))

    def best_rate(self, src: str, dst: str) -> float:
        """Best rate for 1 unit of src in dst, or -1.0 if unreachable."""
        rate, _ = self.best_path(src, dst)
        return rate

    def best_path(self, src: str, dst: str) -> Tuple[float, List[str]]:
        if src not in self.currencies or dst not in self.currencies:
            return -1.0, []
        if src == dst:
            return 1.0, [src]

        best: Dict[str, float] = {src: 1.0}
        parent: Dict[str, Optional[str]] = {src: None}
        n = len(self.currencies)

        for round_no in range(n):
            changed = False
            for u, v, w in self.edges:
                if u not in best:
                    continue
                cand = best[u] * w
                if cand > best.get(v, 0.0) * (1 + EPS):
                    if round_no == n - 1:
                        raise ArbitrageError(f"arbitrage cycle reaches {v}")
                    best[v] = cand
                    parent[v] = u
                    changed = True
            if not changed:
                break

        if dst not in best:
            return -1.0, []
        path: List[str] = []
        node: Optional[str] = dst
        while node is not None:
            path.append(node)
            node = parent[node]
        return best[dst], path[::-1]


def brute_force(quotes: List[Quote], src: str, dst: str) -> float:
    """DFS over simple paths; exponential, used to cross-check."""
    graph: Dict[str, List[Tuple[str, float]]] = defaultdict(list)
    for a, b, r in quotes:
        graph[a].append((b, r))
    best = -1.0

    def dfs(node: str, product: float, seen: set) -> None:
        nonlocal best
        if node == dst:
            best = max(best, product)
            return
        for nxt, w in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                dfs(nxt, product * w, seen)
                seen.remove(nxt)

    dfs(src, 1.0, {src})
    return best

Let n be the number of currencies and m the number of quotes (one directed edge each).

• Building the exchange: O(m) time and space.
• best_rate / best_path: O(n * m) time in the worst case (at most n
  rounds over m edges, usually far fewer because of the early exit),
  O(n) extra space for best and parent.
• Brute force: O(n!) paths in the worst case; only for checking.

• Direct quote: [("USD","EUR",0.9)], USD -> EUR gives 0.9.
• No reverse quote: same quotes, EUR -> USD gives -1.
• Chain: [("GBP","USD",1.25), ("USD","JPY",150)], GBP -> JPY gives
  187.5, path GBP, USD, JPY.
• Indirect beats direct: [("A","B",2), ("B","C",3), ("A","C",5)],
  A -> C gives 6 through B.
• The case that breaks max-heap Dijkstra (a large weight late in the path):
  [("S","A",0.9), ("S","B",0.5), ("B","A",10), ("A","T",1)]. Dijkstra
  finalizes A at 0.9; the right answer for S -> T is 0.5 * 10 = 5.
• Unknown currency: best_rate("USD", "XYZ") gives -1.
• Disconnected currencies: [("A","B",2), ("C","D",3)], A -> D gives -1.
• Same currency: A -> A gives 1.
• Spread round trip is fine: [("USD","EUR",0.9), ("EUR","USD",1.1)]
  (cycle product 0.99), USD -> EUR gives 0.9.
• Arbitrage: [("A","B",2), ("B","C",2), ("C","A",0.5)] (cycle product
  2) raises ArbitrageError.

• Quotes work both ways at 1 / r. Add the reverse edges. In a
  consistent market every path gives the same rate, so one BFS/DFS (or a
  weighted union-find for many queries) is enough; the interesting part
  becomes checking consistency, since any two paths that disagree form an
  arbitrage cycle.
• Return the path, not just the rate. Keep a parent pointer whenever a
  relaxation wins, then walk back from dst (already in best_path).
• Many queries on a fixed rate table. Run Floyd-Warshall once in the
  multiplicative domain (best[i][j] = max(best[i][j], best[i][k] * best[k][j])), O(n^3) up front and O(1) per query. With only ~150
  world currencies this is cheap. If the quotes are known to be consistent
  (no spread), a single BFS/DFS or a weighted union-find gives every rate
  relative to a root in near O(m).
• Detect and report arbitrage. Run the n-th round of Bellman-Ford; any
  edge that still relaxes lies on or after a profitable cycle. Walk parent
  pointers n times to land inside the cycle, then follow them until a node
  repeats to print it.
• Limit the number of hops (each conversion costs a fee or a call to a
  partner). Run exactly k rounds of Bellman-Ford, relaxing from a copy of
  the previous round's values, like "cheapest flights within k stops".

Mid-level (L4)

• Models currencies as a directed graph and asks whether quotes work in
  reverse.
• Gets a working BFS/DFS that multiplies rates along a path and returns -1
  when there is no path.
• Handles the same-currency and unknown-currency cases.

Senior (L5)

• Notices that "best" means maximizing a product over several paths, and
  explains why plain max-heap Dijkstra is wrong once weights exceed 1.
• Uses the log transform to arrive at Bellman-Ford and states the
  no-arbitrage assumption it depends on.
• Discusses floating-point comparisons and returns the conversion path.

Staff (L6+)

• Separates query patterns: Bellman-Ford per query versus Floyd-Warshall or
  a precomputed table for many queries, and weighted union-find when quotes
  are consistent.
• Detects arbitrage and explains what a real exchange should do with it
  (reject the quote set, alert, or cap the result).
• Talks about live rate updates, stale quotes, money as decimals rather than
  floats in the final settlement, and how the service would cache results.