## Google Interview Question

**Country:**United States

The brute force solution is a scan for all the bikes in the parking lot followed by the calculation of the distance between the man and the bike.

The "bleed" solution is a BFS where, starting from the man position, it evaluates if the man is sitting on bike or not and call itself over the neighbours. Since we don't want the man to walk back on his steps, we mark all the visited locations and we skip then.

The "better" version scans all the reachable locations at a certain distance and stops as soon as a bike is found.

Some code:

```
class ClosestBike {
// bikes are 1s in the parkingLot
public static int calculateDistanceBrute(int[][] parkingLot, int manPosRow, int manPosCol) {
int minDistance = Integer.MAX_VALUE;
// the man is standing outside the parking lot. Can't reach any bike.
if (manPosRow > parkingLot.length -1 || manPosCol > parkingLot[0].length - 1)
return minDistance;
for (int row = 0; row < parkingLot.length; row++) {
for (int col = 0; col < parkingLot[0].length; col++) {
if (parkingLot[row][col] == 1) {
minDistance = Math.min(minDistance, ( Math.abs(row - manPosRow) + Math.abs(col - manPosCol) ));
}
}
}
return minDistance;
}
public static int calculateDistanceBleed(int[][] parkingLot, int manPosRow, int manPosCol) {
// the man is standing outside the parking lot. Can't reach any bike.
int minDistance = Integer.MAX_VALUE - 1;
if (manPosRow > parkingLot.length -1 || manPosCol > parkingLot[0].length - 1)
return minDistance;
// The man is sitting on a bike
if (parkingLot[manPosRow][manPosCol] == 1)
return 0;
// Mark the parkingLot location as visited
parkingLot[manPosRow][manPosCol] = -1;
// man can move DOWN
if (manPosRow > 0 && parkingLot[manPosRow - 1][manPosCol] != -1) {
minDistance = Math.min(minDistance, 1 + calculateDistanceBleed(parkingLot, manPosRow - 1, manPosCol));
}
// man can move UP
if (manPosRow < parkingLot.length - 1 && parkingLot[manPosRow + 1][manPosCol] != -1) {
minDistance = Math.min(minDistance, 1 + calculateDistanceBleed(parkingLot, manPosRow + 1, manPosCol));
}
// man can move LEFT
if (manPosCol > 0 && parkingLot[manPosRow][manPosCol - 1] != -1) {
minDistance = Math.min(minDistance, 1 + calculateDistanceBleed(parkingLot, manPosRow, manPosCol - 1));
}
// man can move RIGHT
if (manPosCol < parkingLot[0].length - 1 && parkingLot[manPosRow][manPosCol + 1] != -1) {
minDistance = Math.min(minDistance, 1 + calculateDistanceBleed(parkingLot, manPosRow, manPosCol + 1));
}
return minDistance;
}
public static int calculateDistanceBetter(int[][] parkingLot, int manPosRow, int manPosCol) {
if (manPosRow > parkingLot.length -1 || manPosCol > parkingLot[0].length - 1)
return Integer.MAX_VALUE;
// The man is already sitting on a bike. No need to check further.
if (parkingLot[manPosRow][manPosCol] == 1)
return 0;
int minDistance = 1;
while (minDistance < parkingLot.length + parkingLot[0].length) {
for (int i = 0; i < minDistance; i++) {
if (manPosRow + i < parkingLot.length && manPosCol + (minDistance - i) < parkingLot[0].length) {
// check SE
if (parkingLot[manPosRow + i][manPosCol + (minDistance - i)] == 1)
return minDistance;
}
if (manPosRow + i < parkingLot.length && manPosCol - (minDistance - i) > 0) {
// check SW
if (parkingLot[manPosRow + i][manPosCol - (minDistance - i)] == 1)
return minDistance;
}
if (manPosRow - i > 0 && manPosCol + (minDistance - i) < parkingLot[0].length) {
// check NE
if (parkingLot[manPosRow - i][manPosCol + (minDistance - i)] == 1)
return minDistance;
}
if (manPosRow - i > 0 && manPosCol - (minDistance - i) > 0) {
// check NW
if (parkingLot[manPosRow - i][manPosCol - (minDistance - i)] == 1)
return minDistance;
}
}
minDistance++;
}
return Integer.MAX_VALUE;
}
public static void main(String[] args) {
int[][] parkingLot = new int[][] {
{ 0, 1, 0, 0, 0, 0, 0, 1},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 1, 0, 1, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 1, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 1},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 1, 0, 0, 0, 1}
};
System.out.println("Cal min distance: " + calculateDistanceBrute(parkingLot, 7, 0));
System.out.println("Cal min distance: " + calculateDistanceBetter(parkingLot, 7, 0));
System.out.println("Cal min distance: " + calculateDistanceBleed(parkingLot, 7, 0));
System.out.println("Parking lot status: (-1 is where the man walked)");
for (int i = 0; i < parkingLot.length; i++) {
for (int j = 0; j < parkingLot[0].length; j++) {
System.out.print(parkingLot[i][j] + " ");
}
System.out.println("");
}
}
}
```

EDIT: added an improved version of the code that stops as soon as a bike is found.

EDIT2: added case "man already sitting on the bike" in the "better" version

EDIT3: fixed a small overflow bug in the bleed version of the algorithm and added a small printout of the parkingLot status after the bleed algorithm.

@tuttobenethx

Thanks for sharing your thoughts. Can you tell me the time complexity of bleed solution

And better solution is not correct solution

if we give manPosRow = 9 and manPosCol = 3 then answer should be zero

but it is giving 4

Thanks for noticing the missing case in the "better" version. Concerning the complexities, I think that beside the "better" version, the complexities are O(M*N) since the code doesn't stop when the minimal distance is found. You can easily verify this by printing the parkingLot matrix after the walk has been done.

The better version has a worst case equal to M*N (when there are no bikes in the parkingLot or the man and the bike are sitting at the opposite corners of it).

```
import random
(n, m, bcount) = (5, 10, 4)
(pos, bpos) = (random.randint(0, n*m-1), set(random.sample(xrange(n*m), bcount)))
(l, visited) = (set([pos]), set())
(r, steps) = (bpos.intersection(l), 0)
while l and not r:
steps += 1
l = set([p + d for p in l for d in [-1, 1, -m, +m]
if 0<=p+d<n*m and abs(p%m - (p+d)%m)<2 and p+d not in visited])
visited.update(l)
r = bpos.intersection(l)
bmap = ['*' if i == pos else 'X' if i in r else 'x' if i in bpos else ' ' for i in xrange(n*m)]
for i in xrange(n):
print "|" + ''.join(bmap[i*m:i*m+m]) + "|"
print "distance =", steps
```

Output:

```
|x * |
| x X |
| |
| x |
| |
distance = 2
```

@whoknows , @tuttobenethx,

Change the "if condition" in the better way, to i<= minDistance:

`for (int i = 0; i <= minDistance; i++) {`

then it works fine.

and when we give row, col of 4,4

o/p are:

Brute min distance: 2

Better min distance: 2

Bleed min distance: 8

something wrong with bleed as well.

This sounds like simple BFS problem.

- Luka Gorgadze June 05, 2018