Frontend School

Optimal Asset Conversion Path

DSA
medium

Optimal Asset Conversion Path

Medium
Graph
Shortest Path
Dijkstra
Financial

Overview

In the dynamic world of financial trading, clients often need to convert one asset into another, sometimes requiring multiple intermediate conversions through different exchanges or brokers. Each direct conversion comes with a transaction fee. To maximize returns, it's crucial to find the sequence of conversions that incurs the minimum total fee. This problem challenges you to model and solve this scenario, identifying the optimal path for asset conversion.

What you need to do / Task

Your task is to implement a function that calculates the minimum total transaction fee required to convert a startAsset to an endAsset.

  1. Model the problem: Represent the assets and exchange rates as a graph where assets are nodes and direct conversions are weighted edges (weights being the fees).
  2. Find the shortest path: Implement an algorithm to determine the path with the minimum cumulative fee from the startAsset to the endAsset.
  3. Handle edge cases: Your solution should correctly handle scenarios where the startAsset is the same as the endAsset, or where no conversion path exists between the given assets.

Input & output

Function Signature:

function findOptimalConversionPath(
  assets: string[],
  exchangeRates: [string, string, number][],
  startAsset: string,
  endAsset: string
): number
  • assets: An array of strings, where each string is the unique identifier for an asset (e.g., "INR", "USD", "BTC"). These are all possible nodes in your graph.
  • exchangeRates: An array of tuples (or arrays) [asset1, asset2, fee]. Each tuple represents a direct conversion from asset1 to asset2 with a non-negative fee. This implies a directed edge from asset1 to asset2 with the specified fee as its weight.
  • startAsset: A string representing the asset you initially possess.
  • endAsset: A string representing the asset you wish to obtain.

Returns:

  • A number representing the minimum total transaction fee to convert startAsset to endAsset. Return -1 if no path exists from startAsset to endAsset.

Clarifications

  • Additive Fees: The total fee for a conversion path is the sum of individual fees for each direct conversion along that path.
  • Direct Conversions: A direct conversion [A, B, fee] means you can convert A to B. It does not imply you can convert B to A, unless explicitly specified by another entry [B, A, anotherFee] in exchangeRates.
  • Self-Conversion: If startAsset is the same as endAsset, the fee is 0.
  • Valid Inputs: Assume all startAsset and endAsset strings are present in the assets array, and all asset1/asset2 in exchangeRates are also valid assets.

Examples

1

Example 1

Input:

assets = ["INR", "USD", "EUR", "GBP"], exchangeRates = [["INR", "USD", 10], ["USD", "EUR", 5], ["EUR", "GBP", 7], ["INR", "EUR", 18]], startAsset = "INR", endAsset = "GBP"

Output:

22

Note:

Path 1: INR -> USD (10) -> EUR (5) -> GBP (7). Total fee = 10 + 5 + 7 = 22. Path 2: INR -> EUR (18) -> GBP (7). Total fee = 18 + 7 = 25. The minimum fee is 22.

2

Example 2

Input:

assets = ["INR", "USD", "JPY"], exchangeRates = [["INR", "USD", 10]], startAsset = "INR", endAsset = "JPY"

Output:

-1

Note:

There is no path to convert INR to JPY. Only INR to USD is possible.

3

Example 3

Input:

assets = ["INR", "USD"], exchangeRates = [["INR", "USD", 10]], startAsset = "INR", endAsset = "INR"

Output:

0

Note:

The start asset is the same as the end asset, so no conversion is needed, and the fee is 0.

Constraints

Constraints & assumptions

  • 1 <= assets.length <= 100 (Number of distinct assets)
  • 0 <= exchangeRates.length <= 1000 (Number of direct conversion routes)
  • 0 <= fee <= 1000 for each conversion. Fees are non-negative integers.
  • startAsset and endAsset will always be valid strings present in the assets array.
  • Asset names are unique strings (e.g., "INR", "USD").
  • The graph represented by assets and exchange rates may be disconnected.
  • No negative cycles will be present (as fees are non-negative).

Out of scope

  • Handling real-time market data or fluctuating exchange rates.
  • Consideration of transaction volume limits or liquidity.
  • Complex fee structures (e.g., percentage-based fees, tier-based fees).

What interviewers evaluate

  • Algorithmic Correctness: Correct application of a shortest path algorithm to find the minimum fee.
  • Efficiency: Optimal time and space complexity for graph construction and traversal.
  • Edge Case Handling: Robustness in handling scenarios like no path, or start and end assets being identical.
  • Code Quality: Clarity, readability, and maintainability of the solution.

Loading editor...