Frontend School

Network Resilience Optimization

DSA
medium

Network Resilience Optimization

Medium
Union Find
Graph
Connected Components

Overview

Cred operates a vast network of financial services, relying on robust and interconnected systems. Ensuring seamless communication between all servers is critical for reliability and performance. This problem challenges you to optimize network connectivity by determining the minimum additional connections needed to link all servers, leveraging existing infrastructure efficiently.

What you need to do / Task

You are given the total number of servers n and a list of connections representing direct links between pairs of servers. Your task is to implement a function that calculates the minimum number of new connections required to ensure every server can communicate with every other server. If it's impossible to achieve full connectivity with the available redundant connections, you should indicate that.

  1. Initialize a data structure (e.g., Union-Find) to keep track of connected components among the n servers.
  2. Process all given connections, merging components as necessary and identifying any redundant connections (i.e., connections between servers already in the same component).
  3. Calculate the total number of distinct connected components remaining after processing all initial connections.
  4. Determine the minimum number of additional connections required to merge these components into a single, fully connected network.
  5. Return this minimum number, or -1 if it's impossible given the number of redundant connections you could repurpose.

Input & output

Function Signature: minConnectionsNeeded(n: number, connections: number[][]): number

  • n: An integer representing the total number of servers, labeled from 0 to n-1.
  • connections: An array of arrays, where each inner array [u, v] indicates a direct connection between server u and server v. Connections are bi-directional.

Return Value:

  • An integer representing the minimum number of additional connections required to make all servers connected.
  • Return -1 if it's impossible to connect all servers.

Clarifications

  • Self-loops and duplicate connections: Connections [u, u] or duplicate [u, v] connections might exist but should be treated as a single effective connection. Your algorithm should implicitly handle this by only performing a union operation once for a given pair.
  • Disconnected servers: Servers might initially be completely isolated if they are not part of any given connections.
  • n = 1: If there's only one server, it's already connected to itself, so 0 connections are needed.

Examples

1

Example 1

Input:

n = 4, connections = [[0,1],[0,2],[1,2]]

Output:

1

Note:

Initially, servers {0,1,2} are connected, and {3} is separate. There is 1 redundant connection ([1,2]) that can be repurposed to connect {0,1,2} with {3}. Thus, 1 new connection is needed.

2

Example 2

Input:

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

Output:

-1

Note:

Servers {0,1,2} form one component, and {3,4} form another. We need 1 additional connection to link them. However, there are no redundant connections available to repurpose. Therefore, it's impossible to connect all servers.

3

Example 3

Input:

n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]

Output:

2

Note:

Servers {0,1,2,3} are connected. Servers {4} and {5} are isolated. We have 2 redundant connections ([1,2] and [1,3]). We need 2 connections to link {0,1,2,3} with {4}, and then the resulting component with {5}. Since we have 2 redundant connections, we can achieve this.

Constraints

Constraints & assumptions

  • 1 <= n <= 10^5
  • 0 <= connections.length <= min(n * (n - 1) / 2, 10^5)
  • 0 <= u, v < n
  • u != v for any [u, v] in connections.
  • The input connections may contain duplicate connections, but you should treat them as a single connection.
  • The connections are undirected.

Out of scope

  • Handling network latency or bandwidth considerations.
  • Optimizing connection routing paths; only minimum number of connections matters.
  • Error handling for invalid input types or values outside the specified constraints (assume valid input).

What interviewers evaluate

  • Correctness: The solution accurately identifies the minimum connections or impossibility.
  • Algorithm Design: Effective use of Union-Find to manage connected components and track redundant connections.
  • Time and Space Complexity: The solution should be efficient, ideally achieving near-optimal time complexity (e.g., O(N + M) where M is connections.length) and reasonable space complexity.
  • Code Structure and Readability: Clean, well-organized code with appropriate data structures and clear variable names.

Loading editor...