Frontend School

Minimum Hops in a Server Network

DSA
easy

Minimum Hops in a Server Network

Easy
Graph
BFS
Shortest Path

Overview

As a network administrator at Zoho, understanding the connectivity and communication efficiency within our distributed server infrastructure is paramount. Data packets traversing the network incur latency, which is often directly proportional to the number of 'hops' or direct connections they must pass through. This problem aims to simulate a critical network monitoring task: determining the maximum number of hops a signal would take to reach all reachable servers from a designated starting point.

What you need to do / Task

Your task is to implement a function that calculates the maximum of the minimum hops required for a signal to reach every other server in a network from a given startServer. If any server in the network cannot be reached from the startServer, the function should indicate this by returning -1.

Input & output

  • n: An integer representing the total number of servers in the network. Servers are labeled from 1 to n.
  • connections: A 2D array of integers, where each connections[i] = [u, v] denotes a direct, bidirectional network connection between server u and server v.
  • startServer: An integer representing the server from which the signal originates.
  • Returns: An integer representing the maximum of the minimum hops required to reach all servers from the startServer. If not all servers can be reached, return -1.

Clarifications

  • Servers are 1-indexed. Make sure your graph representation and traversal logic account for this.
  • Connections are bidirectional, meaning if [u, v] exists, [v, u] is also implied.
  • If n=1, the startServer is the only server, and 0 hops are needed.
  • If connections is empty and n > 1, only the startServer is reachable from itself, so other servers are unreachable.

Examples

1

Example 1

Input:

n = 4, connections = [[1,2],[1,3],[2,4]], startServer = 1

Output:

2

Note:

From server 1:

  • Server 1: 0 hops
  • Server 2: 1 hop (1->2)
  • Server 3: 1 hop (1->3)
  • Server 4: 2 hops (1->2->4) The maximum of these minimum hops is 2.
2

Example 2

Input:

n = 3, connections = [[1,2]], startServer = 1

Output:

-1

Note:

From server 1:

  • Server 1: 0 hops
  • Server 2: 1 hop (1->2)
  • Server 3: Unreachable. Since not all servers are reachable, return -1.
3

Example 3

Input:

n = 1, connections = [], startServer = 1

Output:

0

Note:

There is only one server, which is the start server itself. 0 hops are needed to 'reach' it.

Constraints

Constraints & assumptions

  • 1 <= n <= 100
  • 0 <= connections.length <= n * (n - 1) / 2
  • 1 <= u, v, startServer <= n
  • u != v (no self-loops)
  • All connections are unique (no duplicate [u, v] pairs in connections)
  • The graph is unweighted, meaning each hop counts as 1.

Out of scope

  • Handling weighted edges (different latency values for connections).
  • Optimizing for extremely large graphs (e.g., millions of nodes).
  • Dynamic network changes (connections being added or removed).

What interviewers evaluate

  • Correct application of Breadth-First Search (BFS) for finding shortest paths in an unweighted graph.
  • Proper construction and utilization of an adjacency list for graph representation.
  • Accurate calculation of the maximum shortest path among all reachable nodes.
  • Robust handling of edge cases, including unreachable servers and single-node networks.

Loading editor...