Frontend School

Optimized Portfolio Conversion with Fee Budget

DSA
hard

Optimized Portfolio Conversion with Fee Budget

Hard
Graph
Shortest Path
Dijkstra
Dynamic Programming

Overview

Groww is committed to providing users with efficient financial tools. A common need is to convert one asset into another, which may involve a series of intermediate trades. Each trade incurs both a transaction fee and a time delay (e.g., for settlement). This problem challenges you to find the most time-efficient sequence of trades to convert a starting asset into a target asset, while ensuring the total transaction fees incurred do not exceed a specified budget. This capability is crucial for optimizing portfolio rebalancing and ensuring cost-effective asset management for our users.

What you need to do / Task

Implement a function minTimeAssetConversion that determines the minimum total time required to convert a startAsset to a targetAsset through a series of trades. The cumulative feeCost of all trades in the path must not exceed maxFeeBudget.

  • The conversion can involve multiple intermediate assets.
  • You must find the path that minimizes the total time cost.
  • If multiple paths yield the same minimum time, any such path is acceptable (you just need to return the minimum time).
  • If no valid path exists within the maxFeeBudget, return -1.

Input & output

Function Signature: function minTimeAssetConversion(numAssets: number, trades: number[][], startAsset: number, targetAsset: number, maxFeeBudget: number): number

Parameters:

  • numAssets: An integer representing the total number of distinct assets, indexed from 0 to numAssets - 1.
  • trades: An array of arrays, where each inner array [u, v, time, fee] represents a possible direct trade: converting asset u to asset v.
    • u: The source asset (integer 0 to numAssets - 1).
    • v: The destination asset (integer 0 to numAssets - 1).
    • time: The time cost (integer) incurred for this trade.
    • fee: The transaction fee (integer) incurred for this trade.
  • startAsset: The initial asset (integer 0 to numAssets - 1).
  • targetAsset: The desired final asset (integer 0 to numAssets - 1).
  • maxFeeBudget: An integer representing the maximum total transaction fee allowed for the entire conversion path.

Return Value:

  • A number representing the minimum total time cost to convert startAsset to targetAsset within the maxFeeBudget.
  • Return -1 if no such valid conversion path exists.

Clarifications

  • A trade can only happen from u to v if specified in trades. Trades are one-way.
  • It's possible for there to be multiple trades between the same two assets u and v (e.g., different brokers offering different time/fee combinations). You should consider all such options.
  • The startAsset and targetAsset can be the same. In this case, if startAsset === targetAsset and maxFeeBudget >= 0, the minimum time is 0.
  • Time and fee costs are always non-negative integers.

Examples

1

Example 1

Input:

numAssets = 3, trades = [[0, 1, 10, 5], [1, 2, 8, 3]], startAsset = 0, targetAsset = 2, maxFeeBudget = 10

Output:

18

Note:

Path 0 -> 1 -> 2: Total time = 10 + 8 = 18. Total fee = 5 + 3 = 8. Since 8 <= 10, this path is valid and its time is 18.

2

Example 2

Input:

numAssets = 4, trades = [[0, 1, 10, 5], [0, 2, 2, 8], [1, 3, 15, 2], [2, 3, 5, 6]], startAsset = 0, targetAsset = 3, maxFeeBudget = 10

Output:

25

Note:

Path 0 -> 1 -> 3: Total time = 10 + 15 = 25. Total fee = 5 + 2 = 7. (Valid) Path 0 -> 2 -> 3: Total time = 2 + 5 = 7. Total fee = 8 + 6 = 14. (Invalid, fee 14 > budget 10) The minimum valid time is 25.

3

Example 3

Input:

numAssets = 3, trades = [[0, 1, 10, 5], [1, 2, 8, 3]], startAsset = 0, targetAsset = 2, maxFeeBudget = 7

Output:

-1

Note:

The only path 0 -> 1 -> 2 has a total fee of 8, which exceeds the maxFeeBudget of 7. No valid path exists.

4

Example 4

Input:

numAssets = 3, trades = [[0, 2, 20, 10], [0, 1, 5, 2], [1, 2, 5, 3]], startAsset = 0, targetAsset = 2, maxFeeBudget = 10

Output:

10

Note:

Path 0 -> 2: Total time = 20, total fee = 10. (Valid) Path 0 -> 1 -> 2: Total time = 5 + 5 = 10, total fee = 2 + 3 = 5. (Valid) The minimum valid time among these is 10.

Constraints

Constraints & assumptions

  • 1 <= numAssets <= 100
  • 0 <= trades.length <= 5000
  • Each trade in trades is [u, v, time, fee] where:
    • 0 <= u, v < numAssets
    • 0 <= time <= 1000
    • 0 <= fee <= 100
  • 0 <= startAsset, targetAsset < numAssets
  • 0 <= maxFeeBudget <= 500
  • The graph may contain cycles.
  • All assets are distinct and represented by unique integers.

What interviewers evaluate

  • Correctness and Optimality: The solution correctly identifies the minimum time adhering to the fee budget, handling all edge cases (e.g., no path, start/target same).
  • Algorithm Design: Demonstration of strong graph algorithm knowledge, specifically shortest path algorithms with resource constraints, and appropriate data structures.
  • Time and Space Complexity: Analysis of the solution's performance and ability to optimize within given constraints.
  • Code Quality: Clarity, readability, modularity, and maintainability of the implemented code.

Loading editor...