Maximize Amount After Two Days of Conversions

You start with exactly 1.0 unit of the currency initialCurrency.

On day 1 you may make any number of conversions (including none) using the pairs pairs1 and rates rates1. The entry pairs1[i] = [from, to] means one unit of from buys rates1[i] units of to. You may also convert the other way: one unit of to buys 1 / rates1[i] units of from.

On day 2 you may again make any number of conversions using pairs2 and rates2, with the same rules. Day 1 rates cannot be used on day 2.

At the end of day 2 you must hold initialCurrency again. Return the largest amount of it you can end with.

The rates on each day are consistent: there are no contradictions and no cycles, so on a given day there is at most one way to get from one currency to another. Answers within 10⁻⁵ of the expected value are accepted.

Treat each day as a graph: currencies are nodes, and each pair is an edge with weight rate one way and 1 / rate the other. Following a path multiplies the weights.

The two days only meet at one moment: the currency you hold at the end of day 1. Call it c. The best plan through c is "get as much c as possible on day 1" times "convert c back to the start currency on day 2". So you need two tables:

• day1[c]: how much c one unit of the start currency buys on day 1.
• day2[c]: how much c one unit of the start currency buys on day 2. Converting c back gives 1 / day2[c] per unit.

The answer is the largest day1[c] / day2[c] over every currency reachable on both days. The start currency itself is always in both tables with value 1, which covers doing nothing. Because neither graph has cycles, each table is a single DFS or BFS from the start currency.

from collections import defaultdict


def _rates_from(start: str, pairs: list[list[str]], rates: list[float]) -> dict[str, float]:
    graph = defaultdict(list)
    for (a, b), r in zip(pairs, rates):
        graph[a].append((b, r))
        graph[b].append((a, 1 / r))
    amount = {start: 1.0}
    stack = [start]
    while stack:
        cur = stack.pop()
        for nxt, r in graph[cur]:
            if nxt not in amount:
                amount[nxt] = amount[cur] * r
                stack.append(nxt)
    return amount


def max_amount(
    initial_currency: str,
    pairs1: list[list[str]],
    rates1: list[float],
    pairs2: list[list[str]],
    rates2: list[float],
) -> float:
    day1 = _rates_from(initial_currency, pairs1, rates1)
    day2 = _rates_from(initial_currency, pairs2, rates2)
    # Hold c overnight: day1[c] units, each worth 1 / day2[c] at the end.
    return max(day1[c] / day2[c] for c in day1 if c in day2)

function ratesFrom(start, pairs, rates) {
  const graph = new Map();
  const add = (a, b, r) => {
    if (!graph.has(a)) graph.set(a, []);
    graph.get(a).push([b, r]);
  };
  pairs.forEach(([a, b], i) => {
    add(a, b, rates[i]);
    add(b, a, 1 / rates[i]);
  });
  const amount = new Map([[start, 1]]);
  const stack = [start];
  while (stack.length) {
    const cur = stack.pop();
    for (const [next, r] of graph.get(cur) ?? []) {
      if (!amount.has(next)) {
        amount.set(next, amount.get(cur) * r);
        stack.push(next);
      }
    }
  }
  return amount;
}

function maxAmount(initialCurrency, pairs1, rates1, pairs2, rates2) {
  const day1 = ratesFrom(initialCurrency, pairs1, rates1);
  const day2 = ratesFrom(initialCurrency, pairs2, rates2);
  let best = 0;
  for (const [c, amt] of day1) {
    // Hold c overnight: amt units, each worth 1 / day2[c] at the end.
    if (day2.has(c)) best = Math.max(best, amt / day2.get(c));
  }
  return best;
}

Say the decomposition clearly: "the only thing that links the days is the currency I hold overnight, so I'll compute the best amount of every currency after day 1 and the best way back from every currency on day 2." That turns a confusing two-phase problem into two independent traversals.

Then point out the trick for day 2: instead of searching from every currency to the start, search once from the start and take reciprocals. Interviewers like hearing that you used the no-cycles guarantee to justify a single DFS, and that you would switch to Bellman-Ford if the graphs could have several paths.