## Amazon Interview Question for SDE-2s

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

care to elaborate? what is a 2D array, a maze? or you want the number of paths through a nxm grid?
if this is a maze, is maze with no walls legit?
this problem looks like O(2*(n**m)) complexity.

Comment hidden because of low score. Click to expand.
0
of 0 vote

is it an adjacency matrix, that is given?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Upon rethinking actually, in the most general case(moving diagonal too), one can use DFS to solve this as a graph problem. So worst case isn't exponential, but it is polynomial in V (i.e. O(V^2)), where V = number of vertices/cells. So you were right on that one ;)

Comment hidden because of low score. Click to expand.
0
of 0 vote

can you please xplain what do you mean by saying m entry points and n exit points and you require the number of paths from all the points?

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a DP problem with complexity O(n^2).

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.