## Microsoft Interview Question for Senior Software Development Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

DFS will do

Comment hidden because of low score. Click to expand.
1
of 1 vote

Topological sort for cycle detection.

Comment hidden because of low score. Click to expand.
1
of 1 vote

To find a cycle in a graph, run DFS and look for a back edge. The existence of a back edges indicates the existence of a cycle.

To look for back edges, keep a running stack of your DFS. If an edge leads to a vertex that's in your current stack, that's a back edge and is a cycle.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//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);

{
{
return false;
}

for(int i=0;i<visited.length;i++)
{
if(!visited[i])
{
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>

Comment hidden because of low score. Click to expand.
0
of 0 vote

If the graph were represented as an incidence matrix, you could simply check if the dimension of the null space is non-zero, which indicates the circuit rank of the graph.

Comment hidden because of low score. Click to expand.
0
of 0 vote

f

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;``````

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.