Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
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
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]
DFS will be ok in acyclic graphs.
- glebstepanov1992 June 07, 2014