Maximize Amount After Two Days of Conversions

Maximize Amount After Two Days of Conversions

What is this problem about?

In this problem, you start with a given amount of an initial currency. You are provided with exchange rates for pairs of currencies on Day 1, and a different set of exchange rates for pairs of currencies on Day 2. You can perform any number of currency conversions on Day 1, hold the resulting currency overnight, and then perform any number of conversions on Day 2. Your goal is to maximize the final amount of your initial currency at the end of Day 2.

Why is this asked in interviews?

This is a fantastic Graph Traversal / Shortest Path problem disguised as financial arbitrage. Interviewers ask it to test your ability to model real-world networks using directed graphs with weighted edges (exchange rates). It evaluates your understanding of Breadth-First Search (BFS) or Bellman-Ford algorithms to find the most profitable path through a network of multipliers.

Algorithmic pattern used

This problem leverages a Two-Phase Graph Traversal (BFS or DFS) pattern.

1. Day 1: Build a directed graph where nodes are currencies and edge weights are exchange rates. Starting from your initial currency with amount 1.0, run a BFS/DFS to find the maximum possible amount you can obtain for every other currency. Store these maximums in a Hash Map.
2. Day 2: Build a new directed graph using Day 2's exchange rates. Now, instead of starting from one currency, you treat every currency you acquired on Day 1 as a starting point with its respective Day 1 max amount. Run a BFS/DFS from each of these states to find the maximum possible amount of the original initial currency you can convert back to.

Example explanation

Initial: 100 USD. Day 1 Rates: USD -> EUR (0.9), EUR -> GBP (0.8). Day 2 Rates: GBP -> JPY (1.2), JPY -> USD (1.5), EUR -> USD (1.1).

• Day 1 Traversal:
  • USD: 100
  • EUR: $100 \times 0.9 = 90$
  • GBP: $90 \times 0.8 = 72$
• Day 2 Traversal:
  • Start from EUR (90). Convert back: $90 \times 1.1 = 99$ USD.
  • Start from GBP (72). Convert GBP -> JPY -> USD: $72 \times 1.2 \times 1.5 = 129.6$ USD.
  • Start from USD (100). Do nothing: 100 USD. The maximum ending amount is 129.6 USD.

Common mistakes candidates make

A common error is assuming that the best Day 1 currency is simply the one with the highest absolute numerical value. You must evaluate the entire path back on Day 2. Another mistake is ignoring cycles. While typical arbitrage problems involve negative-weight cycles (infinite money loops), these problems usually constrain the graph to be a tree or a DAG per day, meaning standard BFS/DFS with a visited set is sufficient and prevents infinite loops.

Interview preparation tip

When tackling currency conversion interview problems, always represent the data as a Hash Map of Hash Maps: Map<String, Map<String, Double>> graph. This allows for ultra-fast neighbor lookups. If the problem guarantees no infinite arbitrage loops, a standard BFS keeping track of the current_amount * rate is perfectly safe and highly performant.