Frontend School

Minimize Transaction Fees Path

DSA
medium

Minimize Transaction Fees Path

Medium
Graph
Shortest Path
Dijkstra
Priority Queue
Logarithms

Overview

PhonePe processes millions of transactions daily across various payment gateways. Optimizing the transaction routing to minimize costs is crucial for both PhonePe and its users. This problem challenges you to find the most cost-effective path between two payment gateways in a network, considering percentage-based transaction fees.

What you need to do / Task

Implement a function minTransactionFeePath that determines the minimum total effective transaction fee to transfer funds from a startGateway to an endGateway within a given network of payment gateways and transaction routes.

The total effective fee for a path is calculated as follows: If a path consists of transactions with individual percentage fees f1, f2, ..., fk, the total effective fee is ((1 + f1/100) * (1 + f2/100) * ... * (1 + fk/100) - 1) * 100. Your goal is to minimize the (1 + f1/100) * ... * (1 + fk/100) product and then convert it back to a percentage.

If no path exists between the startGateway and endGateway, return -1.0.

Input & output

Function Signature: function minTransactionFeePath(numGateways: number, transactions: number[][], startGateway: number, endGateway: number): number

Parameters:

  • numGateways: An integer representing the total number of payment gateways, indexed from 0 to numGateways - 1.
  • transactions: A 2D array of integers, where each inner array [source, destination, feePercentage] represents a directed transaction route from source gateway to destination gateway with an associated feePercentage.
  • startGateway: An integer representing the index of the starting payment gateway.
  • endGateway: An integer representing the index of the ending payment gateway.

Return Value:

  • A number (float/double) representing the minimum total effective transaction fee percentage.
  • Return -1.0 if no path exists from startGateway to endGateway.

Clarifications

  • All feePercentage values are non-negative.
  • The graph can contain cycles.
  • A gateway can have multiple outgoing or incoming transactions.
  • If startGateway == endGateway, the minimum effective fee is 0.0, representing no transactions needed. This is true even if there are self-loops with fees.

Examples

1

Example 1

Input:

numGateways = 3, transactions = [[0,1,10],[1,2,5]], startGateway = 0, endGateway = 2

Output:

15.5

Note:

Path 0 -> 1 -> 2: (1 + 10/100) * (1 + 5/100) = 1.1 * 1.05 = 1.155. Effective fee = (1.155 - 1) * 100 = 15.5.

2

Example 2

Input:

numGateways = 4, transactions = [[0,1,10],[0,2,20],[1,3,5],[2,3,2]], startGateway = 0, endGateway = 3

Output:

15.5

Note:

Path 0 -> 1 -> 3: (1 + 10/100) * (1 + 5/100) = 1.1 * 1.05 = 1.155 (15.5% fee). Path 0 -> 2 -> 3: (1 + 20/100) * (1 + 2/100) = 1.2 * 1.02 = 1.224 (22.4% fee). The minimum is 15.5.

3

Example 3

Input:

numGateways = 2, transactions = [[0,1,10]], startGateway = 1, endGateway = 0

Output:

-1.0

Note:

There is no path from gateway 1 to gateway 0.

4

Example 4

Input:

numGateways = 2, transactions = [[0,0,5],[0,1,10]], startGateway = 0, endGateway = 0

Output:

0.0

Note:

Since startGateway is equal to endGateway, the minimum effective fee is 0.0 (no transactions needed).

Constraints

Constraints & assumptions

  • 1 <= numGateways <= 1000
  • 0 <= transactions.length <= numGateways * (numGateways - 1)
  • transactions[i] will always be of the form [source, destination, feePercentage]
  • 0 <= source, destination < numGateways
  • 0 <= feePercentage <= 100
  • 0 <= startGateway, endGateway < numGateways
  • The result should be accurate up to commonly accepted floating-point precision (e.g., 10^-5 or 10^-6).

What interviewers evaluate

  • Correctness and Optimality: The solution correctly identifies the minimum effective transaction fee path and uses an optimal algorithm for the given constraints.
  • Algorithm Selection & Justification: Clear understanding and justification of the chosen graph algorithm (e.g., Dijkstra's) and its suitability for multiplicative weights.
  • Code Structure & Readability: Well-organized, clean, and easy-to-understand code with appropriate data structures.
  • Edge Case Handling: Correctly handles scenarios like no path, and startGateway == endGateway.

Loading editor...