Microsoft Interview Question
Country: United States
Interview Type: In-Person
Yes. It seems very simple.
1. Represent nodes in adjecency list. Keep a bool visited[total_nodes] array. Initially all values set to false.
2. Write a dfs function for a given node.
signature: bool Print_cycle(int node_number)
2. call above Print_cycle in a function say Make_work_Disjoint. In this iterate on visited[] and call Print_cycle for every node which is not visited.
Very straightforward
class LoopFinder
{
public List<Node> FindLoop(Node node)
{
if (node == null)
throw new ArgumentNullException();
return this.FindLoop(node, new List<Node>());
}
private List<Node> FindLoop(Node node, List<Node> visitedNodes)
{
if (visitedNodes.Contains(node))
return new List<Node>(visitedNodes) { node };
if (node.NextNodes == null || node.NextNodes.Count == 0)
return null;
foreach (Node n in node.NextNodes)
{
var r = FindLoop(n, new List<Node>(visitedNodes) { node });
if (r != null)
return r;
}
return null;
}
}
This is just what came in my mind. I have not tested this code. It may contain some errors.
//N is number of nodes.
void findLoop(int matrix[][]){
int arr[N];
int count=0;
int i=0,j=0;
int visited[N]={0};
while(i< N && j < N){
if(visited[i] == 1){
break;
}
if(arr[i][j] != 0){
i = j;
j = 0;
arr[count++] = i;
visited[i] = 1;
}else{
j++;
}
}
j=0;
while(j<count){
if(arr[j] == i){
break;
}
j++;
}
while(j<count)
printf(arr[j])
}
Assuming it is a finite graph, use dfs traversal using colours. To speed things up you may use multiple threads and colours to detect cycles. If the graph is disjoint search must start from a node of each disjoint part.
- Noobie January 04, 2014