Question

Goldman sachs | OA | Complete Day | Set - 31

Answer 1

This question is from a Goldman Sachs Internship Test. The question was roughly as follows:

 

There are n places in a city, we need to connect each place to every other place in the city by roads (called complete day condition). The way we update edges(roads) is by selecting a node(place), upon which every pre-existing edge from that node will vanish and every possible edge that wasn't there in pre-existing edges (which just vanished) will appear. We can select any number of nodes, in any order. There were some pre-existing edges provided for every city. Task is to figure out if complete day condition will be met by some order of selection of nodes.
number of nodes : n <= 1000.

My idea was to make an array of n of bools, where the value represents the parity of the number of times a node is selected. If for some nodes x and y, sum of parity was even then the edge between the edge should exist if odd then edge shall not exist. I will start by assuming parity for first node and see if we can figure out parity of rest without contradiction. I wasn't able to code this.

 

Will this approach work? What is an optimal way to solver this problem.

Answer 2

Thanks for sharing, this is very interesting. Note that the status one step before completion must have exactly one node without any connections, with other nodes fully connected. Probably we can enumerate this node (n possibilities). With this node fixed, the other nodes to flip seem fixed as well to me, and to determine each possibility would be O(n) time, so overall TC is O(n^2). Might do some coding later when I have time.

 

Edit: I feel this brain-teaser style problem amazing so I wrote the full code with test cases :) feel free to correct me if anything is wrong.

 

from typing import Optional

def complete_day(graph: list[list[int]]) -> Optional[set[int]]:
    '''
    The status before completion must have one node without any connections,
    with other nodes fully connected. We can enumerate this node.

    Parameter: n*n matrix, graph[i][j] = graph[j][i] = 1
        if there is an edge between i and j, else 0.
    Return: subset of indexes to flip. If such flip does not exist, return None.
    '''
    n = len(graph)
    # Preprocess: count initial edges for each node
    init_edges = [sum(edges) for edges in graph]
    if all(edges == n for edges in init_edges):
        # Already complete
        return set()
    # Enumerate the node to leave out at the last step
    for i in range(n):
        # We have to flip all the nodes with an edge to i,
        # and leave others intact.
        to_flip = {j for j in range(n) if graph[i][j]}
        # flip everything == flip nothing
        if len(to_flip) == n:
            continue
        # Check if this is a legit flip
        for j in range(n):
            if j in to_flip:
                if init_edges[j] != 2 and i != j:
                    # Only edges between j-j and j-i allowed
                    break
            else:
                if init_edges[j] != n - len(to_flip):
                    # Should be fully connected, except with to_flip subset
                    break
        else:
            # The for loop is completed without a break,
            # so we already found the subset
            return to_flip
    # No such flip exists
    return None

# Some test cases
# {0,1} - Example 1 (identical to flip {2})
print(complete_day([
    [1,1,0],
    [1,1,0],
    [0,0,1],
]))
# {0,1} - Example 2
print(complete_day([
    [1,1,0,0],
    [1,1,0,0],
    [0,0,1,1],
    [0,0,1,1],
]))
# None - Example 3
print(complete_day([
    [1,1,0],
    [1,1,1],
    [0,1,1],
]))
# empty set
print(complete_day([
    [1,1,1],
    [1,1,1],
    [1,1,1],
]))
# {2,3,4}
print(complete_day([
    [1,1,0,0,0],
    [1,1,0,0,0],
    [0,0,1,0,1],
    [0,0,0,1,1],
    [0,0,1,1,1],
]))
# {0,1}
print(complete_day([
    [1,1,0,0,0],
    [1,1,0,0,0],
    [0,0,1,1,1],
    [0,0,1,1,1],
    [0,0,1,1,1],
]))
# None
print(complete_day([
    [1,0,0,0,0],
    [0,1,0,0,0],
    [0,0,1,1,1],
    [0,0,1,1,1],
    [0,0,1,1,1],
]))

Answer 3

Lets try to solve this question in reverse order. Lets assume that answer exists and all nodes are connected to each other . Try to remove one node at a time. If you try to remove one node every time you will see that removing them creates one more connected component in which all nodes are connected to each other. So thats how we get our answer.
If given graph has atmost 2 cc and both cc have n(n-1)/2pairs of edges n is total nodes in a cc . Then the answer exists else not.
And that easily explains all the test Lets try to solve this question in reverse order. Lets assume that answer exists and all nodes are connected to each other . Try to remove one node at a time. If you try to remove one node every time you will see that removing them creates one more connected component in which all nodes are connected to each other. So thats how we get our answer.
If given graph has atmost 2 cc and both cc have n(n-1)/2pairs of edges n is total nodes in a cc . Then the answer exists else not.
And that easily explains all the test cases as well.