Amazon.com Interview Question
Web:
www.amazon.com
|
HQ:
Seattle, WA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,589 Interview Reviews |
Back to all Amazon.com Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Development Engineer II at Amazon.com:
Jun 13, 2011
Write algorithm/code to find longest path between any two cities. 4X4 matrix was given. If there is no connectivity between two cities then the distance between them was given as -1. Its cyclic graph.
Add Tags
[?]
See more for this Amazon.com Software Development Engineer II Interview
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (2)
2 of 2 people found this helpful
Jun 15, 2011
Finding longest path between two nodes in a graph is an NP Hard problem. So, we should not try to find a polynomial solution to this problem.
As you can see the given problem is of very small size. So even brute force is acceptable.
Solution:
Let there be n cities. GIven starting city as S and destination city as D. We are left with n-2 cities.
There are approximately 2^(n-2) * (n-2)! ways for reaching D from S.
Find length of all these ways and choose the smallest one.
As you can see the given problem is of very small size. So even brute force is acceptable.
Solution:
Let there be n cities. GIven starting city as S and destination city as D. We are left with n-2 cities.
There are approximately 2^(n-2) * (n-2)! ways for reaching D from S.
Find length of all these ways and choose the smallest one.
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Development Engineer II Interview Questions, Amazon.com Interview
by ✳✳✳✳✳✳✳✳