Katkat
Back

Identify the Orchestrator in a Server Connection Graph

NetappSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests graph theory fundamentals by identifying a central hub node in a star-topology network using adjacency properties.

Problem Statement

You are given a network of n servers labeled from 0 to n-1, represented as an undirected graph. The network follows a specific architecture: there is exactly one "orchestrator" node that is connected to every other node (the "workers"). The workers do not have any connections between themselves; they only connect to the orchestrator.

Given an array of edges edges where edges[i] = [u, v] represents a connection between server u and server v, identify and return the orchestrator node.

Input

  • n: An integer representing the number of servers.
  • edges: A 2D list of integers where each inner list contains two elements representing an edge.

Constraints

  • 3 <= n <= 10^5
  • edges.length == n - 1
  • All servers are distinct.

Examples

Example 1:

  • Input: n = 4, edges = [[0, 1], [0, 2], [0, 3]]
  • Output: 0
  • Explanation: Node 0 is connected to 1, 2, and 3. Workers 1, 2, and 3 have no connections between them.

Example 2:

  • Input: n = 3, edges = [[1, 2], [2, 0]]
  • Output: 2
  • Explanation: Node 2 is connected to 1 and 0. Node 2 is the orchestrator.

Function Signature

def find_orchestrator(n: int, edges: list[list[int]]) -> int:

Hints

Hint 1

In a star graph, the orchestrator is the only node that appears in more than one edge.

Hint 2

Consider the degree of each node; how does the degree of the orchestrator compare to the degree of a worker?

Hint 3

If you look at the first two edges, the orchestrator must be one of the nodes present in both edges.

Follow-up questions

  • How would you optimize your solution if the graph were extremely large and provided as a stream of edges?
  • What happens to your logic if the network topology changes such that workers can have a limited number of connections to other workers?
  • How would you detect if the given graph is NOT a valid star topology?