Amazon Interview Question Software Engineer / Developers
I think it should be MAX(|A-C|, |B-D|) - MIN(|A-C|,|B-D|) + 1.1* MIN(|A-C|, |B-D|) = MAX(|A-C|, |B-D|) + 0.1 * MIN(|A-C|, |B-D|) , right?
Let's consider the distance from (0,0) ->vertical-> (0,1) , (0,0) ->horizontal-> (1,0), (0,0)->diagonal->(1,1) as one step. Then the cost of moving along diagonal is 1.1*step, moving thought vertical and horizontal will cost 1*step+1*step = 2*step > 1.1*step. So we always choose diagonal as long as possible. the cost for longest diagonal will be 1.1* MIN(|A-C|, |B-D|). and left MAX(|A-C|, |B-D|) - MIN(|A-C|,|B-D|) step for horizontal or vertical which cost 1 for each step.
You missed the point. The answer is to move diagonally until you are aligned vertical or horizon with the other point. (a,b) --> (c,d) = 1.1 * Min( |a-c|, |b-d| ) + 1 * Max( |a-c|, |b-d| ). The number of shortest paths is Max( |a-c|, |b-d| ) - Min( |a-c|, |b-d| ) + 1.
It's a logical analysis problem.
let the point are (x1,y1) and (x2,y2)
- Anonymous July 21, 2011diagonal moves m=MOD(x1-x2)
horizontal move n = MOD(MOD(y1-y2)-m)
total number of shortest path = !(m+n)/!m!n