## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

bfs

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

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
if not googleMap or not googleMap[0] or not employeeLocation:
return 0

minCost = 0
pathToBuilding = []
# 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:

queue.append((nextX, nextY, currCost + 1, path + [dir]))

return (minCost, pathToBuilding)``````

Test Code

``````# Test Case 1
['.', '.', '.', '.', '.', '#'],
['.', '.', 'E', '.', '.', '#'],
['#', '#', '#', '#', '.', '#'],
['.', 'B', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', 'B']
]
# OUTPUTS: (6, ['R', 'R', 'D', 'D', 'R', 'D'])

# Test Case 2
['.', '.', '.', '.', '.', '#'],
['.', '.', 'E', '.', '.', '#'],
['#', '#', '#', '#', '.', '#'],
['B', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.']
]
# OUTPUTS: (8, ['R', 'R', 'D', 'D', 'L', 'L', 'L', 'L'])``````

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

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.

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

A*

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

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

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

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!")
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
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!
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!
DDRDD
.#		E#
.#		*#
..		**
#.		#*
.B		.B

Got new map! 5x6
Bike found!
RDDDR
.....#		.....#
.....#		...E*#
####.#		####*#
.B....		.B..*.
.....B		....*B

Got new map! 8x19
Bike found!
DDDDDRRRDDRR
.....#..#.....#...#		E....#..#.....#...#
.#####..#..#..#...#		*#####..#..#..#...#
...........#......#		*..........#......#
..#...#..#######..#		*.#...#..#######..#
..###.#......#....#		*.###.#......#....#
......#........#..#		****..#........#..#
.##.######..#..#..#		.##*######..#..#..#
..#..B.#....#......		..#**B.#....#......

Bike found!
DDLLLLLDDDLLDDRR
.....#..#.....#...#		.....#..#.E...#...#
.#####..#..#..#...#		.#####..#.*#..#...#
...........#......#		.....******#......#
..#...#..#######..#		..#..*#..#######..#
..###.#......#....#		..###*#......#....#
......#........#..#		...***#........#..#
.##.######..#..#..#		.##*######..#..#..#
..#..B.#....#......		..#**B.#....#......

Bike found!
LLLLUULLULLLLUULLLDDDLLDDRR
.....#..#.....#...#		.....#..#.....#...#
.#####..#..#..#...#		.#####..#..#..#...#
...........#......#		.....****..#......#
..#...#..#######..#		..#..*#.*#######..#
..###.#......#....#		..###*#.*****#....#
......#........#..#		...***#.....***#..#
.##.######..#..#..#		.##*######..#.*#..#
..#..B.#....#......		..#**B.#....#.****E``````

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

import java.util.ArrayList;
import java.util.HashSet;
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 < 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));

}

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>();

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{
}
}

}
}
}

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(){

}

}

}

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

``````package cup.google;

import java.util.ArrayList;
import java.util.HashSet;
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 < 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));

}

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>();

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{
}
}

}
}
}``````

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(){

}

}

}

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

``````package cup.google;

import java.util.ArrayList;
import java.util.HashSet;
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 < 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));

}

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>();

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{
}
}

}
}
}

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(){

}

}

}``````

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

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

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

``````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);
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)){
}
Point up = new Point(p.x,p.y + 1,p.step + 1);
if(isValidMove(campus,campusWidth,campusHeight,up,visited)){
}
Point left = new Point(p.x - 1,p.y,p.step + 1);
if(isValidMove(campus,campusWidth,campusHeight,left,visited)){
}
Point down = new Point(p.x,p.y - 1,p.step + 1);
if(isValidMove(campus,campusWidth,campusHeight,down,visited)){
}
}
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);
}

}``````

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

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.

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.