Frontend School

Minimum Hops in a Server Network

DSA
easy

Minimum Hops in a Server Network

Easy
Graph
BFS
Shortest Path

Overview

Browserstack operates a vast global network of virtual machines and physical devices. When a user initiates a test, the request might traverse through several interconnected servers to reach the target device. Ensuring minimal latency is crucial for a smooth user experience. This problem asks you to find the shortest path, in terms of network "hops," between two specific servers in our simplified network model.

What you need to do / Task

Implement a function minHops that takes the total number of servers, a list of direct connections between them, a starting server, and an ending server. Your function should return the minimum number of hops required to travel from the startNode to the endNode.

Input & output

  • n: An integer representing the total number of servers, labeled from 0 to n-1.
  • connections: An array of [u, v] pairs, where each pair indicates a direct, bidirectional connection between server u and server v.
  • startNode: An integer representing the starting server.
  • endNode: An integer representing the target server.
  • Return: An integer, the minimum number of hops. If endNode is unreachable from startNode, return -1. If startNode is endNode, return 0.

Clarifications

  • The connections are bidirectional. If [u, v] is in connections, v can reach u in one hop, and u can reach v in one hop.
  • The graph is unweighted, meaning each connection counts as one "hop."
  • Servers are 0-indexed.

Examples

1

Example 1

Input:

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

Output:

2

Note:

Path: 0 -> 2 -> 4. Hops: 2.

2

Example 2

Input:

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

Output:

-1

Note:

Server 4 is not reachable from server 0.

3

Example 3

Input:

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

Output:

0

Note:

Starting and ending node are the same, 0 hops.

4

Example 4

Input:

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

Output:

3

Note:

Path: 0 -> 1 -> 2 -> 3. Hops: 3.

Constraints

Constraints & assumptions

  • 1 <= n <= 100
  • 0 <= connections.length <= n * (n - 1) / 2
  • 0 <= u, v < n, u != v for any [u, v] in connections
  • 0 <= startNode, endNode < n
  • There are no duplicate connections in connections.
  • The graph may not be connected.

Out of scope

  • Handling weighted edges (all edges are weight 1).
  • Complex network protocols or dynamic network changes.

What interviewers evaluate

  • Correctness of the BFS algorithm implementation.
  • Efficient graph representation (adjacency list).
  • Handling edge cases (unreachable node, start == end).
  • Clarity and readability of the code.

Loading editor...