Jobs

Interviews

Discussions

Find Center of Star Graph

Easy

Google

1 view

Topics:

Graphs

You are given an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.

You are given a 2D integer array edges where each edges[i] = [u_i, v_i] indicates that there is an edge between the nodes u_i and v_i. Return the center of the given star graph.

Example 1:

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2:

Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1

Constraints:

3 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i
The given edges represent a valid star graph.

Find Center of Star Graph

Easy

Google

1 view

Topics:

Graphs

You are given a 2D integer array edges where each edges[i] = [u_i, v_i] indicates that there is an edge between the nodes u_i and v_i. Return the center of the given star graph.

Example 1:

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2:

Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1

Constraints:

3 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i
The given edges represent a valid star graph.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the size range of the input 'edges' array? Is there a maximum number of nodes the star graph can have?
What are the possible values for the node labels in the 'edges' array? Are they guaranteed to be positive integers, and is there a maximum value?
Will the input 'edges' always represent a valid star graph (i.e., will there always be exactly one central node connected to all other nodes)?
Is the input guaranteed to have at least three nodes/two edges, or should I handle the edge case of a smaller graph?
If there's an issue with the input (e.g., not a star graph), what should the function return? Should I throw an exception, or return a specific value like -1?

Brute Force Solution

Approach

The goal is to identify the central node in a star graph. A brute-force method involves examining each node individually to see if it connects to all other nodes, which would identify it as the center.

Here's how the algorithm would work step-by-step:

Pick a node from the connections you are given.
Check if this node appears in every connection you have.
If the node is in every connection, it is the center, so you're done.
If it's not, pick a different node.
Repeat this process until you find a node that is part of every connection.

Code Implementation

def find_center_of_star_graph_brute_force(edges):    number_of_edges = len(edges)
    # Consider the first node in the edges list as a potential center
    potential_center = edges[0][0]
    
    # Iterate through the edges to check if the potential center appears in all edges
    for edge in edges:
        if potential_center not in edge:
            potential_center = edges[0][1]
            break
            
    # Verify that the new potential center is in every edge
    for edge in edges:
        if potential_center not in edge:
            return -1 # Error condition in case of invalid input

    return potential_center

Big(O) Analysis

Time Complexity

O(n) – The input consists of an array of edges, where n is the number of edges. We examine, at most, two nodes to determine the center. For each edge, we examine the two nodes connected by that edge. If the nodes are connected to every edge, then we found the center. Since there are a constant number of operations for each edge, the complexity is directly proportional to the number of edges. Given that the graph is a star graph, n is almost identical to the number of nodes.

Space Complexity

O(1) – The provided algorithm examines nodes from the input edges one by one. It doesn't create any auxiliary data structures like lists, sets, or maps to store intermediate results or track visited nodes. The algorithm only involves picking a node and checking its presence across connections, requiring a few variables to store the current node being checked. The space used remains constant regardless of the number of edges (N), so the space complexity is O(1).

Optimal Solution

Approach

The problem describes a star graph where one special point is connected to all other points. The trick is to quickly identify this central point. The key insight is to look at any two connections to find the common point, which must be the center.

Here's how the algorithm would work step-by-step:

Examine the first two connections given to you.
Find the point that is present in both of these connections.
The point common to both connections is the center of the star graph. No further checks are needed.

Code Implementation

def find_center_of_star_graph(edges):
    # Examine the first two edges to deduce the center.
    first_edge = edges[0]
    second_edge = edges[1]

    # Check if the first node of the first edge is in the second edge.
    if first_edge[0] == second_edge[0] or first_edge[0] == second_edge[1]:
        # This confirms the center of the star graph.
        return first_edge[0]

    # If not, the second node of the first edge must be the center.
    # It must be present in the second edge.
    return first_edge[1]

Big(O) Analysis

Time Complexity

O(1) – The algorithm examines only the first two edges in the input array. Regardless of the total number of edges (n) in the star graph, the number of operations remains constant. This involves a fixed number of comparisons to find the common node between the two edges. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The algorithm examines only the first two connections. It stores, at most, two integer variables to represent the nodes in these connections for comparison. The space used doesn't grow with the number of connections N in the graph. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input 'edges' array	Return an appropriate value (e.g., -1 or throw an exception) indicating invalid input.
Edges array with only one edge	Return either of the nodes in the single edge as the center.
Maximum number of nodes (n = 10^5) as defined by the constraints	Ensure the solution uses O(n) space and time complexity to avoid exceeding time/memory limits.
Edges array where all edges connect to the same node	The algorithm should correctly identify the common node as the center.
Edges contain negative node values	The algorithm should work correctly as long as the graph is still a star graph, by using a hash map or similar to track the node connections.
Edges contain node values close to the maximum integer value	Ensure intermediate calculations (if any) don't cause integer overflow.
Input is not a valid star graph, i.e., more than one node connected to all others	Return -1 or throw an exception to indicate that the input is not a valid star graph as the problem describes.
Node values are strings instead of integers	Handle invalid input gracefully, like throwing an exception or returning an error code, as the problem is defined for integers.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the size range of the input 'edges' array? Is there a maximum number of nodes the star graph can have?
What are the possible values for the node labels in the 'edges' array? Are they guaranteed to be positive integers, and is there a maximum value?
Will the input 'edges' always represent a valid star graph (i.e., will there always be exactly one central node connected to all other nodes)?
Is the input guaranteed to have at least three nodes/two edges, or should I handle the edge case of a smaller graph?
If there's an issue with the input (e.g., not a star graph), what should the function return? Should I throw an exception, or return a specific value like -1?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Pick a node from the connections you are given.
Check if this node appears in every connection you have.
If the node is in every connection, it is the center, so you're done.
If it's not, pick a different node.
Repeat this process until you find a node that is part of every connection.

Code Implementation

def find_center_of_star_graph_brute_force(edges):    number_of_edges = len(edges)
    # Consider the first node in the edges list as a potential center
    potential_center = edges[0][0]
    
    # Iterate through the edges to check if the potential center appears in all edges
    for edge in edges:
        if potential_center not in edge:
            potential_center = edges[0][1]
            break
            
    # Verify that the new potential center is in every edge
    for edge in edges:
        if potential_center not in edge:
            return -1 # Error condition in case of invalid input

    return potential_center

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Examine the first two connections given to you.
Find the point that is present in both of these connections.
The point common to both connections is the center of the star graph. No further checks are needed.

Code Implementation

def find_center_of_star_graph(edges):
    # Examine the first two edges to deduce the center.
    first_edge = edges[0]
    second_edge = edges[1]

    # Check if the first node of the first edge is in the second edge.
    if first_edge[0] == second_edge[0] or first_edge[0] == second_edge[1]:
        # This confirms the center of the star graph.
        return first_edge[0]

    # If not, the second node of the first edge must be the center.
    # It must be present in the second edge.
    return first_edge[1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input 'edges' array	Return an appropriate value (e.g., -1 or throw an exception) indicating invalid input.
Edges array with only one edge	Return either of the nodes in the single edge as the center.
Maximum number of nodes (n = 10^5) as defined by the constraints	Ensure the solution uses O(n) space and time complexity to avoid exceeding time/memory limits.
Edges array where all edges connect to the same node	The algorithm should correctly identify the common node as the center.
Edges contain negative node values	The algorithm should work correctly as long as the graph is still a star graph, by using a hash map or similar to track the node connections.
Edges contain node values close to the maximum integer value	Ensure intermediate calculations (if any) don't cause integer overflow.
Input is not a valid star graph, i.e., more than one node connected to all others	Return -1 or throw an exception to indicate that the input is not a valid star graph as the problem describes.
Node values are strings instead of integers	Handle invalid input gracefully, like throwing an exception or returning an error code, as the problem is defined for integers.