Katkat
Back

Solve listed algorithm problems

RipplingSoftware Engineer · HR Screen
HardSoftware EngineerHR ScreenCoding & Algorithms

Last updated

This problem tests your ability to model exchange rates as a graph and use path-finding algorithms to detect profitable arbitrage opportunities.

Arbitrage Detection

Given a list of currency exchange rates, where each rate is a tuple (source_currency, target_currency, rate), determine if there exists a sequence of trades that results in a net gain.

Starting with 1 unit of a base currency, if you trade through a sequence of currencies, you end up with the product of the rates. An arbitrage opportunity exists if you can return to the original currency with more than 1 unit.

Function Signature

def can_make_profit(rates: List[Tuple[str, str, float]]) -> bool

Constraints

  • The number of currencies is up to 100.
  • Rates are positive floating-point numbers.
  • A sequence of trades must contain at least one exchange.

Example 1

Input: [('USD', 'EUR', 0.9), ('EUR', 'GBP', 0.8), ('GBP', 'USD', 1.5)] Output: False Explanation: 0.9 * 0.8 * 1.5 = 1.08. Wait, this example results in 1.08, so True.

Example 2

Input: [('USD', 'EUR', 0.5), ('EUR', 'USD', 1.5)] Output: False Explanation: 0.5 * 1.5 = 0.75, which is less than 1.

Edge Cases

  • Disconnected graph components.
  • Rates exactly equal to 1.0.
  • Cycles of length 2.

Hints

Hint 1

Transform the multiplication of rates into an addition problem by taking the negative logarithm of each rate.

Hint 2

A product of rates > 1 becomes a sum of negative logs < 0.

Hint 3

Use the Bellman-Ford algorithm or SPFA to detect if there is a negative weight cycle in the transformed graph.

Follow-up questions

  • How would you reconstruct the actual sequence of trades that leads to the profit?
  • If the number of currencies grows to 10,000, how would your approach change?
  • How do you account for transaction fees (e.g., a fixed percentage deducted per trade)?