This question was asked today as the first of 5 interviews for Google L4 position.

Given a two 2D integer array, find the min score of a path from the upper left cell to bottom right cell that doesn't visit any of the cells twice. The score of a path is the maximum value in that path.

For example:

Input:

[1,5,3]
[2,6,9]
[4,5,2]

Here are some paths from [0,0] to [2,2] and the minimum value on each path:

path: 1->2->4->5->2, maximum value on this path: 5

path: 1->2->6->9->2, maximum value on this path: 9

path: 1->2->6->5->2, maximum value on this path: 6

Only right and down movement allowed

In the end the min score(the max value) of all the paths is 5.

Output: 5