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.