Frontend School

Minimum Hops in Payment Network

DSA
easy

Minimum Hops in Payment Network

Easy
Graph
Shortest Path
BFS

Overview

Razorpay processes millions of transactions daily, and the efficiency of our payment routing network is paramount. A payment might traverse several internal processing nodes before reaching its final destination. Optimizing these routes helps reduce latency and ensures a smooth customer experience. This problem asks you to find the most direct path (in terms of number of connections, or 'hops') a payment takes through a simplified network of processing nodes.

What you need to do / Task

Implement a function minHops that determines the minimum number of direct connections (hops) required for a payment to travel from a startNode to an endNode within a given payment processing network. If no path exists between the two nodes, the function should indicate this.

Input & output

Function Signature:

function minHops(n: number, edges: number[][], startNode: number, endNode: number): number

Parameters:

  • n: An integer representing the total number of processing nodes in the network. Nodes are 0-indexed, from 0 to n-1.
  • edges: An array of arrays, where each inner array [u, v] represents a direct, undirected connection (an edge) between node u and node v.
  • startNode: An integer representing the source node from which the payment originates.
  • endNode: An integer representing the destination node where the payment needs to arrive.

Return Value:

  • An integer representing the minimum number of hops (edges traversed) from startNode to endNode. If startNode is the same as endNode, the return value should be 0. If no path exists, return -1.

Clarifications

  • The network is undirected: if there's an edge from u to v, there's also an edge from v to u.
  • All edges have a 'weight' of 1, meaning each direct connection counts as one hop.
  • The startNode and endNode can be the same, in which case 0 hops are needed.

Examples

1

Example 1

Input:

n = 5, edges = [[0,1],[0,2],[1,3],[2,4]], startNode = 0, endNode = 3

Output:

2

Note:

The shortest path from node 0 to node 3 is 0 -> 1 -> 3, which requires 2 hops.

2

Example 2

Input:

n = 4, edges = [[0,1],[2,3]], startNode = 0, endNode = 2

Output:

-1

Note:

Nodes 0 and 2 are in disconnected components; there is no path between them.

3

Example 3

Input:

n = 6, edges = [[0,1],[1,2],[2,3],[0,4],[4,5],[5,3]], startNode = 0, endNode = 3

Output:

3

Note:

One shortest path is 0 -> 1 -> 2 -> 3 (3 hops). Another is 0 -> 4 -> 5 -> 3 (3 hops).

4

Example 4

Input:

n = 3, edges = [[0,1],[1,2]], startNode = 0, endNode = 0

Output:

0

Note:

Starting and ending at the same node requires 0 hops.

Constraints

Constraints & assumptions

  • 1 <= n <= 1000 (Number of nodes)
  • 0 <= edges.length <= n * (n - 1) / 2 (Number of edges)
  • 0 <= u, v < n, where [u, v] is an edge in edges.
  • u != v for any given edge.
  • 0 <= startNode, endNode < n

What interviewers evaluate

  • Correctness of the algorithm for finding the shortest path in an unweighted graph.
  • Efficient handling of graph traversal, especially for larger inputs.
  • Proper management of visited nodes to prevent infinite loops and redundant computation.
  • Clarity and structure of the code, including appropriate data structures.

Loading editor...