Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
Perform a simple BFS on the graph and add the points to the queue until you find a building. I present a simple solution in Python below.
Code
from collections import deque
# This function returns the minimum cost
def bfs(googleMap, employeeLocation):
if not googleMap or not googleMap[0] or not employeeLocation:
return 0
minCost = 0
pathToBuilding = []
rows, cols = len(googleMap), len(googleMap[0])
# Perform a BFS here
startX, startY = employeeLocation
queue = deque([(startX, startY, 0, [])])
visited = set([(employeeLocation)])
while queue:
x, y, currCost, path = queue.popleft()
if googleMap[x][y] == 'B': # Destination Reached
minCost = currCost
pathToBuilding = path
break
for nextX, nextY, dir in [(x, y+1, 'R'), (x+1, y, 'D'), (x, y-1,'L'), (x-1, y, 'U')]:
if 0 <= nextX < rows and 0 <= nextY < cols \
and googleMap[nextX][nextY] != '#'\
and (nextX, nextY) not in visited:
visited.add((nextX, nextY))
queue.append((nextX, nextY, currCost + 1, path + [dir]))
return (minCost, pathToBuilding)
Test Code
# Test Case 1
googleMap = [
['.', '.', '.', '.', '.', '#'],
['.', '.', 'E', '.', '.', '#'],
['#', '#', '#', '#', '.', '#'],
['.', 'B', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', 'B']
]
print(bfs(googleMap, (1, 2)))
# OUTPUTS: (6, ['R', 'R', 'D', 'D', 'R', 'D'])
# Test Case 2
googleMap = [
['.', '.', '.', '.', '.', '#'],
['.', '.', 'E', '.', '.', '#'],
['#', '#', '#', '#', '.', '#'],
['B', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.']
]
print(bfs(googleMap, (1, 2)))
# OUTPUTS: (8, ['R', 'R', 'D', 'D', 'L', 'L', 'L', 'L'])
Start with the B in the queue and then pop it by exploring nearby points which are vacant and simultaneously pushing them in queue, as in Breadth First Search in Graph, maintain a cost matrix and fill simultaneously, untill you reach E or you have nothing in queue. The cost corresponding to E in matrix will be the answer.
BFS
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
class Point
{
public:
Point(int r, int c)
{
r_ = r;
c_ = c;
}
int r_, c_;
};
Point NearestBike(vector<vector<char>> map, const Point& start)
{
queue<Point> q;
q.push(start);
while (!q.empty())
{
Point p = q.front();
q.pop();
int r = p.r_;
int c = p.c_;
if (r >= 0 &&
r < map.size() &&
c >= 0 &&
c < map[r].size() &&
map[r][c] != '#' &&
map[r][c] != 0)
{
if (map[r][c] == 'B')
{
return p;
}
map[r][c] = 0;
q.push(Point(r + 1, c));
q.push(Point(r - 1, c));
q.push(Point(r, c + 1));
q.push(Point(r, c - 1));
}
}
return Point(-1, -1);
}
int main()
{
Point p = NearestBike(
{
{'.', '.', '.', '.', '.', '#'},
{'.', '.', '.', '.', '.', '#'},
{'#', '#', '#', '#', '.', '#'},
{'.', 'B', '.', '.', '.', '.'},
{'.', '.', '.', '.', '.', 'B'},
},
Point(1, 2)
);
cout << p.r_ << ", " << p.c_ << "\n";
return 0;
}
Python
def trace(*txt):
traceOn = False
if traceOn:
print(*txt)
class Bike:
def __init__(self,gmap):
assert len(gmap) > 0
assert len(gmap[0]) > 0
self._m = gmap
print("Got new map! %dx%d"%(len(gmap),len(gmap[0])))
def findRoute(self, *pos):
visited = {pos: None} # position -> (tuple for direction, prev y, prev x)
stack = [pos]
gm = self._m
h,w = len(gm), len(gm[0])
y, x = pos
trace("Start at ", pos)
if y < 0 or x < 0 or y >= h or x >= w:
print("You are out of map, too bad: %s\n\n"%(str(pos)))
return
while len(stack):
prevY, prevX = stack[0]
for a,y,x in [('U', prevY - 1, prevX),
('D', prevY + 1, prevX),
('L', prevY, prevX - 1),
('R', prevY, prevX + 1)]:
trace("try: %s %u,%u"%(a,y,x))
if y < 0 or x < 0 or y >= h or x >= w:
trace("out of map: %s %u,%u"%(a,y,x))
continue
if (y,x) in visited:
trace("already visited: %s %u,%u"%(a,y,x))
continue
obj = gm[y][x]
if obj == '#':
continue # skip wall
trace("new area: %s %u,%u reached from %u,%u"%(a,y,x,prevY,prevX))
visited[(y,x)] = (a, prevY, prevX)
stack.append((y,x))
if obj == 'B':
print("Bike found!")
print("Follow me: ")
path = []
# print pretty map and instructions
trace("\n".join([str(pos)+"->"+str(prev) for pos,prev in visited.items()] ))
while visited[(y,x)]:
m = visited[(y,x)]
a,y,x=m
trace("adding: ", m)
path.insert(0, m)
print("".join([a for a,_,_ in path]))
plan = [list(r) for r in gm]
trace(plan)
for a,y,x in path:
if plan[y][x] != 'B':
plan[y][x] = '*' if (y,x) != pos else "E"
for r in range(len(plan)):
print("%s\t\t%s"%(gm[r], "".join(plan[r])))
print ("\n")
return
del stack[0]
print("I can't reach the bike! My position is ", pos)
print("\n".join(gm))
print("\n")
b1 = Bike(["..#...#..",
"....#...B"])
b1.findRoute(0,0)
b1.findRoute(len(b1._m),0)
b1.findRoute(0,len(b1._m[0]))
bb = Bike(["..#...#..",
"....#.#.B"])
bb.findRoute(0,0)
b2 = Bike([".#",
".#",
"..",
"#.",
".B"])
b2.findRoute(0,0)
b3 = Bike([".....#",
".....#",
"####.#",
".B....",
".....B"])
b3.findRoute(1,3)
b4= Bike([".....#..#.....#...#",
".#####..#..#..#...#",
"...........#......#",
"..#...#..#######..#",
"..###.#......#....#",
"......#........#..#",
".##.######..#..#..#",
"..#..B.#....#......"])
b4.findRoute(0,0)
b4.findRoute(0,10)
b4.findRoute(7,18)
Output:
Got new map! 2x9
Bike found!
Follow me:
DRRRURRDRRR
..#...#.. E.#***#..
....#...B ****#***B
You are out of map, too bad: (2, 0)
You are out of map, too bad: (0, 9)
Got new map! 2x9
I can't reach the bike! My position is (0, 0)
..#...#..
....#.#.B
Got new map! 5x2
Bike found!
Follow me:
DDRDD
.# E#
.# *#
.. **
#. #*
.B .B
Got new map! 5x6
Bike found!
Follow me:
RDDDR
.....# .....#
.....# ...E*#
####.# ####*#
.B.... .B..*.
.....B ....*B
Got new map! 8x19
Bike found!
Follow me:
DDDDDRRRDDRR
.....#..#.....#...# E....#..#.....#...#
.#####..#..#..#...# *#####..#..#..#...#
...........#......# *..........#......#
..#...#..#######..# *.#...#..#######..#
..###.#......#....# *.###.#......#....#
......#........#..# ****..#........#..#
.##.######..#..#..# .##*######..#..#..#
..#..B.#....#...... ..#**B.#....#......
Bike found!
Follow me:
DDLLLLLDDDLLDDRR
.....#..#.....#...# .....#..#.E...#...#
.#####..#..#..#...# .#####..#.*#..#...#
...........#......# .....******#......#
..#...#..#######..# ..#..*#..#######..#
..###.#......#....# ..###*#......#....#
......#........#..# ...***#........#..#
.##.######..#..#..# .##*######..#..#..#
..#..B.#....#...... ..#**B.#....#......
Bike found!
Follow me:
LLLLUULLULLLLUULLLDDDLLDDRR
.....#..#.....#...# .....#..#.....#...#
.#####..#..#..#...# .#####..#..#..#...#
...........#......# .....****..#......#
..#...#..#######..# ..#..*#.*#######..#
..###.#......#....# ..###*#.*****#....#
......#........#..# ...***#.....***#..#
.##.######..#..#..# .##*######..#.*#..#
..#..B.#....#...... ..#**B.#....#.****E
package cup.google;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class NearestBike {
/* You are given a campus map with the Google buildings, roads and Google
bikes. You have to help the employee find the nearest Google bike.
Campus map:
. - Free path/road
# - Building
B - Google bike
Employee location - (x, y) - (1, 2)
. . . . . #
. . E . . #
# # # # . #
. B . . . .
. . . . . B
*/
public static void main(String[] args) {
int[][] matrix = {{0,0,0,0,0,1},{0,0,0,0,0,1},{1,1,1,1,0,1},{0,2,0,0,0,0},{0,0,0,0,0,2}};
Point employee = new Point(1,2);
bfsBikeSearch(matrix, employee);
}
public static List<Point> getAdjacentPaths(int[][] matrix, Point start){
List<Point> adjacnetPaths = new ArrayList<NearestBike.Point>();
if(start.x-1>=0 && matrix[start.x-1][start.y] !=1) adjacnetPaths.add(new Point(start.x-1,start.y));
if(start.x+1 < matrix.length && matrix[start.x+1][start.y] !=1) adjacnetPaths.add(new Point(start.x+1,start.y));
if(start.y-1 >=0 && matrix[start.x][start.y-1] !=1 ) adjacnetPaths.add(new Point(start.x,start.y-1));
if(start.y+1 < matrix[0].length && matrix[start.x][start.y+1] !=1) adjacnetPaths.add(new Point(start.x,start.y+1));
return adjacnetPaths;
}
public static void bfsBikeSearch(int[][] matrix, Point employee){
if(matrix[employee.x][employee.y] == 2) {
System.out.println("Fount bike at employee location (" + employee.x + "," + employee.y + ")"); return;
}
Queue<Point> queue = new LinkedList<Point>();
Set<Point> visited = new HashSet<NearestBike.Point>();
visited.add(employee);
queue.add(employee);
while(!queue.isEmpty()){
Point loc = queue.remove();
List<Point> neighbors = getAdjacentPaths(matrix, loc);
for(Point neighbor : neighbors){
if(!visited.contains(neighbor)){
if(matrix[neighbor.x][neighbor.y] == 2){
System.out.println("Fount bike at employee location (" + neighbor.x + "," + neighbor.y + ")"); return;
}else{
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
}
static class Point{
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
public Point(){
}
}
}
package cup.google;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class NearestBike {
/* You are given a campus map with the Google buildings, roads and Google
bikes. You have to help the employee find the nearest Google bike.
Campus map:
. - Free path/road
# - Building
B - Google bike
Employee location - (x, y) - (1, 2)
. . . . . #
. . E . . #
# # # # . #
. B . . . .
. . . . . B
*/
public static void main(String[] args) {
int[][] matrix = {{0,0,0,0,0,1},{0,0,0,0,0,1},{1,1,1,1,0,1},{0,2,0,0,0,0},{0,0,0,0,0,2}};
Point employee = new Point(1,2);
bfsBikeSearch(matrix, employee);
}
public static List<Point> getAdjacentPaths(int[][] matrix, Point start){
List<Point> adjacnetPaths = new ArrayList<NearestBike.Point>();
if(start.x-1>=0 && matrix[start.x-1][start.y] !=1) adjacnetPaths.add(new Point(start.x-1,start.y));
if(start.x+1 < matrix.length && matrix[start.x+1][start.y] !=1) adjacnetPaths.add(new Point(start.x+1,start.y));
if(start.y-1 >=0 && matrix[start.x][start.y-1] !=1 ) adjacnetPaths.add(new Point(start.x,start.y-1));
if(start.y+1 < matrix[0].length && matrix[start.x][start.y+1] !=1) adjacnetPaths.add(new Point(start.x,start.y+1));
return adjacnetPaths;
}
public static void bfsBikeSearch(int[][] matrix, Point employee){
if(matrix[employee.x][employee.y] == 2) {
System.out.println("Fount bike at employee location (" + employee.x + "," + employee.y + ")"); return;
}
Queue<Point> queue = new LinkedList<Point>();
Set<Point> visited = new HashSet<NearestBike.Point>();
visited.add(employee);
queue.add(employee);
while(!queue.isEmpty()){
Point loc = queue.remove();
List<Point> neighbors = getAdjacentPaths(matrix, loc);
for(Point neighbor : neighbors){
if(!visited.contains(neighbor)){
if(matrix[neighbor.x][neighbor.y] == 2){
System.out.println("Fount bike at employee location (" + neighbor.x + "," + neighbor.y + ")"); return;
}else{
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
}
static class Point{
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
public Point(){
}
}
}
package cup.google;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class NearestBike {
/* You are given a campus map with the Google buildings, roads and Google
bikes. You have to help the employee find the nearest Google bike.
Campus map:
. - Free path/road
# - Building
B - Google bike
Employee location - (x, y) - (1, 2)
. . . . . #
. . E . . #
# # # # . #
. B . . . .
. . . . . B
*/
public static void main(String[] args) {
int[][] matrix = {{0,0,0,0,0,1},{0,0,0,0,0,1},{1,1,1,1,0,1},{0,2,0,0,0,0},{0,0,0,0,0,2}};
Point employee = new Point(1,2);
bfsBikeSearch(matrix, employee);
}
public static List<Point> getAdjacentPaths(int[][] matrix, Point start){
List<Point> adjacnetPaths = new ArrayList<NearestBike.Point>();
if(start.x-1>=0 && matrix[start.x-1][start.y] !=1) adjacnetPaths.add(new Point(start.x-1,start.y));
if(start.x+1 < matrix.length && matrix[start.x+1][start.y] !=1) adjacnetPaths.add(new Point(start.x+1,start.y));
if(start.y-1 >=0 && matrix[start.x][start.y-1] !=1 ) adjacnetPaths.add(new Point(start.x,start.y-1));
if(start.y+1 < matrix[0].length && matrix[start.x][start.y+1] !=1) adjacnetPaths.add(new Point(start.x,start.y+1));
return adjacnetPaths;
}
public static void bfsBikeSearch(int[][] matrix, Point employee){
if(matrix[employee.x][employee.y] == 2) {
System.out.println("Fount bike at employee location (" + employee.x + "," + employee.y + ")"); return;
}
Queue<Point> queue = new LinkedList<Point>();
Set<Point> visited = new HashSet<NearestBike.Point>();
visited.add(employee);
queue.add(employee);
while(!queue.isEmpty()){
Point loc = queue.remove();
List<Point> neighbors = getAdjacentPaths(matrix, loc);
for(Point neighbor : neighbors){
if(!visited.contains(neighbor)){
if(matrix[neighbor.x][neighbor.y] == 2){
System.out.println("Fount bike at employee location (" + neighbor.x + "," + neighbor.y + ")"); return;
}else{
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
}
static class Point{
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
public Point(){
}
}
}
static final int [][] DIRS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
static class Coordinate {
int i;
int j;
int distance;
public Coordinate(int i, int j, int distance) {
this.i = i;
this.j = j;
this.distance = distance;
}
@Override
public String toString() {
return "(" + this.i + ", " + this.j + ") " + this.distance;
}
}
public static Coordinate findNearestBike(char [][] campus, Coordinate start) {
Queue<Coordinate> q = new LinkedList<>();
Coordinate min = new Coordinate(-1, -1, campus.length * campus[0].length + 1);
boolean [][] visited = new boolean[campus.length][campus[0].length];
q.add(start);
visited[start.i][start.j] = true;
while (!q.isEmpty()) {
Coordinate top = q.poll();
if (campus[top.i][top.j] == 'B') {
if (top.distance < min.distance) {
min.distance = top.distance;
min.i = top.i;
min.j = top.j;
}
}
for (int [] dir : DIRS) {
int i = top.i + dir[0];
int j = top.j + dir[1];
if (i < 0 || i >= campus.length || j < 0 || j >= campus[0].length) continue;
if (campus[i][j] == '#' || visited[i][j]) continue;
q.add(new Coordinate(i, j, top.distance + 1));
visited[i][j] = true;
}
}
return min;
}
char grid[][] = { {'-', '-', '-', '-', '-', '#'},
{'-', '-', 'E', '-', '-', '#'},
{'#', '#', '#', '#', '-', '#'},
{'-', 'B', '-', '-', '-', '-'},
{'-', '-', '-', '-', '-', 'B'}
};
System.out.println(findNearestBike(grid, new Coordinate(1, 2, 0)).toString());
prints (4, 5) 6
public class GoogleCampusQuestion {
final static private int BUILDING = 1;
final static private int BIKE = 2;
static class Point{
public int x;
public int y;
public int step;
public Point(int x, int y,int step){
this.x = x;
this.y = y;
this.step = step;
}
}
public static int numOfStepsToNearestBike(int[][] campus, int campusWidth, int campusHeight, int row, int col) {
Queue<Point> points = new LinkedList<>();
Set<Point> visited = new HashSet<>();
Point firstPosition = new Point(col,row,0);
points.add(firstPosition);
visited.add(firstPosition);
int minSteps = campusWidth*campusHeight;
while(!points.isEmpty()) {
Point p = points.remove();
if(p.step > minSteps)
continue;
if(campus[p.y][p.x] == BIKE){
if(p.step < minSteps)
minSteps = p.step;
}
Point right = new Point(p.x + 1,p.y,p.step + 1);
if(isValidMove(campus,campusWidth,campusHeight,right,visited)){
points.add(right);
visited.add(right);
}
Point up = new Point(p.x,p.y + 1,p.step + 1);
if(isValidMove(campus,campusWidth,campusHeight,up,visited)){
points.add(up);
visited.add(up);
}
Point left = new Point(p.x - 1,p.y,p.step + 1);
if(isValidMove(campus,campusWidth,campusHeight,left,visited)){
points.add(left);
visited.add(left);
}
Point down = new Point(p.x,p.y - 1,p.step + 1);
if(isValidMove(campus,campusWidth,campusHeight,down,visited)){
points.add(down);
visited.add(down);
}
}
return minSteps;
}
private static boolean isValidMove(int[][] campus, int campusWidth, int campusHeight,Point point,Set<Point> visited) {
if (point.x >= campusWidth || point.y >= campusHeight || point.x < 0 || point.y < 0)
return false;
int position = campus[point.y][point.x];
return position != BUILDING && !visited.contains(point);
}
public static void main(String[] args) {
int[][] board = new int[][]{
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 2, 0, 0},
{0, 0, 1, 0, 0, 2, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 0, 0, 1, 0}
};
int width = 10;
int height = 5;
int row = 0;
int col = 0;
int minSteps = numOfStepsToNearestBike(board,width,height, row, col);
System.out.println(minSteps);
}
}
I think this problem should be done with simultaneous BFS, i.e BFS from all the Bs to E at the same time. And on every new node (spot), if it has already been visited (let's say by B1) that means it is at a shorter distance from other B1 than the one currently in execution (let's say B2), so it should not be visited by B2, nor should B2 visit that node's neighbors.
bfs
- Inno August 30, 2018