rippling·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Rippling SWE interview that went deep into currency exchange as a graph problem. The question sounds like a finance puzzle but it's really testing whether you can model multi-day path optimization and reason about cycles under time pressure.

Questions Asked (1)

You start with a fixed amount in some currency. You're given exchange rates for two consecutive days, each as a list of directed conversion edges with rates. You can do any number of conversions on day 1, then any number on day 2. What's the maximum amount you can end up with in a target currency after both days? Walk through how you'd model it, handle arbitrage cycles, and analyze the time complexity.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

I went straight to Bellman-Ford in my head because 'cycles' and 'rates' screamed arbitrage detection, but the twist is you're maximizing a product along a path, not minimizing a sum.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where currencies are nodes and exchange rates are directed edges with weights equal to the negative logarithm of the rate. Then, for each day, compute the maximum amount reachable from the starting currency using a modified shortest path algorithm that handles negative cycles (arbitrage). Finally, combine the results from both days to find the maximum final amount in the target currency.

Pro tip: Emphasize that arbitrage cycles can be exploited by converting to the cycle currency, looping, and converting back, but only if the cycle is reachable and can reach the target. Also, mention that the order of days matters and you must optimize over all possible intermediate currencies after day 1.

1. Model as Graph

Represent currencies as nodes and exchange rates as directed edges with weights = -log(rate). This converts multiplicative rates to additive costs, so maximizing amount becomes minimizing cost.

2. Handle Arbitrage Cycles

Detect negative cycles (product of rates > 1) using Bellman-Ford. For any currency reachable from a negative cycle, set its maximum amount to infinity (or a very large number) because you can exploit the cycle to increase money arbitrarily.

3. Compute Max Amounts for Each Day

For day 1, compute the maximum amount of each currency starting from the initial amount. For day 2, compute the maximum amount of each currency starting from 1 unit (or from the amounts after day 1). Use Bellman-Ford with negative cycle handling.

4. Combine Days

For each currency C, the maximum amount after day 2 is max over C of (max amount of C after day 1) * (max amount of target from C on day 2). Take the maximum over all C.

5. Analyze Complexity

Time complexity: O(V * E) per day for Bellman-Ford, where V is number of currencies and E is number of edges. Space: O(V) for distances. Mention that if negative cycles exist, additional O(V*E) to propagate infinities.

Key Points to Mention

Use of negative logarithm to convert multiplication to addition and enable shortest path algorithms.
Bellman-Ford algorithm for detecting negative cycles and computing shortest paths with negative edges.
Handling of arbitrage cycles: if a negative cycle is reachable from the start and can reach the target, the answer is unbounded (or effectively infinite).
Dynamic programming over two days: compute optimal amounts after day 1, then use those as starting amounts for day 2.
Time complexity: O(V * E) per day, which is efficient for typical currency graphs.
Edge cases: unreachable target, no arbitrage, multiple cycles, and the need to consider all intermediate currencies.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.