## Amazon Interview Question for Software Engineer / Developers

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

To detect cycles in a directed graph, the most common technique is to perform a depth first search (DFS) of the graph. According to the standard algorithm, we mark each node as white initially, grey when it is visited during search, and black when all its neighbours are finished. During the search, whenever we encounter a node thats already marked grey, we know thats a cycle.
The logic is simple. Any node in the cycle will again be visited when its descendent's neighbours are being seached recursively, before all the descendents are finished.
The run time is the same as DFS, O(|V| + |E|).

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

wont that be changing structure of tree ...

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

As per http://pages.cs.wisc.edu/~vernon/cs367/notes/13.GRAPH.html, here's the code for cycle detection::

{{
static boolean hasCycle(Graphnode n) {
n.setMark( grey );
Iterator it = n.getSuccessors().iterator();
while(it.hasNext()) {
Graphnode m = it.next();
if (m.getMark() == grey) return true;
if (m.getMark() != black) {
if (hasCycle(m)) return true;
}
}
n.setMark( black);
return false;
}
}}

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

topo sort,
or
BFS with mark table

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

build the directed graph using linked list.
use fast-slow pointer approach to detect cycles.

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

dfs can work as well.

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More