Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
We know that if we have a rectangle (width = x, height = y), that the number of ways to get from the top left corner of the rectangle to the bottom left corner of the rectangle with right and down movements will be C(x + y, x) [which is also C(x + y, y)], because this represents the way we can order R and D movements so that we end up at our destination.
Now, we can apply this to the grid by finding rectangles created by entry and exit points - such that these points represent opposite corners of a rectangle, plug in the width and height of the given rectangle into C(w + h, w), and then sum these values to get the total paths.
Runtime should be O(n^2)
What if your entry point and exit point are right next to each other? Imagine like so
m 0 0
n 0 0
0 0 0
The number of ways to go from entry point m to exit point n in the above case is 7.
Your solution makes three-fold assumptions (which should be clarified from the interviewer):
a. You can only travel in rightward and downward directions.
b. You cannot exit from an exit point if it exists on the same rail as an entry point, and you started from that entry point.
c. A valid traversal from an entry point to an exit point can only happen if i(m) >= i(n) where i(m) is the row index of the entry point, and i(n) is the row index of the exit point.
If traveling in all directions is feasible, then I don't see a polynomial solution to this problem. It can basically be reduced to a path enumeration problem, which is O(2^n).
Corrections:
- "The number of ways to go from entry point m to exit point n in the above case is 8."
- Your solution makes a fourth assumption(actually, this assumption can be derived from the previous three listed above): You never visit a given cell more than once.
FWIW, I think the above assumption is a valid one.
care to elaborate? what is a 2D array, a maze? or you want the number of paths through a nxm grid?
- care March 03, 2015if this is a maze, is maze with no walls legit?
this problem looks like O(2*(n**m)) complexity.