Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

DFS will be ok in acyclic graphs.

- glebstepanov1992 June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
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)

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

- Sandeep June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
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]

- KaLee June 20, 2014 | Flag Reply

Add a Comment

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


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


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