Frontend School

Ad Network Connectivity Check

DSA
easy

Ad Network Connectivity Check

Easy
Graph
Shortest Path
BFS

Overview

Inmobi manages a vast ad delivery network, comprising numerous ad servers interconnected globally. To ensure efficient campaign deployment, rapid incident response, and optimal resource allocation, it's crucial to quickly assess the connectivity between different ad servers. This problem simulates checking the minimum number of direct connections (hops) required to send data from a source server to a target server within this network.

What you need to do / Task

Implement a function that calculates the minimum number of hops (direct connections) needed to travel from a given startServer to a targetServer within the ad network. If the targetServer is unreachable from the startServer, return -1.

Input & output

  • n: An integer, representing the total number of ad servers, labeled from 0 to n-1.
  • connections: An array of arrays, where each inner array [u, v] indicates a direct, bidirectional connection between server u and server v.
  • startServer: An integer, the index of the starting server.
  • targetServer: An integer, the index of the target server.
  • Return: An integer, the minimum number of hops. Return -1 if the target is unreachable.

Clarifications

  • Servers are 0-indexed.
  • Connections are bidirectional (if u is connected to v, v is also connected to u).
  • A server is considered reachable from itself with 0 hops if startServer equals targetServer.

Examples

1

Example 1

Input:

n = 5, connections = [[0,1],[0,2],[1,3],[2,4]], startServer = 0, targetServer = 3

Output:

2

Note:

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

2

Example 2

Input:

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

Output:

-1

Note:

Server 3 is not reachable from server 0.

3

Example 3

Input:

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

Output:

0

Note:

The start server is the same as the target server, so 0 hops are needed.

Constraints

Constraints & assumptions

  • 1 <= n <= 100
  • 0 <= connections.length <= n * (n - 1) / 2
  • 0 <= u, v < n, u != v
  • 0 <= startServer, targetServer < n
  • No duplicate connections are provided.

What interviewers evaluate

  • Correctness of the shortest path algorithm for unweighted graphs (BFS).
  • Efficient graph traversal and state management (visited nodes).
  • Handling edge cases like unreachable targets and start/target being the same.
  • Code clarity, organization, and efficient use of data structures.

Loading editor...