## Amazon Interview Question

Country: United States

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

This can be done by doing a DFS of the directed graph where you maintain these attributes while doing the DFS:
1) Previsit numbers for nodes, the clock value when you are about to visit a node
2) Postvisit numbers for nodes, the clock value when you are leaving the node after it has been explored
3) Parent/Ancestor information. For every node, record its ancestor/parent as you do the DFS.

Directed graphs have the property that cycles are always found when DFS reveals a back-edge. A back-edge means that if you are looking at an edge (u,v) during traversal, you will see that (pre, post) pair for u is contained within (pre, post) pair of v.

Whenever you spot a back-edge during DFS, just use parent information to back-trace the cycle.

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

Do a DFS of directed graph. Maintain these attributed while doing DFS,
- previsit numbers for nodes
- postvisit numbers for nodes
- parent/ancestor information for nodes

Directed graph has cycles where DFS reveals back-edges. Back edges means when you have an edge (u,v) such that (pre,post) pair of u is contained in that of v.

Whenever you get a back edge, use parent information to back-trace the cycle.

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

You can generate the minimum spanning tree (MST) of the graph, which is rather simple with BFS. Any graph edges not in the MST is possible to introduce a cycle.

For each edge not in MST, let source_vertex be the source of the edge, and end_vertex be the end of the edge. If end_vertex is ancestor of source_vertex, then there is a loop between source_vertex and end_vertex. The loop can be identified by calling getParent() from source_vertex, until meet the end_vertex.

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

my earlier comment about MST is not right.

The following code is tested to work well.

``````public void printGraphCycles(Graph graph) {
HashSet<Vertex> visited = new HashSet<>();
HashSet<Vertex> candidates = new HashSet<>();
for(Vertex vertex : graph.vertexs()){
if(! visited.contains(vertex) && !candidates.contains(vertex))
DFS(graph, vertex, visited, candidates);
}
}

public void DFS(Graph graph, Vertex vertex, HashSet<Vertex> visited, HashSet<Vertex> candidates) {
/*
1 ---] 2
]     /] \
|    / |  ]
|   /  |   3
|  /   |  /
| [    | [
5 ----] 4
*/

// visited nodes may need to revisit to build the cycle
// so don't put visited.contains(adj) on the if condition.
// an example is node 4
// found cycle
} else {
adj.setParent(vertex); // build the trace back
}
}
candidates.remove(vertex);
}``````

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

``````your code fails for the following test case and prints the cycle more than once.

8 11    //  no of nodes  no of edges
0 1     // edge between nodes
1 4
4 0
4 3
3 1
1 2
2 3
2 5
5 6
6 7
7 5``````

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.