## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

DFS will be ok in acyclic graphs.

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

a tree structure like this where except for root node all other nodes have just one child will make the alogrithm move up and down the tree more often and hence DFS would be taxing as compared to BFS. (Even in DFS we could always stop at hop k i.e. Depth K the tax is in moving back and forth)

a11
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44

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

Just to summarize, as per my understanding: Please add any more points missed
glebtepanov1992 is right...

let a, b, c, d, e, and f are nodes of same graph.

1. a-b-c-d-e

2. a-c-e-f
3. a-b-d-c
4. a-c-g [of, course i didn't list all the possible traversal paths but this should be enough]

Now as Sandeep has poined out, if code always stops at kth hop (to avoid unnecessary traversal larger than k), then we might loose few valid nodes from visiting. As an example lets take k = 4. Somehow, the DFS chooses the 3. as the first path. Everyone knows, how DFS work. that is, when a node is visited, if at all we come across the same node, we wont go beyond that node. With the path considered, code will definitely miss the node g from printing its value.[ Path 4.]

If we dont the limit the number of hops, we end up exploring all the connected nodes from source, which is very inefficient. [as mentioned by eugene]

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.