## Amazon Interview Question

**Country:**United States

To elaborate slightly, as people are still posting wrong answers:

Take the minimum node, M1, on graph G. This is minimal on *any* path containing it which goes from start to end. So we just need to check there is a path (BFS M1 from start, S, and BFS end, E, from M1).

Then we "cross off" this node and consider Graph G' = G \ {M1}, with minimum M2. If any path from S to E through M2 on G' exists, M2 is minimum on it. So again, run BFS for M2 from S, then BFS for E from M2. If path exists, M2 is also a minimum.

We repeat this until we get to only one remaining node (think about earlier stopping points for micro optimisations if you wish - big O complexity does not change).

Complexity is simple. We consider V nodes, and run BFS on G for each.

Readers should notice a similarity with Prim's algorithm.

Note if we only need the maximal minimum, not all possible minimums, this problem can be solved almost immediately with a Max heap: add back in each cell until there is a path from S to E (how do we check there is a path?). The last edge we needed is the minimal edge on this path, and no paths exist only using larger elements. Again, compare this to Prim's.

I'm a little bit confused... if it is a matrix for sure there is a path that contains the cell with the smallest weight. Do a zig-zag through the matrix and there you go... a path that contains all the cels... so, yes... it is a trick question.

So, maybe I do not understand the problem, but just to a damn for through the matrix and find the minimum weight and the path is the zig-zag one.

I think the problem refers to some kind of minimum sum, then yes...you have a nice problem.

Very cute problem. Had to think about it for a few minutes.

- Yawn January 15, 2019HINT: Look to work through cells (finite), not paths (infinite).

Algorithm is as follows:

*Add all cells to a min heap

*Take lowest node

*Check if path from top left to bottom right not using any previously seen nodes exists; if it does, this is the min on that path, and otherwise this is never a min

*Add the mins to a stack and the last one on is our answer

Coding and proof of correctness left as an exercise.