Frontend School

Reliable Fund Transfer Path

DSA
medium

Reliable Fund Transfer Path

Medium
Graph
BFS
DFS
Connectivity

Overview

At Groww, ensuring the reliability and security of financial transactions is paramount. Imagine a network of financial institutions where each connection has a 'reliability score' representing the trustworthiness of a transaction segment. Before initiating a large fund transfer, we need to verify if a path exists between the source and destination institutions where every segment of the path meets a minimum required reliability standard.

This problem challenges you to implement an algorithm that can determine if such a reliable path exists within a given financial network. It tests your ability to model and traverse graphs with specific edge conditions, a common scenario in complex systems like financial infrastructure.

What you need to do / Task

Implement the function canTransferFunds that takes the following parameters:

  1. n: The total number of financial institutions in the network.
  2. connections: A list of connections, where each connection [u, v, reliability] indicates a bidirectional link between institution u and institution v with a given reliability score.
  3. source: The starting institution for the fund transfer.
  4. destination: The target institution for the fund transfer.
  5. minReliability: The minimum reliability score that every segment of the transfer path must meet.

The function should return true if there exists at least one path from source to destination where all connections along the path have a reliability score greater than or equal to minReliability. Otherwise, it should return false.

Input & output

  • Input:

    • n: An integer representing the number of institutions (nodes). Institutions are 0-indexed.
    • connections: A number[][] where each inner array [u, v, reliability] denotes a bidirectional connection between institution u and institution v with a reliability score. reliability is an integer.
    • source: An integer representing the starting institution.
    • destination: An integer representing the target institution.
    • minReliability: An integer representing the minimum required reliability for all path segments.
  • Output:

    • A boolean value: true if a reliable path exists, false otherwise.

Clarifications

  • Institutions are 0-indexed, from 0 to n-1.
  • Connections are bidirectional. If [u, v, reliability] exists, funds can flow u -> v and v -> u with that reliability.
  • A path of zero length (source == destination) is considered a valid path if source and destination are the same. In this problem, source and destination will always be different.
  • The graph might be disconnected.
  • There might be multiple connections between the same pair of institutions. If so, only the one with the highest reliability (or any one meeting the criteria) matters for a direct segment.

Examples

1

Example 1

Input:

n = 5, connections = [[0,1,80],[1,2,90],[0,3,70],[3,4,95],[2,4,85]], source = 0, destination = 4, minReliability = 75

Output:

true

Note:

Path 0 -> 1 -> 2 -> 4 has segment reliabilities [80, 90, 85]. The minimum reliability along this path is 80, which is >= 75. So, a reliable path exists.

2

Example 2

Input:

n = 4, connections = [[0,1,60],[1,2,70],[2,3,80]], source = 0, destination = 3, minReliability = 85

Output:

false

Note:

The only path 0 -> 1 -> 2 -> 3 has segment reliabilities [60, 70, 80]. The minimum reliability along this path is 60, which is < 85. No other path exists, so no reliable path is found.

3

Example 3

Input:

n = 3, connections = [[0,1,90],[1,2,95],[0,2,70]], source = 0, destination = 2, minReliability = 80

Output:

true

Note:

Path 0 -> 1 -> 2 has segment reliabilities [90, 95]. The minimum is 90, which is >= 80. Although a direct connection 0 -> 2 exists with reliability 70 (which is < 80), a valid path through node 1 is found.

Constraints

Constraints & assumptions

  • 2 <= n <= 10^4
  • 0 <= connections.length <= 5 * 10^4
  • 0 <= u, v < n, u != v for any connection [u, v, reliability]
  • 1 <= reliability <= 100
  • 0 <= source, destination < n, source != destination
  • 1 <= minReliability <= 100
  • The graph can contain cycles.

Out of scope

  • Finding the path with the maximum possible minimum reliability.
  • Finding the shortest path in terms of number of hops.
  • Handling negative reliability scores or infinite reliability.

What interviewers evaluate

  • Ability to correctly model graph data structures (e.g., adjacency list).
  • Proficiency in implementing BFS or DFS traversal algorithms.
  • Correctly applying the minReliability constraint during graph traversal.
  • Handling graph connectivity and avoiding infinite loops (cycles).
  • Analysis of time and space complexity for the chosen approach.

Loading editor...