Interview Question

Software Development Engineer In Test I (SDET) Interview Seattle, WA

Consider a rectangular mesh (intersecting horizontal and

  vertical lines ). These lines represent intersecting roads. You are standing at top left intersection and you need to reach to a resort located at bottom right intersection. On your way, you can see interesting sights which are given points (weightage). You are lazy to walk (i.e. you wont walk left / up. You will only walk to right or down). While reaching resort , you want to cover maximum points (see things that have more weightage). Write a program to calculate maximum number of points that you can cover. He later asked me to improve solution by avoiding paths already visited.

Interview Answer

1 Answer


Use Dijkstra minimal path algorithm. Give the edges weight according to how interesting a resort is and find the path with the maxim interest.

Eric on Dec 14, 2013

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up