Q: Minimum Strongly Connected NetworkSun 22 May 2016
A group of software engineers want to develop an algorithm for finding strongly connected groups among members of a social networking site. A group of people are considered to be strongly connected if each person knows each other person within the group.
Given M nodes and N edges develop an algorithm that determines the minimum size of the largest strongly connected group.
1 <= N <= 100000
2 <= M <= 10000
1 <= M <= N*(N-1)/2
Online coding challenge
- 1 of 3 coding problems
- 2 hours given
This question was a 2nd round automated interview question given after passing multiple choice statistics question
Similar to the other coding questions the initial prompt initially led me astray. I spent a couple of minutes trying to determine the best way to find all the strongly connected groups in an existing network.
However this is not what the problem is asking. Instead of finding the sizes of the strongly connected groups, it's actually asking how can you make the least strongly connected graph
To illustrate this point here are some visualizations. If we needed to construct a graph of 4 nodes and 4 edges it could look like this.
However this solution is suboptimal. We can see that there are 3 strongly connected groups of 2 and 1 strongly connected group of three.
Instead if we place 4 edges like this, the largest connected group is 2 even though the number of edges and nodes are the same.
The trick to this problem is to construct the most weakly connected network possible. This can intuitively be done in stages. At first the edges are placed to connect the nodes "around the edges". Up until this point the minimum strongly connected network size is 2. In code this is done by connecting the N index node with the N+1 index node.
After this the we can continue by connecting the N index node with the N + 3 indexed node. We do this because if we connected the N node with the N+2 node at this point we would end up with a strongly connected group of 3. Connecting the N indexed node with the N+3 indexed node we can continue placing edges while maintaining a strongly connected group of 2.
Eventually it becomes the case that adding more edges will created strongly connected groups of three but the above algorithm avoids this case as long as possible.
In words this is challenging to describe but the algorithm is quite visually intuitive as shown below.
def add_edge(self, source, target): if target >= self.max_n: target = target % (self.max_n) if target not in self.relationships[source]: self.relationships[source].add(target) self.relationships[target].add(source) self.edges_placed +=1 return self.relationships def create_network(self): base_adder = 1 loop_adder = 0 n =0 # Add all the loops while self.edges_placed < self.max_edges: # While adder is less than max n while (base_adder + loop_adder) < self.max_n: #While the node being iterated is less than the maximum while n < self.max_n: #Stop adding edges if all are placed if self.edges_placed == self.max_edges: break else: self.add_edge(n, n+(loop_adder+base_adder)) n+=1 # Continue connecting nodes loop_adder += 2 n = 0 #Strong Connections Start base_adder += 1 loop_adder = 0