Interview Question for Software Development Engineer In Test I (SDET) at Amazon.com:

Sep 28, 2012

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.