Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

since question says path, we can assume that the distance cannot be negative.
Visualize the matrix as graph and apply Dijkstra's algorithm to get the shortest path.

- msramachandran October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dijkstra's algorithm only applies if all entries are non-negative, not just the overall distance between the source and destination. This assumption was not explicitly stated. You cannot infer that from "path".

Still, you could ask the interviewer whether all values are non-negative, and if they are all non-negative, you'd be set.

- eugene.yarovoi October 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Isn't it: (0,0)--(0,1)--(1,2)--(2,2). Path cst = 5+3+2+1 = 11 ?

- Anonymous October 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah u r correct. My mistake.

- Anonymous October 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't it a question of MST?

- Anonymous October 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If all values are positive, Dijkstra's algorithm for finding the shortest path should work.

- erhuaming October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes I answered the same. But he was looking for some DP solution.

- Anonymous October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I dont think that some DP solution for this problem exists coz it does not satisfy optimality test.
Moreover it does not satisfy DP nature left to right sub-solution nature coz to reach a point we have to check all possible ways to reach that point with minimum total path.

- Anonymous October 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dijkstra's algorithm is a kind of DP

- absolutehot100 November 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes the regular greedy Dijkstra's Algorithm will work on a regular matrix with non-negative numbers. But it does not work for graph with negative edges.

Here is the dynamic programming solution to the problem:

Let Opt(x,i) : optimal solution from the xth entry in the matrix to the end using i entries.
foreach neighbor of x:
Case1: either the neighbor will not be in the solution:
Which means that Opt(x,i) = Opt(x,i-1)
Case2: one of the neighbors will be in the solution:
Which means that for each neighbor w of x: Opt(x,i) = MIN ( val[w]+Opt(w,i-1))
The solution will be the minimum of Case1 and Case2.

Hence answer:
foreach neighbor w of x
Opt(x,i) = MIN (Opt(x,i-1), MIN(val[w]+Opt(w,i-1)));

Reference: Shortest path problem on a graph with negative edges (Chapter on Dynamic Programming, Jon Klienberg).

- code_monkey January 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a = 10;

- Anonymous January 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BFS with branch and bound

- Anonymous February 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

- Anonymous January 22, 2012 | Flag Reply


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