Google Interview Question


Country: United States




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

This sounds like simple BFS problem.

- Luka Gorgadze June 05, 2018 | Flag Reply
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.

- tuttobenethx June 09, 2018 | Flag Reply
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

- whoknows June 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- tuttobenethx June 10, 2018 | Flag
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

- adr June 10, 2018 | Flag Reply
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.

- Ali June 20, 2018 | Flag Reply
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.

- mrincodi July 13, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More