## Microsoft Interview Question

Senior Software Development Engineers**Country:**United States

**Interview Type:**Phone Interview

```
//Assumption:The graph is in the form of an adjacency matrix.
//Time Complexity: O(v+e) where v is the number of vertices and e is the number of edges.
//Space: O(v);
public boolean hasCycle(boolean[][] adj)
{
if(adj==null||adj.length==0)
{
return false;
}
boolean[] visited=new boolean[adj.length];
for(int i=0;i<visited.length;i++)
{
if(!visited[i])
{
boolean hasCycle=checkCycle(i,visited, adj, new HashMap<Integer,Boolean>());
if(hasCycle)
{
return true;
}
}
}
return false;
}
private boolean checkCycle(int p, boolean[] v,boolean[][] m, HashMap<Integer,Boolean> mp)
{
v[p]=true;
mp.put(p,true);
for(int i=0;i<m[p].length;i++)
{
if(m[p][i])
{
if(mp.containsKey(i))
{
return true;
}
if(![v])
{
boolean c=checkCycle(i,v,m,mp);
if(c)
{
return true;
}
}
}
}
return false;
}
```

I believe that the question is simplified and therefore you do not have to do a full blown DFS. For this problem you can get away with something like this (NOTE: not tested):

<pre>

Map<Node> visitedNodes = new HashMap<Node>();

public boolean isCycle( Node node ) {

Node existingNode = visitedNodes.put( node );

if( existingNode != null ) {

return true;

}

boolean cycleFound = false;

for( Node connectedNode : node.connectedNodes ) {

cycleFound = cycleFound || isCycle( connectedNode );

}

return cycleFound;

}

</pre>

Two traversals at once,

- Traverse the Graph using DFS picking up the node with immediate next depth

- Traverse the Graph using DFS picking up the node with next to next depth

If the faster traversal finishes itself ==> this is not a cyclic directed graph

Else if the two traversals meet at some point ==> this is a cyclic directed graph.

The complexity is same as DFS, just twice.

I believe that the question simplifies the implementation and you do not have to do a full blown DFS. This should do (NOTE: was not tested)

```
Map<Node> visitedNodes = new HashMap<Node>();
public boolean isCycle( Node node ) {
Node existingNode = visitedNodes.put( node );
if( existingNode != null ) {
return true;
}
boolean cycleFound = false;
for( Node connectedNode : node.connectedNodes ) {
cycleFound = cycleFound || isCycle( connectedNode );
}
return cycleFound;
}
```

I believe that the question is simplified and therefore you do not have to do a full blown DFS. For this problem you can get away with something like this (NOTE: not tested):

```
Map<Node> visitedNodes = new HashMap<Node>();
public boolean isCycle( Node node ) {
Node existingNode = visitedNodes.put( node );
if( existingNode != null ) {
return true;
}
boolean cycleFound = false;
for( Node connectedNode : node.connectedNodes ) {
cycleFound = cycleFound || isCycle( connectedNode );
}
return cycleFound;
```

}

I believe that the question is simplified and therefore you do not have to do a full blown DFS. For this problem you can get away with something like this (NOTE: not tested):

```
Map<Node> visitedNodes = new HashMap<Node>();
public boolean isCycle( Node node ) {
Node existingNode = visitedNodes.put( node );
if( existingNode != null ) {
return true;
}
boolean cycleFound = false;
for( Node connectedNode : node.connectedNodes ) {
cycleFound = cycleFound || isCycle( connectedNode );
}
return cycleFound;
}
```

DFS will do

- hprem991 April 09, 2016