Question

D.E. Shaw | OA | SDE-Internship | Coding Questions and Solutions | 2023 | Set-3

Answer 1

Section 3 - Disconnected Nodes (Coding, 30 mins)

 

Problem statement: there is an undirected graph with n nodes and some edges, there is also an array of m integers disconnected_nodes, which represnt the array of nodes that are not reachable from one another via any path. No two nodes in the array are connected directly or indirectly.
Find the maximum number of edges that can be added to the graph such that the set of disconnected_nodes remains disconnected.

 

Example:
Input - n = 6, edges = [[1,2], [1,3], [2,3], [4,5]], disconnected_nodes = [2, 4]
output - 3
Explanation - following edges can be added [6,1] , [6,2], [6,3]

Comments

The is a 24 in coding edges