Jobs

Interviews

Discussions

Add Edges to Make Degrees of All Nodes Even

Hard

Uber

0 views

Topics:

Graphs

You are given an undirected graph consisting of n nodes numbered from 1 to n. You are also given a 2D array edges where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i. The graph can be disconnected.

You can add at most two additional edges (possibly none) to this graph so that there are no repeated edges and no self-loops.

Can you determine if it is possible to make the degree of each node in the graph even? The degree of a node is the number of edges connected to it.

Example 1:

n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]

In this example, the output should be true because you can add an edge between nodes 1 and 5. All nodes will then have even degrees.

Example 2:

n = 4, edges = [[1,2],[3,4]]

In this example, the output should be true because you can add edges between nodes 1 and 3, and between nodes 2 and 4. All nodes will then have even degrees.

Example 3:

n = 4, edges = [[1,2],[1,3],[1,4]]

In this example, the output should be false because it is not possible to obtain a valid graph with all even degrees by adding at most 2 edges.

Add Edges to Make Degrees of All Nodes Even

Hard

Uber

0 views

Topics:

Graphs

You can add at most two additional edges (possibly none) to this graph so that there are no repeated edges and no self-loops.

Can you determine if it is possible to make the degree of each node in the graph even? The degree of a node is the number of edges connected to it.

Example 1:

n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]

In this example, the output should be true because you can add an edge between nodes 1 and 5. All nodes will then have even degrees.

Example 2:

n = 4, edges = [[1,2],[3,4]]

In this example, the output should be true because you can add edges between nodes 1 and 3, and between nodes 2 and 4. All nodes will then have even degrees.

Example 3:

n = 4, edges = [[1,2],[1,3],[1,4]]

In this example, the output should be false because it is not possible to obtain a valid graph with all even degrees by adding at most 2 edges.

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 range of possible values for the number of nodes, and how many edges can there be initially?
Is the graph guaranteed to be connected? If not, should I only consider the connected component containing the original graph, or should I make all node degrees even across all components?
If there are multiple possible sets of edges to add that result in all even degrees, is there any preference in which set I should return? (e.g., minimize the number of edges added, or minimize the node indices used in the new edges)
If it's impossible to make the degrees of all nodes even, what should I return? (e.g., null, an empty list, or throw an exception)
How is the graph represented as input? Is it an adjacency list, an adjacency matrix, or a list of edges? What data types are used to represent nodes (e.g., integers starting from 0 or 1, or some other identifier)?

Brute Force Solution

Approach

The goal is to make sure every point in a network connects to an even number of other points. The brute force approach tries every possible combination of adding connections until we find one where all points have an even number of connections.

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

First, identify all the points in the network that are connected to an odd number of other points.
Then, consider adding a direct connection between every possible pair of these 'odd' points.
For each possible pairing, check if adding that connection makes all points in the network have an even number of connections.
If adding a connection doesn't solve the problem, try adding two new connections. Consider all possible pairs of 'odd' points and then all possible pairings between these pairs.
Check each of these new configurations to see if all points now have an even number of connections.
If you find a configuration that works (all points have an even number of connections), you've solved the problem. If you've tried every possible combination of adding connections and still haven't found a solution, then it's impossible to solve.

Code Implementation

def add_edges_to_make_degrees_even(number_of_nodes, existing_edges):    odd_degree_nodes = []
    for node in range(1, number_of_nodes + 1):
        degree = 0
        for edge_start, edge_end in existing_edges:
            if node == edge_start or node == edge_end:
                degree += 1
        if degree % 2 != 0:
            odd_degree_nodes.append(node)

    if not odd_degree_nodes:
        return []

    # If only 2 nodes have odd degree, add an edge between them
    if len(odd_degree_nodes) == 2:
        return [(odd_degree_nodes[0], odd_degree_nodes[1])]

    # Attempt to fix by adding one edge
    for i in range(len(odd_degree_nodes)): 
        for j in range(i + 1, len(odd_degree_nodes)): 
            edge_to_add = (odd_degree_nodes[i], odd_degree_nodes[j])
            temp_edges = existing_edges + [edge_to_add]
            all_even = True
            for node in range(1, number_of_nodes + 1):
                degree = 0
                for edge_start, edge_end in temp_edges:
                    if node == edge_start or node == edge_end:
                        degree += 1
                if degree % 2 != 0:
                    all_even = False
                    break
            if all_even:
                return [edge_to_add]

    # Attempt to fix by adding two edges
    for i in range(len(odd_degree_nodes)): 
        for j in range(i + 1, len(odd_degree_nodes)): 
            for k in range(len(odd_degree_nodes)): 
                for l in range(k + 1, len(odd_degree_nodes)): 
                    # Ensure unique pairings
                    if len(set([i, j, k, l])) != 4:
                        continue

                    edge_one = (odd_degree_nodes[i], odd_degree_nodes[j])
                    edge_two = (odd_degree_nodes[k], odd_degree_nodes[l])
                    temp_edges = existing_edges + [edge_one, edge_two]

                    all_even = True
                    # Check if all degrees are even
                    for node in range(1, number_of_nodes + 1):
                        degree = 0
                        for edge_start, edge_end in temp_edges:
                            if node == edge_start or node == edge_end:
                                degree += 1
                        if degree % 2 != 0:
                            all_even = False
                            break

                    if all_even:
                        return [edge_one, edge_two]

    return []

Big(O) Analysis

Time Complexity

O(n^4) – The algorithm first identifies nodes with odd degrees, which takes O(n) time where n is the number of nodes. The core of the brute force approach involves considering pairs of odd-degree nodes. In the worst case, almost all nodes could have odd degrees, leading to O(n) such nodes. Adding a single edge involves iterating through all possible pairs of odd nodes, resulting in O(n^2) combinations. If adding one edge doesn't solve the problem, the algorithm tries adding two edges. This requires considering all pairs of odd nodes and then all possible pairings between these pairs. This nested pairing contributes an additional factor of O(n^2) for the second edge. Thus, the overall complexity is approximately O(n^2 * n^2), simplifying to O(n^4).

Space Complexity

O(N) – The space complexity is primarily determined by the need to identify and store the nodes with odd degrees. In the worst-case scenario, all N nodes could have odd degrees, requiring us to store them in a list or set. The brute-force approach explores various combinations of these odd-degree nodes, but the storage of these node combinations doesn't fundamentally change the dominant factor. Thus, the auxiliary space is proportional to the number of nodes N, leading to a space complexity of O(N).

Optimal Solution

Approach

The goal is to make sure every point in our network has an even number of connections. We achieve this by selectively adding new connections between points that currently have an odd number of connections, ensuring we do it in the most efficient way possible.

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

First, identify all the points that have an odd number of connections.
If there are no points with an odd number of connections, we're done and don't need to add any new connections.
If there are an even number of points with an odd number of connections, pair them up and add direct connections between each pair. This immediately makes the connections for each point even.
If there are an odd number of points with an odd number of connections, this means we cannot make an even number of connections for each. The problem can't be solved.
If pairing up points directly is not allowed because they're already connected, find a different point with an odd number of connections, and connect it to one of your points, and then connect your new point to any point in the graph that is unconnected.
By strategically pairing and connecting points with odd connections, we ensure the minimum number of connections are added to make the degree of each point even.

Code Implementation

def add_edges_to_make_degrees_even(number_of_nodes, edges):
    odd_degree_nodes = []
    adjacency_list = [[] for _ in range(number_of_nodes)]

    for node1, node2 in edges:
        adjacency_list[node1].append(node2)
        adjacency_list[node2].append(node1)

    for node_index in range(number_of_nodes):
        if len(adjacency_list[node_index]) % 2 != 0:
            odd_degree_nodes.append(node_index)

    number_of_odd_nodes = len(odd_degree_nodes)

    if number_of_odd_nodes == 0:
        return []

    if number_of_odd_nodes % 2 != 0:
        return None

    new_edges = []

    # Pair up odd degree nodes and add edges.
    for i in range(0, number_of_odd_nodes, 2):
        node1 = odd_degree_nodes[i]
        node2 = odd_degree_nodes[i+1]

        # Check if the edge already exists.
        if node2 not in adjacency_list[node1]:
            new_edges.append((node1, node2))
        else:
            #If nodes are already connected, connect node1 to a new node.
            for potential_connection_node in range(number_of_nodes):
                if potential_connection_node != node1 and potential_connection_node not in adjacency_list[node1]:
                    new_edges.append((node1, potential_connection_node))
                    break
    
    return new_edges

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm's time complexity is determined by the number of nodes (n) with odd degrees. Identifying nodes with odd degrees requires iterating through all nodes, taking O(n) time. The core of the algorithm involves pairing these odd-degree nodes. In the worst-case scenario, where nodes cannot be directly connected, we might need to check for existing connections, potentially requiring a check between all pairs of odd-degree nodes. Therefore, the pairing process in the worst case can take O(n^2) since we need to check if 2 nodes are already connected to each other and in the worst case scenario will check all node pairings. Thus, the overall time complexity is dominated by this pairwise check and simplifies to O(n^2).

Space Complexity

O(N) – The primary space complexity comes from identifying odd degree nodes, which, in the worst case, could involve storing all N nodes of the graph in a list or set. The algorithm might also temporarily store pairs of nodes to connect. Therefore, the auxiliary space is determined by the storage needed for the odd degree nodes, leading to a space complexity of O(N), where N is the number of nodes in the graph.

Edge Cases

Case	How to Handle
Null or empty graph (no nodes)	Return an empty list, as there are no edges to add.
Graph with only one node	Return an empty list, as a single node trivially has an even degree.
All nodes initially have even degrees	Return an empty list because no edges need to be added.
Only two nodes with odd degrees	Add an edge directly between these two nodes.
Four nodes with odd degrees (the most interesting case)	Try all three possible pairings of the four nodes with odd degrees and return the first one that works.
More than four nodes with odd degrees (impossible)	Return an empty list, since it's impossible to have an odd number of nodes with odd degrees.
Graph is already fully connected (adding edges might create parallel edges, but degrees still become even)	The algorithm should still correctly identify and add edges between odd-degree nodes, potentially creating parallel edges which are allowed.
Self-loops already exist in the graph	The algorithm should correctly identify nodes with odd degrees after considering the existing self-loops.

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 range of possible values for the number of nodes, and how many edges can there be initially?
Is the graph guaranteed to be connected? If not, should I only consider the connected component containing the original graph, or should I make all node degrees even across all components?
If there are multiple possible sets of edges to add that result in all even degrees, is there any preference in which set I should return? (e.g., minimize the number of edges added, or minimize the node indices used in the new edges)
If it's impossible to make the degrees of all nodes even, what should I return? (e.g., null, an empty list, or throw an exception)
How is the graph represented as input? Is it an adjacency list, an adjacency matrix, or a list of edges? What data types are used to represent nodes (e.g., integers starting from 0 or 1, or some other identifier)?

Brute Force Solution

Approach

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

First, identify all the points in the network that are connected to an odd number of other points.
Then, consider adding a direct connection between every possible pair of these 'odd' points.
For each possible pairing, check if adding that connection makes all points in the network have an even number of connections.
If adding a connection doesn't solve the problem, try adding two new connections. Consider all possible pairs of 'odd' points and then all possible pairings between these pairs.
Check each of these new configurations to see if all points now have an even number of connections.
If you find a configuration that works (all points have an even number of connections), you've solved the problem. If you've tried every possible combination of adding connections and still haven't found a solution, then it's impossible to solve.

Code Implementation

def add_edges_to_make_degrees_even(number_of_nodes, existing_edges):    odd_degree_nodes = []
    for node in range(1, number_of_nodes + 1):
        degree = 0
        for edge_start, edge_end in existing_edges:
            if node == edge_start or node == edge_end:
                degree += 1
        if degree % 2 != 0:
            odd_degree_nodes.append(node)

    if not odd_degree_nodes:
        return []

    # If only 2 nodes have odd degree, add an edge between them
    if len(odd_degree_nodes) == 2:
        return [(odd_degree_nodes[0], odd_degree_nodes[1])]

    # Attempt to fix by adding one edge
    for i in range(len(odd_degree_nodes)): 
        for j in range(i + 1, len(odd_degree_nodes)): 
            edge_to_add = (odd_degree_nodes[i], odd_degree_nodes[j])
            temp_edges = existing_edges + [edge_to_add]
            all_even = True
            for node in range(1, number_of_nodes + 1):
                degree = 0
                for edge_start, edge_end in temp_edges:
                    if node == edge_start or node == edge_end:
                        degree += 1
                if degree % 2 != 0:
                    all_even = False
                    break
            if all_even:
                return [edge_to_add]

    # Attempt to fix by adding two edges
    for i in range(len(odd_degree_nodes)): 
        for j in range(i + 1, len(odd_degree_nodes)): 
            for k in range(len(odd_degree_nodes)): 
                for l in range(k + 1, len(odd_degree_nodes)): 
                    # Ensure unique pairings
                    if len(set([i, j, k, l])) != 4:
                        continue

                    edge_one = (odd_degree_nodes[i], odd_degree_nodes[j])
                    edge_two = (odd_degree_nodes[k], odd_degree_nodes[l])
                    temp_edges = existing_edges + [edge_one, edge_two]

                    all_even = True
                    # Check if all degrees are even
                    for node in range(1, number_of_nodes + 1):
                        degree = 0
                        for edge_start, edge_end in temp_edges:
                            if node == edge_start or node == edge_end:
                                degree += 1
                        if degree % 2 != 0:
                            all_even = False
                            break

                    if all_even:
                        return [edge_one, edge_two]

    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, identify all the points that have an odd number of connections.
If there are no points with an odd number of connections, we're done and don't need to add any new connections.
If there are an even number of points with an odd number of connections, pair them up and add direct connections between each pair. This immediately makes the connections for each point even.
If there are an odd number of points with an odd number of connections, this means we cannot make an even number of connections for each. The problem can't be solved.
If pairing up points directly is not allowed because they're already connected, find a different point with an odd number of connections, and connect it to one of your points, and then connect your new point to any point in the graph that is unconnected.
By strategically pairing and connecting points with odd connections, we ensure the minimum number of connections are added to make the degree of each point even.

Code Implementation

def add_edges_to_make_degrees_even(number_of_nodes, edges):
    odd_degree_nodes = []
    adjacency_list = [[] for _ in range(number_of_nodes)]

    for node1, node2 in edges:
        adjacency_list[node1].append(node2)
        adjacency_list[node2].append(node1)

    for node_index in range(number_of_nodes):
        if len(adjacency_list[node_index]) % 2 != 0:
            odd_degree_nodes.append(node_index)

    number_of_odd_nodes = len(odd_degree_nodes)

    if number_of_odd_nodes == 0:
        return []

    if number_of_odd_nodes % 2 != 0:
        return None

    new_edges = []

    # Pair up odd degree nodes and add edges.
    for i in range(0, number_of_odd_nodes, 2):
        node1 = odd_degree_nodes[i]
        node2 = odd_degree_nodes[i+1]

        # Check if the edge already exists.
        if node2 not in adjacency_list[node1]:
            new_edges.append((node1, node2))
        else:
            #If nodes are already connected, connect node1 to a new node.
            for potential_connection_node in range(number_of_nodes):
                if potential_connection_node != node1 and potential_connection_node not in adjacency_list[node1]:
                    new_edges.append((node1, potential_connection_node))
                    break
    
    return new_edges

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty graph (no nodes)	Return an empty list, as there are no edges to add.
Graph with only one node	Return an empty list, as a single node trivially has an even degree.
All nodes initially have even degrees	Return an empty list because no edges need to be added.
Only two nodes with odd degrees	Add an edge directly between these two nodes.
Four nodes with odd degrees (the most interesting case)	Try all three possible pairings of the four nodes with odd degrees and return the first one that works.
More than four nodes with odd degrees (impossible)	Return an empty list, since it's impossible to have an odd number of nodes with odd degrees.
Graph is already fully connected (adding edges might create parallel edges, but degrees still become even)	The algorithm should still correctly identify and add edges between odd-degree nodes, potentially creating parallel edges which are allowed.
Self-loops already exist in the graph	The algorithm should correctly identify nodes with odd degrees after considering the existing self-loops.