CareerCup

This sounds like simple BFS problem.

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

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.

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.