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

- Inno August 30, 2018 | Flag Reply
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
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'])

- prudent_programmer September 23, 2018 | Flag Reply
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.

- deepaklather2709 August 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A*

- avv August 30, 2018 | Flag Reply
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;
}

- Alex October 18, 2018 | Flag Reply
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!")
                    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

- Diana.Savvatina November 09, 2018 | Flag Reply
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.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(){

}

}



}

- Anonymous November 15, 2018 | Flag Reply
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.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(){

}

}



}

- cci November 15, 2018 | Flag Reply
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.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(){
			
		}
		
	}
	
	

}

- hojoborolo.ultopalta November 15, 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