FastPrep
Problem · Graph

Distributed System Recovery

Learn this problem
● MediumRipplingINTERNOA

Problem statement

Your team manages a distributed system with networkNodes nodes. A major incident occurs, and the primary server with ID company begins recovery operations.

The nodes are connected by bidirectional links. The ith link connects networkFrom[i] and networkTo[i]. Recover every node reachable from company according to these rules:

  1. The starting node company is already online and must not appear in the result.
  2. Recover nodes in increasing order of their shortest number of hops from company.
  3. If multiple nodes are equally distant, recover the lower-numbered node first.
  4. Ignore isolated or otherwise unreachable nodes.

Return the reachable node IDs in recovery order, excluding company.

Function

recoverNetwork(networkNodes: int, networkFrom: int[], networkTo: int[], company: int) → int[]

Examples

Example 1

networkNodes = 4networkFrom = [1,2,2]networkTo = [2,3,4]company = 1return = [2,3,4]

Node 2 is one hop away. Nodes 3 and 4 are both two hops away, so node 3 is recovered first because it has the lower ID.

Example 2

networkNodes = 5networkFrom = [1,1,2,3,1]networkTo = [2,3,4,5,5]company = 1return = [2,3,5,4]

Nodes 2, 3, and 5 are one hop away and are ordered by node ID. Node 4 is two hops away.

Example 3

networkNodes = 3networkFrom = [1]networkTo = [2]company = 2return = [1]

Node 1 is reachable in one hop. Node 3 is isolated and is not returned.

Constraints

  • 2 <= networkNodes <= 10^5
  • 1 <= networkFrom.length <= min(networkNodes * (networkNodes - 1) / 2, 10^5)
  • 1 <= networkFrom[i], networkTo[i], company <= networkNodes
  • networkFrom[i] != networkTo[i]

More Rippling problems

drafts saved locally
public int[] recoverNetwork(int networkNodes, int[] networkFrom, int[] networkTo, int company) {
  // write your code here
}
networkNodes4
networkFrom[1,2,2]
networkTo[2,3,4]
company1
expected[2,3,4]
checking account