## Google Interview Question

Java Developers**Country:**United States

Reframing question(from what i understand)

--> Find optimum path from 0,0 -> n-1, n-1, which minimizes no of days.

'N' days are spend , when water is at level "l" and next node in path is a level "l+N".

Reframing the problem again, this basically means if i have a path with heights

0,5,2,4,7,12, 8, 2 -> Then days spend are -> (5-0) + (7-5) + 12-7 , which is effectively 12 (or the max height seen)

--> Find a path from 0,0 -> n-1, n-1 , that minimizes the maximum height seen in path. Or

We can use djiskstra to find the path , basically the cost function for edge (i,j -> x,y) becomes Max(minimum maxheight at i,j, height(x,y));

Assumptions:

- the cell where the boat is starting has hight -1, the boat can float

- it takes one time unit to move let, right, up and down (Manhatten moves)

- in order to be able to float on a field the water level must be field hight + 1 when

I reach there. for example level is 2 when I start at field (0,0) I can go to

field (1,0) in one time unit if level of that field (1,0) is 2.

I'd solve it using a Dijkstras sort of shortest path. The cost to go to an adjacent field

is current-path-length + min(1, field-height - current-path-length). That is, the cost is defined by the field and not the weight of an edge. Thus I don't need the relaxation step from Dijkstra.

I could add heuristics that estimates remaining distance, to create an A* like thing.

- Chris December 03, 2017