Google Interview Question
Java DevelopersCountry: 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