Currency Exchange Rate Lookup (Verbal Algorithm Round)

Format. One report of a four-round onsite, posted in September 2026. The algorithm round needs no code: you explain the approach and its complexity out loud. One reply says they heard back the same day.

The task. You get an array of exchange rates such as ['USD', 'GBP', 0.77], meaning 1 USD is worth 0.77 GBP, plus a source currency and a target currency. Find the exchange rate from the source to the target.

Ask before you answer (the report doesn't say):

• Can you trade in reverse? If ['USD', 'GBP', 0.77] also means 1 GBP = 1/0.77 USD, every rate is a two-way edge.
• What if there is no route, or a currency never appears? Return None, -1, or raise?
• Is it one query, or many queries against the same rates? Many queries change the best structure.
• Can two routes give different rates, or the same pair appear twice with different rates? Real quotes are not perfectly consistent.
• Can a rate be zero or negative? (The code below rejects both.)
• Are floating-point rates acceptable, or does it need exact arithmetic?

Walkthrough (ours, not from the report). We ran every function below against randomized rate tables and a brute-force check, including a 5,000-currency chain.

1. Model it as a graph. Currencies are nodes. A rate [a, b, r] is an edge a → b with weight r, and, if reverse trades are allowed, b → a with weight 1/r. Converting along a route multiplies the weights, so the answer is the product along any path from source to target.

2. One query: search from the source. BFS (or an iterative DFS; a recursive one can hit Python's recursion limit on long chains), carrying the running product. O(V + E) time and space for V currencies and E rates. It returns the first route it finds and does not check that other routes agree.

from collections import defaultdict, deque


def build_graph(rates):
    """rates: [[from, to, rate], ...] meaning 1 unit of `from` buys `rate` units of `to`."""
    graph = defaultdict(list)
    for a, b, r in rates:
        if r <= 0:
            raise ValueError(f"rate must be positive: {a}->{b} = {r}")
        graph[a].append((b, r))
        graph[b].append((a, 1 / r))          # the reverse trade
    return graph


def convert(rates, source, target):
    """Rate from source to target by BFS, multiplying along the path. None if unreachable.
    Returns the first route found: it does not check that other routes agree."""
    graph = build_graph(rates)
    if source not in graph or target not in graph:
        return None
    if source == target:
        return 1.0
    seen = {source}
    queue = deque([(source, 1.0)])
    while queue:
        cur, acc = queue.popleft()
        for nxt, r in graph[cur]:
            if nxt == target:
                return acc * r
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, acc * r))
    return None

3. Many queries: weighted union-find. Store, for each currency, its rate to its set's root; the rate from a to b is to_root[a] / to_root[b]. With path compression and union by size, each query costs nearly constant amortized time (inverse Ackermann) after building. The same structure catches inconsistent input: if a new rate connects two currencies already connected, the rate it implies must match. For a small, fixed set of currencies, precomputing every pair with Floyd–Warshall in O(V³) is another option.

class RateBook:
    """Many queries: weighted union-find. to_root[x] = units of root per unit of x."""

    def __init__(self, rates):
        self.parent, self.to_root, self.size = {}, {}, {}
        for a, b, r in rates:
            if r <= 0:
                raise ValueError(f"rate must be positive: {a}->{b} = {r}")
            self._union(a, b, r)

    def _find(self, x):
        path = []
        while self.parent[x] != x:               # iterative: no recursion limit on long chains
            path.append(x)
            x = self.parent[x]
        root, acc = x, 1.0
        for node in reversed(path):              # compress, keeping each node's product to root
            acc *= self.to_root[node]
            self.to_root[node], self.parent[node] = acc, root
        return root

    def _union(self, a, b, r):                   # 1 a = r b
        for x in (a, b):
            if x not in self.parent:
                self.parent[x], self.to_root[x], self.size[x] = x, 1.0, 1
        ra, rb = self._find(a), self._find(b)
        if ra == rb:                             # already connected: the new rate must agree
            implied = self.to_root[a] / self.to_root[b]
            if abs(implied / r - 1) > 1e-9:
                raise ValueError(f"inconsistent rates: {a}->{b} is {r}, other routes give {implied}")
            return
        rate_ra_to_rb = r * self.to_root[b] / self.to_root[a]
        if self.size[ra] > self.size[rb]:        # union by size: attach the smaller tree
            ra, rb, rate_ra_to_rb = rb, ra, 1 / rate_ra_to_rb
        self.parent[ra], self.to_root[ra] = rb, rate_ra_to_rb
        self.size[rb] += self.size[ra]

    def rate(self, source, target):
        if source not in self.parent or target not in self.parent:
            return None
        if self._find(source) != self._find(target):
            return None
        return self.to_root[source] / self.to_root[target]

4. If routes can disagree. With two-way trades at reciprocal rates, any disagreement is an arbitrage loop: go one way, come back the other, and end up with more than you started with. So "the best rate" is not defined; the right answer is to flag the data, which the union-find above does. With one-way quotes (a bid in one direction, an ask in the other), the best rate is the largest product over all routes. Taking -log of each rate turns that into a shortest path: Bellman-Ford in O(V·E). A negative cycle is an arbitrage loop; only if it can reach the target is the best rate unbounded, so the code marks everything a negative cycle can reach before answering.

def best_rate(quotes, source, target):
    """One-way quotes only (e.g. bid/ask, no automatic reverse trade): the best product over
    all routes, via Bellman-Ford on -log(rate). Returns (rate, unbounded). If an arbitrage
    cycle reachable from source can also reach target, the rate is unbounded: (None, True)."""
    import math
    nodes = {c for a, b, _ in quotes for c in (a, b)}
    if source not in nodes or target not in nodes:
        return None, False
    if any(r <= 0 for _, _, r in quotes):
        raise ValueError("rates must be positive")
    edges = [(a, b, -math.log(r)) for a, b, r in quotes]
    dist = {n: math.inf for n in nodes}
    dist[source] = 0.0
    for _ in range(len(nodes) - 1):
        for a, b, w in edges:
            if dist[a] + w < dist[b]:
                dist[b] = dist[a] + w
    for _ in range(len(nodes)):                   # anything a negative cycle can reach -> -inf
        for a, b, w in edges:
            if dist[a] != math.inf and (dist[a] == -math.inf or dist[a] + w < dist[b] - 1e-12):
                dist[b] = -math.inf
    if dist[target] == -math.inf:
        return None, True
    return (None if dist[target] == math.inf else math.exp(-dist[target])), False

5. Things to say out loud. State the graph model and your reverse-trade assumption before any algorithm. Give the complexity of each option, and say when you would precompute instead of searching per query. Mention floating-point error when rates are multiplied along long routes: decimal.Decimal reduces drift for rates given as decimals, but a reverse trade such as 1/3 still rounds; fractions.Fraction is exact.