Maximize Amount After Two Days of Conversions
Asked at Rippling
Problem
You are given a list of currency conversions represented as directed edges with exchange rates. Starting with a given amount of a source currency, you must perform conversions over at most two days, where each day you can convert along any path in the graph. The goal is to maximize the final amount of the target currency by choosing the optimal sequence of conversions.
Asked At
| Company | Difficulty | |
|---|---|---|
| Rippling | MEDIUM | View all Rippling questions → |
How to Think About It
Brute force: try every possible two-step conversion path and track the maximum result.
Model currencies as nodes and conversions as directed weighted edges where the weight is the exchange rate.
Use DFS or BFS from the source currency to find the best single-day conversion to any intermediate currency.
For each intermediate currency reachable on day one, perform a second BFS/DFS to the target on day two and multiply the rates.
Optimal: run two graph traversals — one from source and one reversed from target — then combine results in O(V + E) time.
Optimal Approach
Build a directed graph where each node is a currency and each edge stores the exchange rate. Perform a DFS or BFS from the source currency to compute the maximum amount reachable after one day for every intermediate currency. Then perform a second traversal from each intermediate currency (or equivalently a reversed BFS from the target) to find the best rate to the target. Multiply the day-one and day-two rates for each intermediate currency and take the maximum. This two-pass approach avoids enumerating all pairs and runs in O(V + E) time.
What Trips People Up in Real Interviews
Clarify whether cycles in the graph are allowed and whether you can revisit currencies across days.
Watch out for floating-point precision — compare using a small epsilon rather than exact equality.
Make sure you handle the case where no valid conversion path exists (return -1 or 0 as specified).
Discuss whether the graph is guaranteed to be connected and what the edge case of a single-node graph looks like.
Explain the time complexity clearly: two graph traversals give O(V + E) which is efficient for the constraints.
Solution Code
from collections import defaultdict
def maxAmount(initialCurrency, pairs, rates):
graph = defaultdict(list)
for (a, b), r in zip(pairs, rates):
graph[a].append((b, r))
graph[b].append((a, 1.0 / r))
def bfs(start):
visited = {}
queue = [(start, 1.0)]
visited[start] = 1.0
while queue:
node, amt = queue.pop(0)
for nei, rate in graph[node]:
new_amt = amt * rate
if nei not in visited or new_amt > visited[nei]:
visited[nei] = new_amt
queue.append((nei, new_amt))
return visited
day1 = bfs(initialCurrency)
best = 0.0
for intermediate, amt1 in day1.items():
day2 = bfs(intermediate)
if initialCurrency in day2:
best = max(best, amt1 * day2[initialCurrency])
return bestFrequently Asked Questions
What is the Maximize Amount After Two Days of Conversions problem?
You are given a list of currency conversions represented as directed edges with exchange rates. Starting with a given amount of a source currency, you must perform conversions over at most two days, where each day you can convert along any path in the graph. The goal is to maximize the final amount of the target currency by choosing the optimal sequence of conversions.
How do you solve Maximize Amount After Two Days of Conversions?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximize Amount After Two Days of Conversions?
Maximize Amount After Two Days of Conversions is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Maximize Amount After Two Days of Conversions?
- Clarify whether cycles in the graph are allowed and whether you can revisit currencies across days.
- Watch out for floating-point precision — compare using a small epsilon rather than exact equality.
- Make sure you handle the case where no valid conversion path exists (return -1 or 0 as specified).
- Discuss whether the graph is guaranteed to be connected and what the edge case of a single-node graph looks like.
- Explain the time complexity clearly: two graph traversals give O(V + E) which is efficient for the constraints.