0 like 0 dislike
719 views
| 719 views

0 like 0 dislike

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.

by Expert (111,530 points)
0 like 0 dislike

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):
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
# 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],
]))``````
by Expert (111,530 points)
0 like 0 dislike
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.
by Expert (111,530 points)