## Google Interview Question for Java Developers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

``````#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int min_time_to_reach_lower_right(const vector<vector<int>>& matrix)
{
const pair<int, int> MOVES[] = { {1,0},{-1,0},{0,1},{0,-1} };
struct QueueItem {
int row, col, pathlen;
};

int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
if (n == 0) return 0;

auto qcomp = [](const QueueItem& a, const QueueItem& b) { return a.pathlen > b.pathlen; };
vector<vector<bool>> explored(m, vector<bool>(n));
priority_queue<QueueItem, vector<QueueItem>, decltype(qcomp)> pq(qcomp);
pq.push({0, 0, 0});
explored[0][0] = true;
while (!pq.empty()) {
auto qi = pq.top();
pq.pop();
if (qi.row == n - 1 && qi.col == m - 1) return qi.pathlen;
for (auto& move : MOVES) {
int r = qi.row + move.first;
int c = qi.col + move.second;
if (r >= 0 && r < m && c >= 0 && c < n && !explored[r][c]) {
explored[r][c] = true;
pq.push({ r, c, max(qi.pathlen + 1, matrix[r][c] + 1) });
}
}
}
return -1; // that's actually an error, it should always be able to reach the end
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.