leninkumar31's blog

By leninkumar31, history, 4 years ago,

Following question was asked in a coding interview.how to solve it with out using dynamic programming?

• +4

 » 4 years ago, # |   0 Auto comment: topic has been updated by leninkumar31 (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 5 →   0 To reach from (0,0) to (X,Y) you need to go right X steps and go up Y steps. Let's regard a step as an arrow. If there is no building, you can make combinations of X right-arrows and Y up-arrows. That's C(X+Y,X) or equivalently C(X+Y,Y).Now, there is a building that covers (A,B) to (A+N,B+M). Let f(X,Y) be the number of combinations can be made with X right-arrows and Y up-arrows. That is, f(X,Y) = C(X+Y,X) = C(X+Y,Y).Then the number of pathes is as follows:f(X,Y) — f(A+1,B+1)f(M-2,N-2)f(X-A-N+1,Y-B-M+1) special case: f(x,y) = 0 where x < 0 or y < 0.
•  » » 4 years ago, # ^ |   0 can you explain last equation in detail?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 In fact it's wrong. I'm finding a new formula. But the idea was: p = the number of pathes from (0, 0) to (A+1, B+1) q = the number of pathes from (A+1, B+1) to (A+N-1, B+M-1) r = the number of pathes from (A+N-1, B+M-1) to (X,Y) the number of pathes can't be taken = pqr 
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 16 64 4 1 1answer is 74. your solution is wrong.
 » 4 years ago, # | ← Rev. 2 →   0 A path should contain exactly one of arrows in the picture. (there are A up-arrows and B right-arrows) The number of pathes that contain u1 is f(0,B+M-1)f(X,Y-B-M) The number of pathes that contain u2 is f(1,B+M-1)f(X-1,Y-B-M) ... So, the answer is: