Frontend School

Network Connectivity Checker

DSA
easy

Network Connectivity Checker

Easy
Union Find
Data Structures

Overview

At Zepto, maintaining robust and reliable network infrastructure is paramount. With thousands of servers handling critical operations, quickly identifying and verifying network connectivity between any two points is essential for troubleshooting, system health monitoring, and ensuring service availability. This problem simulates a simplified scenario where you need to build a system to track server connections and efficiently answer queries about network reachability.

What you need to do / Task

Your task is to implement a NetworkConnectivityChecker class that can manage connections between N servers and efficiently determine if any two servers are connected, directly or indirectly.

  1. constructor(n: number): Initialize the system with n servers. Initially, no servers are connected to each other.
  2. connect(server1: number, server2: number): void: Establishes a direct connection between server1 and server2. This connection is bi-directional. If server1 and server2 are already connected (directly or indirectly), this operation should not change the connectivity state, but should still be handled efficiently.
  3. isConnected(server1: number, server2: number): boolean: Returns true if server1 and server2 are connected (directly or indirectly), and false otherwise.

Input & output

  • n: An integer representing the total number of servers, indexed from 0 to n-1.
  • server1, server2: Integers representing the IDs of the servers involved in an operation.
  • connect method: Returns void.
  • isConnected method: Returns a boolean value indicating connectivity.

Clarifications

  • Server IDs are 0-indexed.
  • Connections are bi-directional: if A is connected to B, B is connected to A.
  • A server is considered connected to itself.
  • Connections are transitive: if A is connected to B, and B is connected to C, then A is connected to C.

Examples

1

Example 1

Input:

operations = ["NetworkConnectivityChecker", "connect", "connect", "isConnected", "isConnected"], params = [[5], [0, 1], [1, 2], [0, 2], [3, 4]]

Output:

[null, null, null, true, false]

Note:

Initialize with 5 servers (0-4). Connect 0-1, then 1-2. Now, servers 0, 1, and 2 are in one connected component. Query if 0 and 2 are connected (true). Query if 3 and 4 are connected (false, as they are separate).

2

Example 2

Input:

operations = ["NetworkConnectivityChecker", "connect", "connect", "connect", "isConnected", "isConnected"], params = [[4], [0, 1], [2, 3], [1, 3], [0, 2], [0, 3]]

Output:

[null, null, null, null, true, true]

Note:

Initialize with 4 servers (0-3). Connect 0-1, then 2-3. Initially, we have two components: {0,1} and {2,3}. Then connect 1-3. This merges the two components, making all servers 0,1,2,3 connected. Query 0-2 (true) and 0-3 (true).

3

Example 3

Input:

operations = ["NetworkConnectivityChecker", "connect", "isConnected", "connect", "isConnected"], params = [[3], [0, 0], [0, 1], [1, 2], [0, 2]]

Output:

[null, null, false, null, true]

Note:

Initialize with 3 servers (0-2). Connecting 0 to 0 has no effect on components. Query 0-1 (false) as they are not yet connected. Connect 1-2. Now servers 0, 1, and 2 are all connected. Query 0-2 (true).

Constraints

Constraints & assumptions

  • 1 <= n <= 10^5
  • 0 <= server1, server2 < n
  • The total number of calls to connect and isConnected will not exceed 10^5.
  • The solution should aim for near constant time (amortized) complexity for connect and isConnected operations.
  • Space complexity should be O(n).

What interviewers evaluate

  • Correct and efficient implementation of the Union-Find data structure.
  • Proper application of optimizations like path compression and union by rank/size.
  • Ability to handle various connectivity scenarios, including self-connections and already connected components.
  • Overall code clarity, structure, and adherence to time/space complexity requirements.

Loading editor...