Country: United States

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

This sounds like simple BFS problem.

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

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.

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

@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

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

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

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

``````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``````

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

@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.

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

I don't understand why you say the "Bleed" code is a BFS when it's a DFS. In a BFS you use a queue. Here you're just using basic recursion (with memoization), so it's a DFS.

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.